¿Cómo se define la adición?

Question

He estado leyendo Sobre números y juegos y me he dado cuenta de que Conway define la adición en su sistema numérico en términos de suma. Del mismo modo, en los libros de análisis y lógica que he leído (estoy seguro de que esto no es así en todos los libros de este tipo) se asume cómo funciona la adición. Por lo que tengo entendido, el método tradicional de construcción del sistema numérico comienza con los números naturales (y el cero)

$0:=|\emptyset|$

$1:=|\{\emptyset\}|$

$2:=|\{\emptyset,\{\emptyset\}\}|$

y así sucesivamente. En esta construcción la adición podría (?) definirse como la unión disjunta de los conjuntos asociados a los dos números. Entonces los enteros podrían definirse como la inversa aditiva y así sucesivamente. Pero, ¿es ésta la forma ideal de hacerlo? ¿Existe un método más elegante?

Answer 1

No se tiene una noción a priori de cardinalidad, por lo que no se puede decir realmente cosas como " $0:=|\emptyset|$ ". De hecho, antes de poder definir los cardinales se suelen definir los ordinales, y normalmente la definición de los naturales precede a la de los ordinales.

El método de la teoría de conjuntos comienza utilizando el Axioma del Infinito, que establece que existe al menos un conjunto inductivo; un conjunto $X$ es inductivo si y sólo si (i) $\emptyset\in X$ y (ii) Para todos los $x$ Si $x\in X$ entonces $s(x) = x\cup\{x\}\in X$ .

Por lo tanto, dejemos que $X$ sea cualquier conjunto inductivo. Entonces definimos $$\mathbb{N} = \cap\\{ A\subseteq X\mid \text{$ A $ is inductive}\\}.$$ Entonces se puede demostrar que $\mathbb{N}$ está bien definido (no depende de la elección de $X$ ) y satisface los "Axiomas de Peano":

1. $\emptyset \in\mathbb{N}$ .
2. Si $x\in\mathbb{N}$ entonces $s(x) \in\mathbb{N}$ .
3. Para todos $x\in\mathbb{N}$ , $s(x)\neq\emptyset$ .
4. Para todos $x,y\in\mathbb{N}$ Si $s(x)=s(y)$ entonces $x=y$ .
5. Si $S\subseteq \mathbb{N}$ es inductivo, entonces $S=\mathbb{N}$ .

(De hecho, 3 y 4 son sólo consecuencias de la definición de $s(x)$ ). A continuación, definimos " $0$ " para significar $\emptyset$ , " $1$ " para significar $s(0)$ , " $2$ " para significar $s(1)=s(s(0))$ etc.

También puedes empezar con los axiomas de Peano. Aquí, hay una noción primitiva llamada "número natural", y un símbolo primitivo llamado $0$ . También tenemos una función primitiva $s$ . Los axiomas de Peano serían:

1. $0$ es un número natural.
2. Si $n$ es un número natural, entonces $s(n)$ es un número natural.
3. Para todos los números naturales $n$ , $s(n)\neq 0$ .
4. Para todos los números naturales $n$ y $m$ Si $s(n)=s(m)$ entonces $n=m$ .
5. Esquema del axioma de inducción. Si $\Phi$ es un predicado tal que $\Phi(0)$ es cierto, y para todos $n$ , $\Phi(n)\Rightarrow \Phi(s(n))$ entonces para todos los números naturales $k$ , $\Phi(k)$ .

(También puede comenzar con $1$ en lugar de $0$ Utilizo $0$ porque entonces es paralela a la construcción teórica de conjuntos). A continuación, definimos " $1$ " para significar $s(0)$ y " $2$ " para significar $s(1)=s(s(0))$ etc.

Entonces necesitamos el Teorema de Recursión:

Teorema de recursión. Dado un conjunto $X$ , un elemento $a\in X$ y una función $f\colon X\to X$ existe una única función $F\colon\mathbb{N}\to X$ tal que $F(0)=a$ y $F(s(n)) = f(F(n))$ para todos $n\in\mathbb{N}$ .

Una vez que tenemos estas definiciones y el teorema, podemos empezar a definir la suma. Fijar $n\in\mathbb{N}$ . Voy a definir "añadir $n$ ", $+_n\colon \mathbb{N}\to\mathbb{N}$ dejando \begin{align*} +_n(0) &= n,\\\ +_n(s(m)) &= s(+_n(m)). \end{align*} O, en notación habitual, \begin{align*} n+0& = n,\\\ n+s(m) &= s(n+m). \end{align*}

Con estas definiciones, tenemos:

Teorema. Para todos $n\in\mathbb{N}$ , $n+0=0+n=n$ .

Prueba. Dejemos que $S=\{n\in\mathbb{N}\mid n+0=0+n=n\}$ . Tenga en cuenta que $0\in S$ ya que $0+0 = 0$ por la definición de adición. Supongamos ahora que $k\in S$ Eso significa que $k+0 = 0+k = k$ . Entonces $0+s(k) = s(0+k) = s(k)$ (primera igualdad por la definición de adición con $0$ , segundo por la hipótesis de inducción). Y por la definición de adición con $s(k)$ tenemos $s(k)+0 = s(k)$ . Por lo tanto, $k\in S$ implica $s(k)\in S$ . Así, $S=\mathbb{N}$ , según se desee. QED

Teorema. Para todos $n\in\mathbb{N}$ , $s(n)=n+1$

Prueba. Dejemos que $S=\{n\in\mathbb{N}\mid s(n)=n+1\}$ . Primero, $0\in S$ ya que $s(0) = 1 = 0+1$ por el teorema anterior. Supongamos que $k\in S$ Eso significa que $s(k)=k+1$ . Entonces $s(s(k)) = s(s(k)+0) = s(k)+s(0) = s(k)+1$ . Así que $k\in S$ implica $s(k)\in S$ Por lo tanto $S=\mathbb{N}$ . QED

Teorema. Para todos $\ell,n,m\in\mathbb{N}$ , $\ell+(m+n) = (\ell+m)+n$ .

Prueba. Fijar $\ell$ y $m$ . Dejemos que $S=\{n\in\mathbb{N}\mid \ell+(m+n)=(\ell+m)+n\}$ . Tenemos $0\in S$ ya que $$\ell + (m+0) = \ell + m = (\ell+m) + 0.$$ Supongamos ahora que $k\in S$ Eso significa que $(\ell+m)+k = \ell+(m+k)$ . Demostramos que $s(k)\in S$ . Tenemos: $$(\ell+m)+s(k) = s((\ell+m)+k) = s(\ell+(m+k)) = \ell+s(m+k) = \ell+(m+s(k)).$$ Así, si $k\in S$ entonces $s(k)\in S$ . Por lo tanto, $S=\mathbb{N}$ . QED

Lema. Para todos $n\in\mathbb{N}$ , $1+n = n+1$ .

Prueba. Dejemos que $S=\{n\in\mathbb{N}\mid 1+n=n+1\}$ . Entonces $0\in S$ . Supongamos que $k\in S$ para que $1+k = k+1 = s(k)$ . Entonces tenemos: $$1+s(k) = s(1+k) = s(k+1) = s(k+s(0)) = s(s(k+0)) = s(s(k)) = s(k)+1.$$ Así, $S=\mathbb{N}$ . QED

Teorema. Para todos $n,m\in\mathbb{N}$ , $n+m=m+n$ .

Prueba. Fijar $m$ y que $S=\{n\in\mathbb{N}\mid m+n=n+m\}$ . Primero, $0\in S$ ya que $m+0=0+m$ . También, $1\in S$ por el lema anterior. Supongamos ahora que $k\in S$ . Entonces $m+k=k+m$ . Para demostrar que $s(k)\in S$ tenemos: \begin{align*} m+s(k) &= s(m+k) = s(k+m) = (k+m)+1 = k+(m+1) = k+(1+m)\\\ &= (k+1)+m = s(k)+m. \end{align*} Así, $S=\mathbb{N}$ . QED

Y así sucesivamente. Podemos entonces definir la multiplicación de manera similar, fijando $n$ y definiendo \begin{align*} n\times 0 &= 0\\\ n\times s(m) &= (n\times m) + n, \end{align*} y demostrar las propiedades habituales de la multiplicación de forma inductiva. Entonces podemos definir la exponenciación también recursivamente: fijar $n$ Entonces \begin{align*} n^0 & = 1\\\ n^{s(m)} &= n^m\times n. \end{align*} Posteriormente definimos el orden entre los números naturales por $$a\leq b\Longleftrightarrow \exists n\in\mathbb{N}(a+n=b),$$ y demostrar las propiedades habituales.

Más tarde, podemos construir $\mathbb{Z}$ de $\mathbb{N}$ , $\mathbb{Q}$ de $\mathbb{Z}$ , $\mathbb{R}$ de $\mathbb{Q}$ , $\mathbb{C}$ de $\mathbb{R}$ etc. Véase, por ejemplo, mi respuesta a esta pregunta anterior .

Answer 2

Jacob, hay dos maneras de definir la adición de números naturales en la teoría de conjuntos.

El primero es el que tú indicas: La suma de dos números es el tamaño de su unión disjunta. En general, se define adición cardinal de esta manera: Si $\kappa$ y $\lambda$ son cardinales (tamaños de conjuntos), digamos $\kappa=|A|$ y $\lambda=|B|$ entonces $\kappa+\lambda=|A\sqcup B|$ , donde $\sqcup$ denota la unión disjunta.

La segunda forma es definir adición ordinal considerando los números naturales como conjuntos ordenados: $0=\emptyset$ , $1=\{0\}$ , $2=\{0,1\}$ etc., con $n=\{0,\dots,n-1\}$ ordenados de la forma habitual, que en realidad corresponde a la afiliación: $a<b$ si $a\in b$ . Aquí identificamos dos conjuntos linealmente ordenados si son de orden isomorfo. La noción relevante aquí es la de suma de conjuntos ordenados: Si $(A,<)$ y $(B,\prec)$ son órdenes lineales, su suma $A+B$ es el conjunto $A\sqcup B$ ordenado por $a$ es menor que $b$ si $a,b\in A$ y $a<b$ o $a,b\in B$ y $a\prec b$ o $a\in A$ y $b\in B$ .

Se puede comprobar que estas dos nociones coinciden cuando $A$ , $B$ son conjuntos finitos (es decir, cuando miramos $n+m$ para $n,m$ finito). Hay que tener cuidado, porque las nociones son diferentes en general para los conjuntos infinitos. Por ejemplo, si $\aleph_0=|{\mathbb N}|$ entonces $\aleph_0+1=1+\aleph_0=\aleph_0$ . Sin embargo, si pensamos en $\aleph_0$ como el conjunto ordenado $\{0<1<\dots\}$ entonces $1+\aleph_0=\aleph_0$ (recordemos que identificamos los conjuntos si son de orden isomorfo). Sin embargo, $\aleph_0+1$ es estrictamente mayor que $\aleph_0$ como conjuntos ordenados.

Hay una tercera opción en el contexto de la aritmética: Todo lo que necesitamos es la noción de sucesor. El sucesor de 0 es 1, de 1 es 2, etc. Denotemos por $S(n)$ el sucesor de $n$ (en general, $S(n)=n+1$ por supuesto). Obsérvese que "sucesor de $n$ "es una noción teórica de orden: El menor número mayor que $n$ . Entonces definimos $n+m$ recursivamente: $n+0=n$ y $n+S(m)=S(n+m)$ .

---

Podemos continuar y definir, por ejemplo, la multiplicación y la exponenciación también de estas tres maneras. La multiplicación cardinal es el tamaño del producto cartesiano. La exponenciación cardinal $|A|^{|B|}$ es el tamaño del conjunto de funciones de $B$ a $A$ .

Multiplicación ordinal $\alpha\beta$ significa: " $\beta$ copias de $\alpha$ ". Así que $\aleph_02=\aleph_0+\aleph_0$ mientras que $2\aleph_0=\aleph_0$ .

La exponenciación ordinal es un poco más complicada de definir: Para conjuntos ordenados $\alpha,\beta$ tal que $\alpha$ tiene un mínimo $0$ , defina $F(\alpha,\beta)$ como el conjunto formado por aquellas funciones $f:\beta\to\alpha$ tal que sólo hay un número finito de $\xi$ tal que $f(\xi)\ne0$ .

Para las funciones $f,g$ en $F(\alpha,\beta)$ set $f\triangleleft g$ si $f(\xi)<g(\xi)$ (en el orden de $\alpha$ ) para $\xi$ mayor (en el orden de $\beta$ ) tal que $f(\xi)\ne g(\xi)$ .

Entonces $\alpha^\beta$ se define como el tipo de orden de $(F(\alpha,\beta),\triangleleft)$ .

De nuevo, estas nociones coinciden para los números finitos, pero difieren mucho para los conjuntos infinitos.

Las definiciones recursivas vienen dadas por $n\cdot 0=0$ y $n\cdot S(m)=nm+n$ y $n^0=1$ (incluso si $n=0$ ) y $n^{S(m)}=n^m\cdot n$ .

Answer 3

Una forma extremadamente elegante de definir los números que quiero mencionar no utiliza establece pero cálculo lambda es decir, funciones y aplicación de funciones. El sistema utilizado se llama Codificación eclesiástica .

La idea es la siguiente: Dos , por ejemplo, significa hacer algo por dos veces.

Más concretamente, cuando tenemos alguna operación (una función) y un valor, aplicamos esta función dos veces sobre este valor. En notación lambda

$$ 2 \equiv \lambda f\,x \mapsto f (f\,x) $$

Así que, en general, cualquier número $n$ se define como una función que toma otra función y devuelve su $n$ th iterar .

Ahora podemos definir simplemente la adición como una composición de funciones . Primero aplicamos la función $n$ veces, entonces $m$ veces y así conseguimos un total de $n+m$ aplicaciones.

$$ n + m \equiv \lambda f\,x \mapsto n f (m f x)$$

Por ejemplo, terminamos con

$$ 2 + 3 \equiv \lambda f\,x \mapsto f (f (f (f (f\,x)))) \equiv 5 $$