[Carlos Ivorra]

Ha llegado el momento de empezar a usar NFA:

La fórmula \( x=x \) es trivialmente estratificada (no creo que merezca poner la prueba en spoiler), luego podemos definir el conjunto universal:

\( V\equiv \{x\mid x=x\} \).

Así, \( V \) es, no el conjunto de todos los conjuntos, sino el conjunto de todos los objetos, pues contiene a todos los conjuntos y a todos los átomos. Nada nos impide definir el conjunto de todos los conjuntos y el conjunto de todos los átomos:

\( C\equiv \{x\mid \text{cto}\,x\}\qquad A\equiv \{x\mid \lnot \text{cto}\,x\} \)

Esto es correcto porque las fórmulas correspondientes están estratificadas (recordemos que la definición de estratificación no impone ninguna restricción al signo \( \text{cto} \)).

Igualmente podemos definir el conjunto vacío:

\( \emptyset\equiv \{x\mid x\neq x\} \)

Una nota técnica:

Spoiler

Alguien podría pensar que podríamos haber incorporado el axioma de los átomos a la teoría a la vez que eliminábamos el signo primitivo cto definiendo un átomo como un objeto sin elementos y un conjunto como un objeto con elementos. Eso no es conveniente porque nos interesa que la teoría tenga un conjunto vacío, es decir, un objeto que no tiene elementos y, a pesar de ello, no es un átomo, sino un conjunto. El axioma de extensionalidad implica que el conjunto vacío es el único conjunto sin elementos, pues dos conjuntos vacíos serían dos conjuntos con los mismos elementos (ninguno) y no puede haber dos conjuntos distintos con los mismos elementos. En cambio, el axioma de extensionalidad no afecta a los átomos, por lo que nada impide que haya muchos átomos distintos y que ninguno tenga elementos.

[cerrar]

Ahora definimos las operaciones conjuntistas básicas (no explico su significado porque son de sobra conocidas):

\( A\cup B \equiv \{x\mid x\in A\lor x\in B\},\qquad A\cap B \equiv \{x\mid x\in A\land x\in B\}, \)

\( A\setminus B\equiv \{x\mid x\in A\land x\notin B\},\qquad \overline A=\{x\mid x\notin A\} \).

Observemos en particular la última definición, que no es posible en ZFC (o, al menos, da lugar a una clase propia): el conjunto complementario de un conjunto \( A \) es el conjunto de todos los objetos que no están en \( A \). Una definición alternativa sería: \( \overline A =V\setminus A \), aunque también podríamos haber definido \( A\setminus B = A\cap \overline B \).

El lector no debería tener dificultad en probar que todas las fórmulas que hemos usado están estratificadas. Por si acaso pongo un spoiler con las estratificaciones:

Spoiler

\( x_0\in A_1\lor x_0\in B_1 \)

\( x_0\in A_1\land x_0\in B_1 \)

\( x_0\in A_1\land \lnot x_0\in B_1 \)

\( \lnot x_0\in A_1 \)

[cerrar]

A partir de estas definiciones se pueden probar todas las relaciones usuales entre estos conceptos exactamente igual a como se hace en ZFC, con la ventaja incluso de que disponemos de un conjunto universal (hemos salvado el universo), de modo que los conjuntos forman una auténtica álgebra de Boole.

Cabe destacar algunas relaciones obvias que pueden "chirriar" a una mente clásica: \( V\in C,\quad C\in V, \quad V\in V,\quad C\in C \).

También podemos definir las grandes uniones e intersecciones:

\( \bigcup X\equiv \{x\mid \exists Y\in X\ x\in Y\},\qquad \bigcap X\equiv \{x\mid \forall Y\in X\ x\in Y\} \).

Así, \( \bigcup X \) es el conjunto cuyos elementos son todos los elementos de los conjuntos que pertenecen al conjunto \( X \) (si \( X \) contiene átomos, éstos no afectan a la definición de \( \bigcup X \), en el sentido de que el conjunto \( X\setminus A \) tiene la misma gran unión). Similarmente, \( \bigcap X \) es el conjunto cuyos elementos son todos los objetos que pertenecen a todos los conjuntos que pertenecen a \( X \). En otras palabras, la gran unión es la unión de todos los conjuntos que pertenecen a \( X \) y la gran intersección es la intersección de todos los conjuntos que pertenecen a \( X \).

Unas cuantas preguntas sobre estos dos conceptos:

1) Probar que las fórmulas que los definen están estratificadas.

2) Probar que los términos \( \bigcup X \) y \( \bigcap X \) están estratificados, ¿cuál es su tipo respecto del tipo de \( X \)?

3) ¿Quiénes son \( \bigcup \emptyset \) y \( \bigcap \emptyset \)?

Respuestas:

Spoiler

1) Unas estratificaciones para las fórmulas que los definen son:

\(  \exists Y_1\in X_2\ x_0\in Y_1 \)

\( \forall Y_1\in X_2\ x_0\in Y_1 \)

2) Unas estratificaciones para los términos son:

\( \bigcup X\equiv \{x_0\mid \exists Y_1\in X_2\ x_0\in Y_1\}_1,\qquad \bigcap X\equiv \{x_0\mid \forall Y_1\in X_2\ x_0\in Y_1\}_1 \)

Aquí hemos usado que, en general,

\( \{x\mid \phi(x)\}\equiv A\mid\forall x(x\in A\leftrightarrow \phi(x)) \)

y, si la fórmula \( \phi(x) \) está estratificada con una estratificación que asigna tipo \( n \) a la variable \( x \), entonces el término está estratificado asignando a la variable \( A \) el tipo \( n+1 \) (por la propiedad 3 de la definición de estratificación) y asignando a todo el término (es decir, a la descripción) el mismo tipo que a la variable \( A \) (por la propiedad 5), luego, en general:

El tipo de un término \( \{x\mid \phi(x)\} \), donde \( \phi(x) \) es una fórmula estratificada, es una unidad mayor que el tipo de la variable \( x \) en la estratificación de \( \phi \).

En nuestros ejemplos, como la variable \( x \) tiene tipo \( 0 \), la gran unión y la gran intersección tienen ambas tipo \( 1 \), y así lo expresa el subíndice de más a la derecha.

La respuesta a la segunda pregunta es que el tipo de \( \bigcup X \) y \( \bigcap X \) es siempre una unidad inferior al tipo de \( X \). En la estratificación concreta que hemos considerado \( X \) tiene tipo \( 2 \) y la unión y la intersección tienen tipo \( 1 \), pero podríamos haber asignado arbitrariamente tipo \( n \) a la variable \( X \) y el tipo de la unión y la intersección habría sido \( n-1 \), como es fácil comprobar. En otras palabras: la gran unión y la gran intersección rebajan el tipo una unidad.

3) Esto es un ejercicio de la "lógica del vacío":

\( \bigcup\emptyset = \emptyset,\quad \bigcap\emptyset =V \).

En efecto, para que un objeto perteneciera a \( \bigcup \emptyset \) tendría que pertenecer a un conjunto perteneciente a \( \emptyset \). Como no hay tal conjunto, la unión es vacía.

Para que un objeto no perteneciera a \( \bigcap\emptyset \), debería haber un conjunto en \( \emptyset \) al cual no perteneciera, como eso es imposible, todo objeto está en la intersección.

[cerrar]

Otro concepto conjuntista básico es

\( \mathcal PA\equiv \{X\mid X\subset A\} \)

Claramente, se trata del conjunto de todos los subconjuntos de \( A \). Ya vimos en el mensaje anterior que la fórmula \( X\subset A \) está estratificada. ¿Cuál es el tipo de \( \mathcal PA \) en función del tipo de \( A \)?

Respuesta:

Spoiler

Si asignamos a \( A \) el tipo \( 0 \), entonces \( X \) tiene también tipo \( 0 \) y, por la observación general hecha en el spoiler anterior, las llaves \( \{X\mid \cdots\} \) aumentan en una unidad el tipo de \( X \), luego el tipo de \( \mathcal PA \) es \( 1 \) o, más en general, es una unidad superior al tipo de \( A \).

[cerrar]

Naturalmente, todas las propiedades básicas sobre los conceptos que acabamos de introducir (por ejemplo, \( X\subset Y\rightarrow \mathcal PX\subset \mathcal PY \)) se demuestran exactamente igual que en ZFC con los mismos argumentos.

Una relación curiosa es que \( C=\mathcal PV \). ¿Cuál es la interpretación de \( F\equiv\mathcal P\mathcal PV \)?

Respuesta:

Spoiler

\( F \) es el conjunto de todas las familias de conjuntos, es decir, el conjunto de todos los conjuntos cuyos elementos son conjuntos (el conjunto de todos los conjuntos que no contienen átomos).

[cerrar]

En el próximo mensaje hablaremos de pares desordenados, pares ordenados y productos cartesianos, y trataré de explicar por qué ha sido conveniente tomar el concepto de par ordenado como concepto primitivo.

[Raúl Aparicio Bustillo]

Bueno, primero, decir que  "todo un honor"  haber contribuido a liar a Ivorra en NFU (o  NFA). Lo de rebautizar la teoría como NFA  me parece prudente,  simplemente por ser conciso: estamos prescindiendo del axioma de átomos. La apuesta de Ivorra es bastante fuerte, en principio pensaba que el axioma era eliminado de la teoría porque era demostrable a partir de los otros 3. Al releer los post me he dado cuenta de que no es eso lo que quiere decir. Lo destierra simplemente porque considera que los teoremas utiles se pueden deducir sin el. En cualquier caso, tampoco hay mucho  que discutir: Ivorra nos habla de una teoría que es NFA, deja claro su lenguaje, deja claro que trabajamos en logica de primer orden, y  deja claros sus 3  axiomas, el resto ya es demostrar y demostrar,y si llegasemos a una contradicción en NFA no se salvan ni NFU ni ZFC.

Una  puntualización (no necesariamente una corrección)  a raiz de un comentario de Argentinator:

 El axioma de estratificación dice que las formulas estratificadas necesariamente definen conjuntos, pero eso no implica que algunos objetos sólo definibles mediante formulas no estratificadas no puedan ser conjuntos. No es demasiado claro Holmes en su libro, y es aquí donde mi puntualización ya se transforma en  una duda: Cuando se refiere a los ordinales de Von Neumann Holmes afirma que podemos considerar que existen o que no existen. Creo que lo que trata de decir (evitandose usar la palabra "modelo") es que NFU tiene modelos con  ordinales de Von Neumann, y otros sin ellos;y  que por tanto es conveniente definir los ordinales de otra forma, que es la que comenta Ivorra, para asegurarnos que existen en la teoría (o sea, que existen en todos los modelos de la teoría). Lo que pasa es que eso de modelos sin ordinales de Von Neumann no es exactamente así: es trivial que el ordina de Von Neumann 0 (el conjunto vacio) ha de existir en todos los modelos de NFU. Me aventuraría a decir que los ordinales finitos también existen en todos los modelos de NFU. Pero de ser así ya me pierdo totalmente y no tengo nada claro que es eso de que "pueden existir pero también pueden no existir" en NFU.

[Carlos Ivorra]

Bueno, primero, decir que  "todo un honor"  haber contribuido a liar a Ivorra en NFU (o  NFA).

La verdad es que me alegro de haber conocido NFA y eso te lo debo a ti.

Lo de rebautizar la teoría como NFA  me parece prudente,  simplemente por ser conciso: estamos prescindiendo del axioma de átomos. La apuesta de Ivorra es bastante fuerte, en principio pensaba que el axioma era eliminado de la teoría porque era demostrable a partir de los otros 3. Al releer los post me he dado cuenta de que no es eso lo que quiere decir. Lo destierra simplemente porque considera que los teoremas utiles se pueden deducir sin el.

Sí, más o menos, pero, para ser más exactos: todos los teoremas que demuestra Holmes en su libro se demuestran sin el axioma de los átomos, y sin tener que hacer ningún esfuerzo para evitarlo, es que simplemente en ningún momento te hace falta para nada. No es que yo diga: "fíjate que gracias a este truco y a este otro podemos arreglárnoslas para prescindir del axioma de los átomos", sino que nunca tienes la necesidad de recurrir a él.

En cualquier caso, tampoco hay nada que discutir: Ivorra nos habla de una teoría que es NFA, da explicitamente los axiomas, y desde luego, es una teoría que es más debil que ZFC y (quizás) más debil tambien que NFU.

Añadir el axioma de los átomos no vuelve a la teoría "más fuerte", en el sentido de que todo modelo de NFA sin el axioma de los átomos se convierte en un modelo de NFA más el axioma de los átomos sin más que modificar la relación de pertenencia para "borrar" los posibles elementos de los átomos.

Una  puntualización (no necesariamente una corrección)  a raiz de un comentario de Argentinator:

El axioma de estratificación dice que las formulas estratificadas necesariamente definen conjuntos, pero eso no implica que algunos objetos sólo definibles mediante formulas no estratificadas no puedan ser conjuntos. No es demasiado claro Holmes en su libro, y es aquí donde mi puntualización ya se transforma en  una duda: Cuando se refiere a los ordinales de Von Neumann Holmes afirma que podemos considerar que existen o que no existen. Creo que lo que trata de decir (evitandose usar la palabra "modelo") es que NFU tiene modelos con  ordinales de Von Neumann, y otros sin ellos;y  que por tanto es conveniente definir los ordinales de otra forma, que es la que comenta Ivorra, para asegurarnos que existen en la teoría (o sea, que existen en todos los modelos de la teoría). Lo que pasa es que esto no es exactamente así: es trivial que el ordinal 0 (el conjunto vacio) ha de existir en todos los modelos de NFU. Me aventuraría a decir que los ordinales finitos también existen en todos los modelos de NFU. Pero de ser así ya me pierdo totalmente y no tengo nada claro que es eso de que "pueden existir pero también pueden no existir" en NFU.

El concepto de ordinal de von Neumann se puede definir en toda teoría de conjuntos entre cuyos teoremas se encuentren el axioma de extensionalidad, la existencia de la unión de dos conjuntos, del complemento de dos conjuntos, del par desordenado de dos conjuntos y del conjunto vacío. No hace falta nada más, en particular no hace falta ningún axioma de formación de conjuntos o subconjuntos a partir de fórmulas.

Todos estos resultados son teoremas de NFA, luego en NFA puedes definir el concepto de ordinal (de von Neumann) e incluso el de número natural (de von Neumann, de modo que \( 0=\emptyset, 1 = \{0\}, 2=\{0,1\} \), etc.)

Ahora bien, las fórmulas "x es un ordinal" o "x es un número natural" (en este sentido de von Neumann) no están estratificadas y, por ello dan muy poco juego. En NFA no es posible demostrar que exista el conjunto de los números naturales en este sentido (pero sí que se pueden definir de otro modo, estratificado, y todo va bien).

Observemos que esto no es una desventaja de NFA frente a ZFC, sino que la situación es simétrica: hay una posible forma de definir los números naturales que en ZFC va perfectamente y en NFA va muy mal, y otra forma de definir los números naturales que en NFA va perfectamente y en ZFC va muy mal (haría que cada número natural fuera una clase propia).

En definitiva, en NFA no puedes demostrar la existencia del ordinal de von Neumann \( \omega \) (aunque puedes definir un ordinal \( \omega \) equivalente de otro modo), pero, por otra parte, puedes tomar como axioma adicional que existe \( \omega \) (es decir, tomar como axioma que exista un conjunto cuyos elementos sean los números naturales de von Neumann), y la teoría sigue siendo consistente (supuesto que ZFC lo sea).

Por otra parte, la verdad es que en ZFC tampoco puedes demostrar la existencia de \( \omega \), sino que esto es un axioma de ZFC. En NFA puedes construir los números naturales sin necesidad de postular la existencia de \( \omega \). (Bueno, ahí hay ciertas sutilezas, pero es pronto para entrar en ellas.)

[Carlos Ivorra]

Otros conceptos elementales que en NFA se definen sin dificultad son:

\( \{x\}\equiv \{u\mid u=x\},\qquad \{x,y\}\equiv \{u\mid u=x\lor u=y\} \).

Es evidente que las fórmulas que los definen están estratificadas, con todas las variables, por ejemplo, de tipo \( 0 \).

Notemos que el criterio de que "las llaves \( \{\cdots \} \) aumentan el tipo una unidad" se cumple también en este caso:

Si \( t \) es cualquier término estratificado, entonces \( \{t\} \) también está estratificado, y su tipo es una unidad más que el tipo de \( t \).

(Pues \( \{t\}\equiv \{u\mid u=t\} \), luego, partiendo de la estratificación de \( t \), hemos de asignar a la variable \( u \) el mismo tipo que a \( t \) y a \( \{t\} \) una unidad más que a \( u \).)

Similarmente:

Un término de la forma \( \{t_1,t_2\} \) está estratificado si y sólo si los términos \( t_1 \) y \( t_2 \) admiten una estratificación conjunta (es decir, tal que los subtérminos comunes tengan siempre el mismo tipo) que les asigne a los dos el mismo tipo, y entonces el tipo de \( \{t_1,t_2\} \) es una unidad mayor.

Ahora es cuando todo aquel familiarizado con ZFC señala que podemos definir:

\( (x,y)^*\equiv \{\{x\},\{x,y\}\} \).

Pongo una estrella para distinguir esta definición del par ordenado \( (x,y) \) que hemos tomado como signo primitivo. Es muy fácil probar que

\( \forall xyuv\,((x,y)^*=(u,v)^*\leftrightarrow x=u\land y=v) \)

Y entonces ¿para qué hemos introducido el par ordenado como signo primitivo y para qué hemos incluido el axioma de los pares ordenados entre los axiomas de NFA cuando teníamos la posibilidad de definir así el par ordenado y demostrar el axioma asociado?

La respuesta es que el par ordenado \( (x,y)^* \) tiene una característica que lo distingue de \( (x,y) \) y lo hace mucho menos conveniente que éste. Observemos que, por las observaciones precedentes sobre la estratificación de los pares desordenados, una estratificación del par que acabamos de definir es

\( (x,y)^*\equiv \{\{x_0\}_1,\{x_0,y_0\}_1\}_2 \)

de modo que el tipo de \( (x,y)^* \) es dos unidades superior al de \( x \) e \( y \). Más en general, un término \( (t_1,t_2)^* \) está estratificado si y sólo si los dos términos \( t_1 \) y \( t_2 \) admiten una estratificación conjunta que les asigne el mismo tipo, y entonces el tipo del par es dos unidades mayor que el tipo de sus componentes.

En pocas palabras: el par ordenado \( (x,y)^* \) aumenta dos unidades el tipo de sus componentes, mientras que, por la propia definición de estratificación, el par ordenado \( (x,y) \) tiene el mismo tipo que sus componentes. Esto se expresa diciendo que el término \( (x,y) \) es un par ordenado nivelado. Así pues:

Lo que afirma el axioma de los pares ordenados es que existe un par ordenado nivelado, es decir, un par ordenado que no aumenta el tipo de sus componentes. El par ordenado que se define en ZFC es un par ordenado no nivelado, luego no es equivalente en NFA al que hemos tomado como signo primitivo (no se puede hacer lo mismo con ambos).

Para ver las ventajas de contar con un par ordenado nivelado tendremos que esperar a hablar de funciones. Ahora bien, sucede que, pese a todo, aunque no hubiéramos tomado el par ordenado como signo primitivo, en NFA habríamos podido demostrar la existencia de pares ordenados nivelados (aquí hay ciertos matices que explicaré más adelante). El proceso habría sido el siguiente:

1) No suponemos la existencia de pares ordenados nivelados.

2) Definimos \( (x,y)\equiv \{\{x\},\{x,y\}\} \) y con este concepto de par ordenado (estratificado, pero no nivelado) definimos los conceptos de relación, aplicación, etc., desarrollamos la teoría de cardinales, números naturales, etc. (para lo cual hay que hacer varios malabarismos por culpa de la estratificación)

3) Cuando tenemos suficiente teoría a nuestra disposición, demostramos que existen pares ordenados nivelados.

4) Entonces volvemos atrás y decimos: todo lo que hemos hecho hasta ahora con pares ordenados no nivelados, se puede hacer también con pares ordenados nivelados, pero más fácil, así que redefinimos los conceptos de relación, aplicación, etc. para considerar que son los definidos a partir de pares nivelados, volvemos hasta el punto al que habíamos llegado y a partir de aquí continuamos la teoría con pares ordenados nivelados.

Así, el postular desde un principio la existencia de pares nivelados nos ahorra las estrecheces de trabajar con pares no nivelados y la necesidad de rehacer todo lo hecho una vez disponemos de los pares nivelados.

Una última observación a este respecto es que en NF (es decir, si suponemos que no hay átomos, se puede demostrar la existencia de pares nivelados sin usar el axioma de elección (a la fuerza, porque el axioma de elección es contradictorio en NF), mientras que en NFA se necesita el axioma de elección, pero esto es lógico que sea así: en NFA tenemos un conjunto de átomos del que no sabemos nada, así que, ¿cómo vamos a emparejar "finamente" unos objetos de los que no sabemos nada sin realizar elecciones carentes de criterio explícito? No podemos hacer elecciones explícitas sobre unos objetos de los que no sabemos absolutamente nada, por lo que el axioma de elección se vuelve imprescindible. En este sentido se podría decir que al postular la existencia de pares nivelados estamos postulando un caso particular del axioma de elección, pero eso es una verdad a medias. También se podría pensar que estamos diciendo algo sobre los átomos: no sabemos nada sobre ellos salvo que se pueden emparejar bien, lo cual es un requisito razonable.

Definimos

\( A\times B\equiv\{x\mid \exists ab(a\in A\land b\in B\land x=(a,b))\} \)

El lector que quiera seguir esto en serio debería plantearse si es capaz de justificar que la fórmula que define el producto está estratificada, así como comprobar que el producto es un término estratificado. ¿Cuál es su tipo en relación al de \( A \) y \( B \)?

Solución:

Spoiler

Una estratificación para la fórmula que define el producto es

\( \exists ab(a_0\in A_1\land b_0\in B_1\land x_0=(a_0,b_0)_0) \).

A su vez, una estratificación de producto es:

\( A\times B\equiv\{x_0\mid \exists ab(a_0\in A_1\land b_0\in B_1\land x_0=(a_0,b_0)_0)\}_1 \)

luego vemos que \( A\times B \) tiene el mismo tipo que \( A \) y \( B \). Más en general, si \( A \) y \( B \) son términos cualesquiera, no necesariamente meras variables, entonces el término \( A\times B \) está estratificado si y sólo si \( A \) y \( B \) admiten una estratificación conjunta que les asigne el mismo tipo, y entonces ese mismo tipo es también el tipo de \( A\times B \).

[cerrar]

Sólo a modo de ejercicio (sin que nos vaya a aprovechar para nada más adelante): Si definimos el producto cartesiano \( A\times B \) con pares ordenados no nivelados \( (a,b)^* \), ¿cuál sería ahora la relación entre el tipo de \( A\times B \) y el tipo de cada factor?

Respuesta:

Spoiler

El tipo de \( A\times B \) sería dos unidades superior a los tipos de \( A \) y \( B \)

[cerrar]

A veces, a la hora de definir subconjuntos de productos cartesianos, conviene emplear expresiones de la forma:

\( \{(a,b)\mid \phi(a,b,x_1,\ldots, x_n)\}\equiv \{x\mid \exists ab(x=(a,b)\land \phi(a,b,x_1,\ldots, x_n))\} \)

Observemos que esto es correcto siempre y cuando la fórmula \( \phi \) admita una estratificación que asigne el mismo tipo a las variables \( a \) y \( b \), pues esa es la condición necesaria y suficiente para que la fórmula \( \exists ab(x=(a,b)\land \phi(a,b,x_1,\ldots, x_n)) \) esté estratificada. En tal caso, el término que acabamos de definir está estratificado y su tipo es una unidad mayor que el de las variables \( a \) y \( b \).

Para terminar una cuestión "para sobresaliente":

Problema: La fórmula \( x\in A\lor x\in \{A\} \) no está estratificada. Entonces, dado un conjunto \( A \), ¿podemos afirmar que existe el conjunto \( A\cup\{A\} \)?

Solución:

Spoiler

Por definición:

\( A\cup \{A\}\equiv \{x\mid x\in A\lor x\in \{A\}\}\equiv Z\mid \forall x(x\in Z\leftrightarrow x\in A\lor x\in \{A\}) \).

Como la fórmula no está estratificada, no podemos usar el axioma de formación de conjuntos para asegurar que exista el conjunto \( A\cup \{A\} \). Sin embargo, esto es un ejemplo de que, aunque el axioma de formación de conjuntos sólo afirma que las fórmulas estratificadas definen conjuntos, eso no impide que una fórmula no estratificada pueda definir igualmente un conjunto. Para probar que así sucede en nuestro ejemplo consideramos la fórmula estratificada

\( x\in A\lor x\in B \)

y le aplicamos el axioma de formación de conjuntos, según el cual:

\( \forall AB\exists Z\forall x(x\in Z\leftrightarrow x\in A\lor x\in B) \).

Ahora, dado un conjunto \( A \), tenemos que \( \{A\} \) es otro conjunto, luego la afirmación anterior, que vale para todo \( A \) y para todo \( B \), vale en particular para \( A \) y \( \{A\} \), es decir:

\( \exists Z\forall x(x\in Z\leftrightarrow x\in A\lor x\in \{A\}) \),

luego, al fin y al cabo, sí que existe el conjunto \( A\cup \{A\} \).

Ahora bien, esto no significa que, cuando en el mensaje anterior hemos afirmado que existe la unión de conjuntos, dicha afirmación no fuera totalmente general, y que en realidad haga falta considerar aparte casos como éste. He hecho estos razonamientos para mostrar explícitamente un caso de fórmula no estratificada que define un conjunto, pero no hacía falta razonar así. El razonamiento directo es el siguiente:

1) Definimos \( A\cup B \equiv \{x\mid x\in A\lor x\in B\} \).

2) Puesto que la fórmula \( x\in A\lor x\in B \) (donde \( x, A, B \) son variables) está estratificada, el axioma de formación de conjuntos (junto con el de extensionalidad, que da la unicidad) nos asegura que la definición anterior es correcta, en el sentido de que

\( \forall AB\forall x(x\in A\cup B\leftrightarrow x\in A\lor x\in B) \).

Esto, así de general, es un teorema de NFA, y la respuesta al problema planteado se sigue inmediatamente de aquí: la respuesta es afirmativa porque basta hacer \( B=\{A\} \) en este teorema.

En resumen: cuando demostramos que existe la unión de conjuntos (o cualquier otro concepto a partir del axioma de formación de conjuntos) demostramos que existe para cualquier valor de los parámetros \( A \) y \( B \), luego en particular existe cuando sustituimos \( A \) y \( B \) por términos que no admiten una estratificación conjunta, como \( A \) y \( \{A\} \), de modo que eso sólo se traduce en que el término \( A\cup\{A\} \) no está estratificado, pero no en que no exista la unión, cuya existencia tenemos garantizada para todo par de conjuntos.

[cerrar]

[Carlos Ivorra]

En este mensaje revisaremos los conceptos básicos relacionados con funciones. Supongo que todo el mundo estará familiarizado con ellos. La cuestión es simplemente comprobar que están estratificados. Empezamos por la definición misma de aplicación entre dos conjuntos:

\( f:A\longrightarrow B\equiv f\subset A\times B\land \forall abb'((a,b)\in f\land (a,b')\in f\rightarrow b=b') \)

\( \land \forall a\in A\exists b\in B\ (a,b)\in f \)

Notemos que aunque la \( f \) sea minúscula, es un conjunto, como se deduce, por ejemplo, de la inclusión \( f\subset A\times B \).

Estratificación de la definición

\( f_1\subset A_1\times B_1\land \forall abb'((a_0,b_0)_0\in f_1\land (a_0,b'_0)\in f_1\rightarrow b_0=b'_0) \)

\( \land \forall a_0\in A_1\exists b_0\in B_1\ (a_0,b_0)_0\in f_1 \)

[cerrar]

Al estratificar \( f: A\longrightarrow B \) vemos que las tres variables \( f, A, B \) tienen que tener asignado el mismo tipo. Más en general, si en vez de variables son términos cualesquiera, la fórmula estará estratificada si y sólo si los tres términos admiten una estratificación conjunta que asigne a los tres el mismo tipo.

Ahora hemos de fijarnos en la expresión \( f(x) \). En principio tiene sentido cuando \( f \) es una función y \( x \) está en su dominio, pero para estratificarla hemos de preguntarnos: ¿cómo se define exactamente? La respuesta es que se trata de una descripción:

\( f(x)\equiv y\mid (x,y)\in f \).

Para estratificarla tenemos en cuenta que el tipo de la descripción debe coincidir con el de la variable \( y \), luego es: \( (y_0\mid (x_0,y_0)_0\in f_1)_0 \). Más en general:

El término \( f(x) \) (cuando tiene sentido) está estratificado y tiene el mismo tipo que \( x \) y una unidad menos que el tipo de \( f \).

A menudo es frecuente definir aplicaciones diciendo: "Sea \( f:A\longrightarrow B \) la aplicación dada por \( f(x)=t(x,x_1,\ldots, x_n) \)", donde \( t \) es un término que depende de \( x \) y tal vez de otros parámetros. Esto equivale a que

\( f\equiv \{(x,y)\mid x\in A\land y\in B\land y=t(x,x_1,\ldots, x_n)\} \)

Y vemos que la definición está estratificada si y sólo si el término \( t(x,x_1,\ldots, x_n) \) admite una estratificación que le asigna el mismo tipo que a la variable \( x \).

El principio general es:

Para que la definición de una aplicación \( f \) esté estratificada su definición debe asignar a cada elemento de su dominio el mismo tipo que a su imagen, y éstos han de ser una unidad inferior al de \( f \).

Se trata de un principio general que podríamos concretar en muchos resultados generales concretos para definir aplicaciones, pero no merece la pena. Por ejemplo, si definimos

\( f: A\times B\longrightarrow B\times A \) mediante \( f(a,b)=(b,a) \), podemos decir que la definición es correcta porque podemos estratificar \( (a_0,b_0)_0 \) y \( (b_0,a_0)_0 \) ambos con tipo \( 0 \) (y entonces \( f \) tiene tipo \( 1 \)). Esta situación no se ajusta exactamente al caso general precedente (porque la función tiene dos variables), pero la comprobación es similar. En la práctica, si alguien quiere comprobar la estratificación de una función con detalle, lo mejor es que la escriba como conjunto, por ejemplo:

\( f\equiv \{x\mid \exists ab(a\in A\land b\in B\land x = ((a,b),(b,a)))\} \)

y es fácil ver que la fórmula que define a \( f \) está estratificada (en esencia por que se cumple el principio general: cada par tiene el mismo tipo que su imagen).

Dejamos al lector la comprobación de que si escribe explícitamente las definiciones de

\( f:A\longrightarrow B \) inyectiva, \( f:A\longrightarrow B \) suprayectiva y \( f:A\longrightarrow B \) biyectiva,

observará que todas ellas están estratificadas y que las tres variables tienen el mismo tipo.

Los conceptos de dominio y rango los usaremos normalmente con funciones, pero no hay razón para complicar la definición exigiendo esto, sino que pueden definirse para conjuntos arbitrarios (y, en realidad, también es útil tener las definiciones aplicables a relaciones cualesquiera):

\( \mathcal DR\equiv \{x\mid \exists y\ (x,y)\in R\},\qquad \mathcal RR\equiv \{y\mid \exists x\ (x,y)\in R\} \).

Igualmente definimos el conjunto (o relación o función) inverso: \( R^{-1}\equiv \{(a,b)\mid (b,a)\in R\} \).

Finalmente:

\( f\circ g\equiv\{(a,c)\mid \exists b\ ((a,b)\in g\land (b,c)\in f)\} \)

\( f[X]\equiv \{y\mid \exists x\in X\ (x,y)\in f\},\qquad f^{-1}[Y]\equiv \{x\mid \exists y\in Y\ (x,y)\in f\} \)

\( f|_X\equiv \{(a,b)\mid a\in X\land (a,b)\in f\} \).

El lector que quiera cerciorarse de que domina "el arte de la estratificación" debería comprobar que todos estos conceptos están estratificados y calcular la relación entre los tipos de sus variables. La tabla siguiente recapitula todos los conceptos que hemos introducido hasta ahora con los datos relevantes respecto a estratificación:

\( \begin{array}{|ccc||ccc|}
\text{Expresión}&\text{Condición}&\text{Variación}&\text{Expresión}&\text{Condición}&\text{Variación}\\
\hline
A\subset B&t(A)=t(B)&&A\times B&t(A)=t(B)&0\\
A\cup B&t(A)=t(B)&0&f:A\longrightarrow B&t(f)=t(A)=t(B)&\\
A\cap B&t(A)=t(B)&0&\mathcal DR&&0\\
\overline A&&0&\mathcal RR&&0\\
A\setminus B&t(A)=t(B)&0&R^{-1}&&0\\
\bigcup A&&-1&f\circ g&t(f)=t(g)&0\\
\bigcap A&&-1&f(x)&t(f)=t(x)+1&-1/0\\
\mathcal PA&&1&f[X]&t(f)=t(X)&0\\
\{x,y\}&t(x)=t(y)&1&f^{-1}[Y]&t(f)=t(Y)&0\\
(x,y)&t(x)=t(y)&0&f|_X&t(f)=t(X)&0\\
\hline
\end{array} \)

Por ejemplo, la segunda línea de la izquierda dice que la condición para que \( A\cup B \) esté estratificado es que el tipo de \( A \) sea igual al tipo de \( B \), y que en tal caso la unión tiene el mismo tipo que \( A \) y \( B \) (la unión no varía el tipo).

En cambio, la sexta línea dice que el tipo de \( \bigcup A \) es una unidad inferior al tipo de \( A \) (la gran unión disminuye el tipo una unidad).

La línea de \( f(x) \) dice que, para que el término esté estratificado el tipo de \( f \) debe ser una unidad mayor que el de \( x \) y que, en tal caso, el término \( f(x) \) tiene tipo una unidad inferior al de \( f \) pero igual al de \( x \) (variación \( -1 \) respecto de \( f \) y \( 0 \) respecto de \( x \)).


Terminamos con una observación sobre qué pasaría si quisiéramos trabajar con aplicaciones definidas con pares no nivelados.

Para definir la suma de cardinales hay que probar que, dados dos conjuntos \( A \) y \( B \), existen siempre dos conjuntos disjuntos del mismo cardinal. La forma típica de asegurar que obtenemos conjuntos disjuntos es pasar a los conjuntos \( A\times\{0\} \) y \( B\times\{1\} \). Dejando de lado la definición de \( 0 \) y \( 1 \), ¿cómo probamos que \( A \) tiene el mismo cardinal que \( A\times\{u\} \), para cualquier objeto \( u \)?. Lo natural es considerar la biyección \( f: A\longrightarrow A\times \{u\} \) dada por \( f(a)=(a,u) \). Esta definición es correcta según lo que hemos visto porque podemos estratificar el par \( (a_0,u_0)_0 \) de modo que tenga el mismo tipo que \( a \) (es decir, de modo que \( a \) y \( f(a)=(a,0) \) tengan el mismo tipo). Así pues, todo va bien.

En cambio, si quisiéramos considerar el par ordenado \( (a,u) \) usual en ZFC, que tiene tipo dos unidades mayor que el tipo de \( a \), resulta que la aplicación \( a\mapsto (a,u) \) no está bien definida (la definición no está estratificada y, por consiguiente, no podemos asegurar que exista el conjunto (la función) \( f \) que pretendemos definir). Eso tampoco significa que no exista, pero el hecho es que tenemos un problema. Esta clase de problemas es la que nos evitamos al trabajar con pares nivelados.

[Óscar Matzerath]

Hola,

Solo quiero felicitarte por el trabajo realizado y animarte a seguir, ya que a mí me interesa bastante el tema y lo voy a seguir con atención. Si ya te animaras a hacer una exposición no solo de la teoría de conjuntos en sí, sino de aspectos de la teoría de modelos de NFU (o NFA), sería genial.

Saludos

[Carlos Ivorra]

Hola,

Solo quiero felicitarte por el trabajo realizado y animarte a seguir, ya que a mí me interesa bastante el tema y lo voy a seguir con atención. Si ya te animaras a hacer una exposición no solo de la teoría de conjuntos en sí, sino de aspectos de la teoría de modelos de NFU (o NFA), sería genial.

Saludos

Gracias, Óscar. Cualquier comentario será bienvenido. En cuanto a lo de los modelos, hay un "robot" pululando por ahí que ha escrito un abstract para mi exposición y ya ha puesto que voy a hablar de la consistencia de NFA, así que ya me había hecho a la idea de hablar de eso. Con mayor razón si hay interés.

[Carlos Ivorra]

En este mensaje expondré los elementos básicos de la teoría de cardinales en NFA como base para construir los números naturales.

La definición básica es la siguiente:

Definición: Diremos que dos conjuntos \( X \) e \( Y \) son equipotentes si existe una aplicación biyectiva \( f:X\longrightarrow Y \). En signos:

\( X\sim Y\equiv \exists f\ f: X\longrightarrow Y \) biyectiva.

Observemos que esta fórmula está estratificada y en ella las variables \( X \) e \( Y \) tienen el mismo tipo.

Las propiedades básicas de la equipotencia son:

1) \( \forall X\ X\sim X \)

2) \( \forall XY(X\sim Y\rightarrow Y\sim X) \)

3) \( \forall XYZ(X\sim Y\land Y\sim Z\rightarrow X\sim Z) \).

Las tres se demuestran sin dificultad. No pongo las pruebas, pero si algún lector tiene dificultades en demostrarlas por sí mismo que me lo diga y las incluiré. En definitiva, estas propiedades afirman que la equipotencia es una relación de equivalencia sobre el conjunto \( C \) de todos los conjuntos.

Definición: Llamaremos cardinal de un conjunto \( X \) al conjunto de todos los conjuntos equipotentes con él, es decir:

\( |X|\equiv \{Y\mid Y\sim X\} \).

Observamos que el término \( |X| \) está estratificado y que su tipo es una unidad superior al de la variable \( X \). Ahora podemos probar la relación fundamental:

Teorema: Dos conjuntos son equipotentes si y sólo si tienen el mismo cardinal.

Demostración

Supongamos que \( X\sim Y \), y hemos de probar que \( |X|=|Y| \). Para ello tomamos un objeto \( u\in |X| \), que será, de hecho, un conjunto \( u\sim X \). Por la transitividad de la equipotencia, \( u\sim Y \), luego \( u\in |Y| \). Igualmente se prueba que si \( u\in |Y| \) entonces \( u\in |X| \), luego \( |X|=|Y| \).

Recíprocamente, si \( |X|=|Y| \), entonces, como \( X\sim X \), tenemos que \( X\in |X| \), luego \( X\in |Y| \), luego \( X\sim Y \).

[cerrar]

Definición: Llamaremos \( K \) al conjunto de todos los cardinales, es decir:

\( K\equiv \{\kappa\mid \exists X\ \kappa = |X|\} \)

Observemos que la fórmula que define a \( K \) está estratificada, luego \( K \) es un conjunto bien definido.

Vamos a definir una relación de orden en \( K \).

Definición: Diremos que un conjunto \( X \) es minuspotente a un conjunto \( Y \) si existe una aplicación \( f:X\longrightarrow Y \) inyectiva. Equivalentemente:

\( X\preceq Y\equiv \exists f\ f:X\longrightarrow Y \) inyectiva.

Así vemos que esta fórmula está estratificada con las dos variables del mismo tipo.

Definición: Diremos que un cardinal \( \kappa \) es menor o igual que un cardinal \( \mu \) si existen conjuntos \( X \) e \( Y \) tales que \( |X|=\kappa, |Y|=\mu \) y \( X\preceq Y \).

Más precisamente, podemos definir \( \leq \) como el siguiente subconjunto de \( K\times K \):

\( \leq \ \equiv \{(\kappa,\mu)\mid \exists XY(|X|=\kappa\land |Y|=\mu\land X\preceq Y)\} \)

La definición es correcta porque la fórmula está estratificada y asigna el mismo tipo a las variables \( \kappa \) y \( \mu \).

De este modo, si escribimos \( \kappa\leq \mu\equiv (\kappa,\mu)\in\ \leq \), tenemos que

\( \kappa\leq \mu\leftrightarrow \exists XY(|X|=\kappa\land |Y|=\mu\land X\preceq Y) \).

Teorema: Para todo par de conjuntos \( X \), \( Y \) se cumple que \( X\preceq Y\leftrightarrow |X|\leq |Y| \).

Demostración

Si \( X\preceq Y \) es inmediato que \( |X|\leq |Y| \), por la propia definición. El recíproco requiere cierto cálculo. En efecto, si suponemos que \( |X|\leq |Y| \), esto significa que existen conjuntos \( X' \) e \( Y' \), no necesariamente los que teníamos, tales que \( X'\preceq Y' \).

Ahora bien, entonces tenemos aplicaciones \( f: X\longrightarrow X' \) biyectiva, \( f': Y\longrightarrow Y' \) biyectiva y \( g': X'\longrightarrow Y' \) inyectiva. Consideramos entonces \( g=f'^{-1}\circ g'\circ f: X\longrightarrow Y \), y es fácil ver que es inyectiva. Por lo tanto \( X\preceq Y \).

[cerrar]

En particular tenemos que si \( X\subset Y \) entonces \( |X|\leq |Y| \), pues podemos considerar la aplicación inclusión \( X\longrightarrow Y \) dada por \( x\mapsto x \).

La relación que acabamos de definir es una relación de orden, es decir, cumple las tres propiedades siguientes:

Teorema:

1) \( \forall \kappa\in K\ \kappa\leq \kappa \)

2) \( \forall \kappa\mu\in K\ (\kappa\leq \mu\land \mu\leq \kappa\rightarrow \kappa=\mu \)

3) \( \forall\kappa\mu\nu\in K(\kappa\leq \mu\land \mu\leq \nu\rightarrow \kappa\leq \nu) \).

Las propiedades 1) y 3) son muy sencillas y no pondré la demostración. (Pero insisto en que si alguien quiere que demuestre cualquier cosa que me salto sólo tiene que pedirlo. Me salto cosas por aligerar un poco, pero lo que haga falta probar, se prueba. Incluso si alguien quiere completar el hilo añadiendo pruebas de cosas no demostradas, yo las revisaré con mucho gusto.)

La propiedad 2) es el teorema de Cantor-Bernstein, y se prueba exactamente igual que en ZFC, pero incluiré la prueba por si alguien tiene curiosidad y no conoce la demostración. Necesita un teorema previo:

Teorema de punto fijo: Sea \( X \) un conjunto y \( F:\mathcal PX\longrightarrow \mathcal PX \) una aplicación con la propiedad de que si \( A\subset B\subset X \) entonces \( F(A)\subset F(B) \).  Entonces existe un \( Z\in \mathcal PX \) tal que \( F(Z)=Z \).

Demostración

Sea \( S=\{A\mid A\in \mathcal PX\land F(A)\subset A\} \). Como siempre, es crucial comprobar que las definiciones son correctas, es decir, que las propiedades están estratificadas, pero en este caso está claro, pues \( F(A) \) tiene el mismo tipo que \( A \), como requiere la incusión.

Ahora observamos que \( S\neq \emptyset \), porque claramente \( X\in S \). Definimos \( Z=\bigcap S \), que está contenido en todos los elementos de \( S \), en particular en \( X \), luego \( Z\in \mathcal PX \). (Si \( S \) fuera vacío, sería \( Z=V \).) Vamos a probar que \( Z \) cumple lo pedido.

Si \( A\in S \), entonces, como \( Z \) está contenido en todos los elementos de \( S \), tenemos que \( Z\subset A \), luego, por la hipótesis sobre \( F \) y por definición de \( S \), tenemos que \( F(Z)\subset F(A)\subset A \).

Con esto hemos probado que \( F(Z) \) está contenido en todos los elementos de \( S \), luego está contenido en su intersección, es decir, \( F(Z)\subset Z \).

De nuevo por la hipótesis sobre \( F \) tenemos que \( F(F(Z))\subset F(Z) \), y por definición de \( S \) tenemos que \( F(Z)\in S \), luego \( Z\subset F(Z) \), ya que \( Z \) (la intersección de \( S \)) está contenida en todos los elementos de \( S \).

La doble inclusión prueba que \( F(Z)=Z \).

[cerrar]

Teorema de Cantor Bernstein Dados dos conjuntos \( X \) e \( Y \), si \( X\preceq Y \) e \( Y\preceq X \), entonces \( X\sim Y \).

Demostración

La hipótesis es que tenemos aplicaciones \( f:X\longrightarrow Y,\ g: Y\longrightarrow X \) inyectivas. Definimos
\( F:\mathcal PX\longrightarrow \mathcal PX \) mediante \( F(A)=X\setminus g[Y\setminus f[A]] \).

Lo único que hemos de hacer de más por trabajar en NFA en lugar de en ZFC es comprobar que la definición de \( F \) es correcta, lo que en este caso significa que el término \( X\setminus g[Y\setminus f[A]] \) está estratificado con el mismo tipo que \( A \), lo cual es cierto, pues hemos visto que todos los conceptos involucrados conservan el tipo.

Ahora comprobamos que \( F \) cumple las hipótesis del teorema anterior: Si \( A\subset B\subset X \), entonces \( f[A]\subset f[B]\rightarrow  Y\setminus f[B]\subset Y\setminus f[A]\rightarrow g[Y\setminus f[B]]\subset g[Y\setminus f[A]] \)

\( \rightarrow X\setminus g[Y\setminus f[A]]\subset X\setminus g[Y\setminus f[B]]\rightarrow F(A)\subset F(B) \).

Así pues, podemos aplicar el teorema anterior para concluir que existe un \( Z\in \mathcal PX \) tal que \( Z=X\setminus g[Y\setminus f[Z]] \) o, equivalentemente, \( X\setminus Z=g[Y\setminus f[Z]] \).

Así tenemos que \( f|_Z: Z\longrightarrow f[Z] \) biyectiva y \( g|_{Y\setminus f[Z]}:Y\setminus f[Z]\longrightarrow X\setminus Z \) biyectiva. Si llamamos \( h=(g|_{Y\setminus f[Z]})^{-1}: X\setminus Z\longrightarrow Y\setminus f[Z] \) biyectiva, concluimos que

\( f|_Z\cup h: X\longrightarrow Y \) biyectiva.

(Notemos que \( f|_Z\cup h \) es la aplicación que actúa como \( f \) sobre \( Z \) y como \( h \) sobre \( X\setminus Z \)).

Esto prueba que \( X\sim Y \).

[cerrar]

La propiedad antisimétrica de la relación de orden entre cardinales (propiedad 2) es simplemente el teorema de Cantor-Bernstein en términos de cardinales en lugar de en términos de conjuntos.

En estos momentos no podemos demostrar que \( \forall \kappa\mu\in K(\kappa\leq \mu\lor \mu\leq \kappa) \) porque esta propiedad requiere el axioma de elección, y todavía no lo hemos incorporado a la teoría. Por otra parte, tampoco necesitamos esto para nada, de momento.

Por ahora sólo podemos añadir lo siguiente a las propiedades de la relación de orden:

Teorema: Existe un mínimo cardinal \( 0 = |\emptyset| \) y un máximo cardinal \( \kappa_0=|V| \).

Demostración

Que \( 0=|\emptyset| \) sea el mínimo cardinal significa que si \( \kappa \) es cualquier cardinal entonces \( 0\leq \kappa \), lo que a su vez significa que si \( |X|=\kappa \) entonces existe una aplicación inyectiva \( f: \emptyset\longrightarrow X \).

Sucede que \( f=\emptyset \) cumple lo pedido, y probarlo es el típico ejercicio de "cinismo" que podemos llamar "lógica del conjunto vacío": \( \emptyset \) es una aplicación de \( \emptyset \) en \( X \), porque no hay ningún elemento de \( \emptyset \) que no sea un par ordenado con primera componente en \( \emptyset \) y segunda componente en \( X \) (¿cómo lo iba a haber, si en \( \emtyset \) no hay nada?) y no hay ningún elemento en \( \emptyset \) que no tenga imagen en \( X \) (¿cómo lo iba a haber?).

Además \( \emptyset \) es una aplicación inyectiva, pues no hay dos elementos en \( \emptyset \) con la misma imagen en \( X \) ¿cómo los iba a haber?. Por dudoso que esto le pueda parecer a alguien: esto es lógica. 

Observemos que en particular \( \emptyset:\emptyset \longrightarrow \emptyset \) biyectiva, pues no hay ningún elemento en \( \emptyset \) que carezca de antiimagen (¿cómo podría haberlo?). Más aún,  si \( f:\emptyset \longrightarrow X \) biyectiva, necesariamente \( X=\emptyset \). En efecto, si hubiera un elemento \( u\in X \), debería tener una antiimagen en \( \emptyset \), lo cual es imposible, luego \( X=\emptyset \).

Esto significa que \( 0=\{\emptyset\} \) (el conjunto de todos los conjuntos equipotentes a \( \emptyset \) se reduce al conjunto vacío).

Por otro lado, dado un cardinal \( \kappa \) cualquiera, tomamos un conjunto tal que \( |X|=\kappa \). Puesto que \( X\subset V \), la inclusión \( i: X\longrightarrow V \) dada por \( x\mapsto x \) es claramente inyectiva, luego \( \kappa = |X|\leq |V|=\kappa_0 \).

Esto prueba que \( \kappa_0 \) es el mayor de todos los cardinales.

[cerrar]

Para definir la suma de cardinales observamos primero lo siguiente:

Teorema: Dados dos cardinales \( \kappa \) y \( \mu \) existen conjuntos tales que \( |X|=\kappa, |Y|=\mu \) y \( X\cap Y=\emptyset \).

Demostración

Tomemos conjuntos tales que \( |X'|=\kappa \) y \( |Y'|=\mu \). Existen por la propia definición de cardinal, pero no podemos asegurar que sean disjuntos. Para obtener conjuntos disjuntos tomamos dos objetos cualesquiera tales que \( u\neq v \). Por ejemplo, \( u=\emptyset \), \( v=\{\emptyset\} \) y definimos

\( X=X'\times\{u\} \), \( Y=Y'\times \{v\} \).

Así es inmediato que \( X\cap Y=\emptyset \), pues un elemento de la intersección debería ser un par ordenado con segunda componente igual a \( u \) y a \( v \) a la vez. Sólo hemos de probar que \( |X|=|X'| \) y que \( |Y|=|Y'| \). Lo probamos para \( X \), para lo cual basta construir la aplicación \( f: X\longrightarrow X\times \{u\} \) mediante \( f(x)=(x,u) \).

Es crucial comprobar que la definición es correcta porque la imagen \( (x,u) \) tiene el mismo tipo que \( x \) (y aquí es crucial que contamos con un par ordenado nivelado). No cuesta nada probar que \( f \) es biyectiva, luego en efecto, \( |X|=|X'| \), e igualmente se razona con \( Y \).

[cerrar]

Definición: Llamaremos suma de cardinales a la aplicación \( +:K\times K\longrightarrow K \) definida como sigue: dados dos cardinales \( \kappa \) y \( \mu \), tomamos conjuntos disjuntos tales que \( |X|=\kappa \) y \( |Y|=\mu \) y llamamos \( \kappa+\mu=|X\cup Y| \).

Más técnicamente:

\( +\equiv \{((\kappa,\mu),\nu))\mid \exists XY(\kappa=|X|\land \mu=|Y|\land X\cap Y=\emptyset\land \nu=|X\cup Y|)\} \).

Es evidente que existe el conjunto \( + \) (la definición está estratificada), pero no es evidente que se trata realmente de una aplicación \( +: K\times K\longrightarrow K \). Ciertamente, es un conjunto de pares ordenados con primera componente en \( K\times K \) y segunda componente en \( K \), pero hemos de probar que cada par de cardinales \( (\kappa, \mu) \) tiene una única imagen \( \nu \).

Demostración

Si \( ((\kappa, \mu),\nu)\in + \) y también \( ((\kappa, \mu), \nu')\in + \), esto significa que, por una parte, tenemos conjuntos  tales que \( |X|=\kappa, |Y|=\mu, X\cap Y=\emptyset, |X\cup Y|=\nu \) y por otra parte tenemos conjuntos tales que \( |X'|=\kappa, |Y'|=\mu, X'\cap Y'=\emptyset, |X'\cup Y'|=\nu' \).

Hemos de probar que \( \nu=\nu' \). Tenemos biyecciones \( f: X\longrightarrow X' \) y \( g: Y\longrightarrow Y' \), y el hecho de que los conjuntos sean disjuntos implica que \( (f\cup g): X\cup Y\longrightarrow (X'\cup Y') \) biyectiva. Por lo tanto \( \mu = |X\cup Y|=|X'\cup Y'|=\nu \).

[cerrar]

En definitiva, tenemos el teorema siguiente:

Teorema: Si \( X \) e \( Y \) son conjuntos disjuntos, entonces \( |X\cup Y|=|X|+|Y| \).

Ahora es fácil probar que la suma de cardinales es asociativa, conmutativa y que tiene como elemento neutro al \( 0 \). Dejamos todos estos hechos como ejercicios.

No estamos en condiciones de calcular sumas explícitamente, pero hay dos muy sencillas: \( 0+0=0 \) y \( \kappa_0+\kappa_0=\kappa_0 \).

El producto de cardinales se define sin dificultad:

Definición: Definimos el producto de cardinales como la aplicación \( \cdot: K\times K\longrightarrow K \) que se calcula como sigue: tomamos conjuntos tales que \( |X|=\kappa \) y \( |Y|=\mu \) y entonces \( \kappa\cdot \mu=|X\times Y| \).

Explícitamente:

\( \cdot \equiv \{((\kappa,\mu),\nu)\mid \exists XY(\kappa=|X|\land \mu=|Y|\land \nu=|X\times Y|)\} \)

Como en el caso de la suma, es inmediato que la definición está estratificada, pero hay que probar que este producto es realmente una aplicación de \( K\times K \) en \( K \). El argumento sigue exactamente el mismo esquema que para la suma, así que lo omitimos.

De este modo tenemos:

Teorema: Para todo par de conjuntos, se cumple que \( |X\times Y| = |X|\cdot |Y| \).

Dejamos también como ejercicio las propiedades obvias: el producto de cardinales es asociativo y conmutativo, además \( \forall \kappa\in K\ \kappa\cdot 0=0 \) y el producto tiene como elemento neutro al cardinal

\( 1= \{X\mid \exists u\ X= \{u\}\} \).

Ejercicio: Probar que \( 1 \) es el menor cardinal mayor que \( 0 \).

Solución

Sea \( \kappa>0 \). Hemos de probar que \( 1\leq \kappa \). Sea \( |X|=\kappa \). No puede ser \( X=\emptyset \), pues entonces \( \kappa =|X|=0 \). Por lo tanto, existe un objeto \( u\in X \), luego \( \{u\}\subset X \), luego \( 1=|\{u\}|\leq |X|=\kappa \).

[cerrar]

En el próximo mensaje construiremos los números naturales.

[Carlos Ivorra]

Con lo visto hasta ahora es fácil construir los números naturales en NFA:

Tenemos definido el conjunto \( K \) de todos los cardinales y, en él, la suma y el producto de cardinales, así como los cardinales \( 0=|\emptyset| \) y \( 1=\{X\mid \exists u\ X=\{u\}\} \).

Así podemos definir el conjunto de los conjuntos inductivos como:

\( \text{Ind}\equiv \{A\mid A\subset K\land 0\in A\land \forall n\in A\ n+1\in A\} \)

Es claro que la definición está estratificada, pero, no obstante, haremos algunos comentarios al respecto:

Spoiler

Una estratificación es:

\( A_1\subset K_1\land 0_0\in A_1\land \forall n_0\in A_1\ (n_0+_11_0)_0\in A_1 \)

Aquí hemos tenido en cuenta varias cosas:

1) Los términos que no tienen variables libres, como \( K, 0, 1,+ \), si están estratificados, admiten estratificaciones en las que el tipo asignado sea cualquiera que nos convenga, porque siempre es posible sumar un mismo número entero a todos los tipos y la estratificación se conserva.

2) Notemos que \( + \) es una aplicación (en particular es un conjunto), de modo que \( n+1\equiv +(n,1)\equiv (n,1)\in + \) y sabemos que una expresión de este tipo está estratificada de modo que la imagen \( n+1 \) tiene el mismo tipo que el argumento \( (n,1) \), que a su vez tiene el mismo tipo que las dos componentes.

[cerrar]

Definición: Llamaremos conjunto de los números naturales a \( \mathbb{N}=\bigcap\text{Ind} \), es decir, a la intersección de todos los conjuntos inductivos.

Observamos que trivialmente \( K\in \text{Ind} \) y, como \( \mathbb{N} \) está contenido en todos los elementos de \( \text{Ind} \), concluimos que \( \mathbb{N}\subset K \), es decir, que los números naturales son cardinales.

Teorema (Axiomas de Peano) Se cumple:

1) \( 0\in \mathbb{N} \).

2) \( \forall n\in \mathbb{N}\ n+1\in \mathbb{N} \).

3) \( \forall mn\in \mathbb{N}(m+1=n+1\rightarrow m=n). \)

4) \( \forall n\in \mathbb{N}\ n+1\neq 0 \).

5) \( \forall X(X\subset \mathbb{N}\land 0\in X\land \forall n\in X\ n+1\in X\rightarrow X=\mathbb{N}) \).

Demostración

1) Como \( 0 \) pertenece a todo conjunto inductivo, también pertenece a la intersección de todos los conjuntos inductivos, es decir, a \( \mathbb{N} \).

2) Si \( n\in \mathbb{N} \) y \( A\in \text{Ind} \), entonces \( n\in A \) por definición de \( \mathbb{R} \), luego \( n+1\in A \) por definición de \( \text{Ind} \), luego \( n+1\in \mathbb{N} \) por definición de \( \mathbb{N} \).

3) Por definición de suma podemos tomar conjuntos \( A, B, C, D \) tales que \( |A|=m, |B|=n, |C|=|D|=1 \) y \( A\cap C=B\cap D=\emptyset \). Por definición de \( 1 \) tenemos que \( C=\{u\} \), \( D=\{v\} \), para ciertos objetos \( u \) y \( v \).

Entonces \( m+1 = |A\cup\{u\} \) y \( n+1=|B\cup\{v\} \) y por hipótesis existe una biyección \( f:A\cup \{u\}\longrightarrow B\cup \{v\} \). Si \( f(u)=v \), entonces \( f \) se restringe a una biyección \( A\longrightarrow B \) que prueba que \( m=|A|=|B|=n \).

En caso contrario sea \( f(u)=u'\in B \) y sea \( f^{-1}(v)=v'\in A \). Es claro que \( g=(f\setminus\{(u,u'),(v',v)\})\cup \{(v',u')\} \) es una biyección \( g:A\longrightarrow B \) y concluimos igualmente.

4) Como antes, podemos tomar \( |A|=n \) y un objeto \( u \) de modo que \( n+1=|A\cup\{u\}| \). Como \( A\cup\{u\}\neq\emptyset \), tenemos que \( n+1\neq 0 \).

5) La hipótesis es que \( X\subset \mathbb{N} \) y \( X\in \text{Ind} \), pero lo segundo implica que \( \mathbb{N}\subset X \) por definición de \( \mathbb{N} \).

[cerrar]

El quinto axioma de Peano es el principio de inducción, pero hay que ser cauto a la hora de aplicarlo, pues demostrar por inducción que todos los números naturales cumplen una propiedad \( \phi(n) \) consiste en aplicar el quinto axioma de Peano al conjunto \( X=\{n\mid n\in \mathbb{N}\land \phi(n)\} \), y para que esto sea correcto la fórmula \( \phi \) tiene que estar estratificada.

Como ejemplo de prueba por inducción veamos que la función siguiente \( S:\mathbb{N}\longrightarrow \mathbb{N}\setminus\{0\} \) es biyectiva. Sabemos que es inyectiva por el tercer axioma de Peano. Para probar la suprayectividad (es decir, que todo natural no nulo es el siguiente de otro número natural) consideramos el conjunto (bien definido)

\( X=\{n\mid n\in \mathbb{N}\land (n=0\lor \exists m\in \mathbb{N}\ n=m+1\} \)

y se prueba trivialmente que cumple las condiciones del principio de inducción, luego \( X=\mathbb{N} \) y esto implica lo dicho.

Veamos algunas propiedades más:

Teorema: Si \( n\in \mathbb{N} \), entonces \( n+1 \) es el menor cardinal mayor que \( \mathbb{N} \).

Demostración

Obviamente \( n\leq n+1 \). Que la desigualdad es estricta se prueba por inducción sobre el conjunto

\( X=\{n\mid n\in \mathbb{N}\land n<n+1\} \)

Tenemos que \( 0\in X \) por el cuarto axioma de Peano y, si \( n\in X \), entonces \( n<n+1 \) y no puede ser \( n+1=n+1+1 \) por el tercer axioma de Peano, luego \( n+1\in X \).

Esto prueba que \( n+1 \) es un cardinal mayor que \( n \). Para probar que es el mínimo tomamos un cardinal \( \kappa \) tal que \( n<\kappa \) y probamos que \( n+1\leq \kappa \).

Por definición de suma existe un conjunto \( |A|=n \) y un objeto \( u\notin A \) de modo que \( n+1=|A\cup\{u\}| \). Sea \( \kappa=|B| \). Por hipótesis existe una aplicación \( f:A\longrightarrow B \) inyectiva que no puede ser biyectiva, pues en tal caso sería \( n=\kappa \). Sea \( u'\in B\setminus f[A] \). Entonces \( g=f\cup\{(u,u')\} \) cumple que \( f':A\cup\{u\}\longrightarrow B \) inyectiva, luego \( n+1\leq \kappa \).

[cerrar]

Más precisamente, los números naturales son los primeros cardinales en el sentido siguiente:

Teorema: Si \( \kappa\in K \) y \( n\in \mathbb{N} \), entonces \( n\leq \kappa \) o \( \kappa\leq n \), y en el segundo caso \( \kappa\in \mathbb{N} \).

Demostración

Por inducción sobre \( n \) (dejo como ejercicio comprobar que el conjunto correspondiente está bien definido).

Si \( n=0 \) sabemos que \( 0\leq \kappa \).

Supongamos que el teorema vale para \( n \), es decir, que \( n\leq \kappa \) o bien \( \kappa\leq n\land \kappa\in \mathbb{N} \).

En el segundo caso, obviamente \( \kappa\leq n+1\land \kappa\in \mathbb{N} \).

En el primer caso, o bien \( n=\kappa \), en cuyo caso \( \kappa\leq n+1\land \kappa\in \mathbb{N} \), o bien \( n<\kappa \), en cuyo caso \( n+1\leq \kappa \) por el teorema anterior.

[cerrar]

Por último:

Teorema: La suma y el producto de números naturales es un número natural.

Demostración

Fijamos un número natural \( m \) y consideramos el conjunto (bien definido)

\( X=\{n\mid n\in \mathbb{N}\land m+n\in \mathbb{N}\} \).

Como \( m+0=m \), tenemos que \( 0\in X \).

Si \( n\in X \), entonces \( m+n\in \mathbb{N} \), luego \( m+(n+1)=(m+n)+1\in \mathbb{N} \) por el segundo axioma de Peano, luego \( n+1\in X \).

(Aquí hemos empleado que la suma de cardinales es asociativa, cosa que ya establecimos en el mensaje anterior.)

Para el producto se razona análogamente, usando esta vez que \( m(n+1)=mn+n \), de modo que \( mn\in \mathbb{N} \) por hipótesis de inducción y la suma está en \( \mathbb{N} \) porque ya hemos probado que la suma de números naturales es un número natural.

[cerrar]

Al tener definida la suma y el producto de los números naturales con sus propiedades usuales (que hemos demostrado, de hecho, para cardinales arbitrarios) tenemos probado que NFA es una teoría aritmética (obviamente recursiva), de modo que, por una parte, le son aplicables los teoremas de incompletitud de Gödel y, por otra parte, ahora sabemos que en NFA se pueden definir todos los conceptos que en general se pueden definir en cualquier teoría aritmética, como la exponenciación de cardinales, los conceptos de número par, impar, primo, exponente de un primo en un número, etc.

Podemos definir el conjunto de todos los conjuntos finitos como

\( \mathcal F=\bigcup \mathbb{N} \).

Dejamos al lector que desarrolle las propiedades básicas de los conjuntos finitos en NFA.

[Carlos Ivorra]

Describiremos aquí los elementos básicos de la teoría de ordinales. Empezamos recordando la definición de conjunto bien ordenado, principalmente para constatar que está estratificada.

Definición: \( (A,\leq) \) es un conjunto bien ordenado si \( \leq\ \subset A\times A \) y además

1) \( \forall x\in A\ x\leq x \),

2) \( \forall xy\in A\ (x\leq y\land y\leq x\rightarrow x=y \),

3) \( \forall xyz\in A\ (x\leq y\land y\leq z\rightarrow x\leq z \),

4) \( \forall X (X\subset A\land X\neq \emptyset\rightarrow \exists x\in X\forall y\in X\ x\leq y) \).

Es facil ver que todas estas condiciones están estratificadas. La última dice que todo subconjunto de \( A \) no vacío tiene un mínimo elemento. Este mínimo es único, pues si \( x,x'\in X \) cumplen la condición, tendríamos que \( x\leq x' \) y \( x'\leq x \), luego \( x=x' \) por 2).

Esto nos permite definir

\( \min X\equiv x\mid (x\in X\land \forall y\in X\ x\leq y) \),

y así observamos que el término \( \min X \) está estratificado y que su tipo es una unidad menor que el tipo de \( X \).

Observemos que todo conjunto bien ordenado está totalmente ordenado, es decir, \( \forall xy\in A(x\leq y\lor y\leq x) \). Basta tener en cuenta que \( \{x,y\} \) tiene mínimo.

En general, si \( (A,\leq) \) es un conjunto ordenado (no necesariamente bien ordenado) y \( a\in A \), podemos considerar el segmento inicial determinado por \( a \):

\( A_a^<\equiv \{x\mid x\in A\land x<a\} \).

El término está estratificado y su tipo es el mismo de \( A \) y una unidad mayor que el de \( a \).

A menudo abusaremos de la notación escribiendo \( (A_a^<,\leq) \), cuando en lugar de \( \leq \) habría que escribir \( \leq\ \cap\ (A_a^<\times A_a^<) \).

Para completar la construcción de los números naturales del mensaje anterior faltaría probar lo siguiente:

Teorema: \( (\mathbb{N},\leq) \) es un conjunto bien ordenado.

Demostración

Sea \( X\subset \mathbb{N} \) un conjunto no vacío, y consideramos el conjunto

\( A=\{n\mid n\in \mathbb{N}\land \mathbb{N}_n^<\cap X=\emptyset\lor \exists m\in \mathbb{N}(m\leq n\land m \text{ es m\'{\i}nimo de }X)\} \).

Vemos que la definición de \( A \) es correcta (la propiedad que lo define está estratificada) y razonamos por inducción que \( A=\mathbb{N} \). En efecto, \( 0\in A \) porque \( \mathbb{N}_0^<=\emptyset \) y si \( n\in A \), o bien hay un mínimo de \( X \) menor o igual que \( n \), en cuyo caso lo mismo vale para \( n+1 \), luego \( n+1\in A \), o bien \( \mathbb{N}_n^<\cap X=\emptyset \). En este caso, o bien \( n\notin X \), con lo que \( \mathbb{N}_{n+1}^<\cap X=\emptyset \) y \( n+1\in A \), o bien \( n\in X \), en cuyo caso \( n \) es el mínimo de \( X \) y \( n\leq n+1 \), luego \( n+1\in A \).

Como sabemos que \( X \) no es vacío, tomamos \( n\in X \). Como \( n+1\in A \) y no cumple la primera condición, debe cumplir la segunda, es decir, hay un mínimo de \( X \) por debajo de \( n+1 \).

[cerrar]

Definición: Diremos que \( f:(A,\leq_A)\longrightarrow (B,\leq_B) \) es una semejanza si \( (A,\leq_A) \) y \( (B,\leq_B) \) son conjuntos bien ordenados, \( f: A\longrightarrow B \) biyectiva y \( \forall xy\in A(x\leq_A y\leftrightarrow f(x)\leq_B f(y)) \). Dos conjuntos bien ordenados son semejantes si existe una semejanza entre ellos.

Observemos que la definición de semejanza está estratificada con todas las variables del mismo tipo. Naturalmente se puede definir el concepto de semejanza para conjuntos no necesariamente bien ordenados, pero si no están totalmente ordenados hay que pedir que la inversa conserve también el orden.

Es fácil probar que la identidad de un conjunto bien ordenado en sí mismo es una semejanza, que la inversa de una semejanza es una semejanza y que la composición de semejanzas es una semejanza. En general, las semejanzas conservan todos los conceptos definidos en términos de la relación de orden (por ejemplo, si \( m \) es el mínimo de \( X \) entonces \( f(m) \) es el mínimo de \( f[X] \), o también, \( f[A_a^<]=B_{f(a)}^< \), etc.)

El siguiente hecho elemental tiene consecuencias importantes:

Teorema: Sea \( (A,\leq) \) un conjunto bien ordenado y \( f: A\longrightarrow A \) inyectiva tal que \( \forall xy\in A(x\leq y\rightarrow f(x)\leq f(y)) \). Entonces \( \forall x\in A\ x\leq f(x) \).

Demostración

Consideramos el conjunto \( X=\{x\in A\mid f(x)<x\} \). Basta probar que es vacío. Si no lo fuera, tendría un mínimo \( x \). Tenemos que \( f(x)<x \), luego \( f(f(x))<f(x) \), luego \( f(x)\in X \) y es menor que su mínimo, contradicción.

[cerrar]

De aquí deducimos:

Teorema: Un conjunto bien ordenado no es semejante a ninguno de sus segmentos iniciales.

Demostración

Si existe \( f:(A,\leq)\longrightarrow (A_a^<,\leq) \) semejanza, entonces \( f \) está en las condiciones del teorema anterior, pero \( f(a)\in A_a^< \), es decir, \( f(a)<a \), contradicción.

[cerrar]

El hecho básico no trivial sobre conjuntos bien ordenados es el siguiente:

Teorema: Dados dos conjuntos bien ordenados, o bien son semejantes, o bien uno es semejante a un (único) segmento inicial del otro.

Demostración

Sean \( (A,\leq_A) \) y \( (B,\leq_B) \) dos conjuntos bien ordenados.

En esta prueba vamos a considerar segmentos iniciales no estrictos, es decir, para cada \( a\in A \), definimos \( A_a^\leq\equiv \{x\mid x\in A\land x\leq a\} \), e igualmente para \( B \)

Observamos que, dado \( a\in A \), si existe un \( b\in B \) tal que \( (A_a^\leq,\leq_A) \) es semejante a \( (B_b^\leq,\leq_B) \), entonces \( b \) es único, pues si hubiera dos, digamos \( b<b' \) y \( b<c\leq b' \) es el menor elemento de \( B \) mayor que \( b \), entonces \( B_b^\leq \) y \( B_{b'}^\leq \) serían semejantes, pues ambos son semejantes a \( A_a^\leq \), pero \( B_b^\leq = (B_{b'}^\leq)_c^< \), y tenemos un conjunto bien ordenado semejante a uno de sus segmentos iniciales (estrictos), lo cual es imposible.

Similarmente, para cada \( b\in B \) hay a lo sumo un \( a\in A \) tal que \( (A_a^\leq,\leq) \) es semejante a \( (B_b^\leq,\leq) \).

Esto se traduce en que el conjunto

\( f\equiv\{(a,b)\mid a\in A\land b\in B\land \exists g\ g:(A_a^\leq,\leq_A)\longrightarrow (B_b^\leq,\leq_B)\mbox{ semejanza}\} \)

es una biyección de un subconjunto de \( A \) en un subconjunto de \( B \). (Recordamos que siempre que se define un conjunto se sobreentiende que hay que comprobar que la fórmula está estratificada.)

Veamos que \( f:(\mathcal Df,\leq_A)\longrightarrow (\mathcal Rf,\leq_B) \) es una semejanza.

En efecto, ya sabemos que \( f \) es biyectiva y, si \( a\leq a' \) están en \( \mathcal Df \), entonces existe una semejanza \( g:(A_{a'}^\leq,\leq_A)\longrightarrow (B_{f(a')}^{\leq},\leq_B) \). Sea \( b=g(a)\leq f(a') \), de modo que \( g \) se restringe a una semejanza

\( (A_a^\leq,\leq_A)\longrightarrow (B_b^\leq,\leq_B) \),

luego el par \( (a,b) \) cumple la definición de \( f \), es decir, \( f(a)=b\leq f(a') \).


Vamos a probar que o bien \( \mathcal Df=A \), o bien existe un \( a\in A \) tal que \( \mathcal Df=A_a^< \).

Si no se da el primer caso, sea \( a = \min(A\setminus \mathcal Df) \) y vamos a probar que \( \mathcal Df = A_a^< \). Trivialmente \( A_a^<\subset \mathcal Df \).

Tomamos \( a'\in \mathcal Df \) y hemos de ver que \( a'<a \). En caso contrario \( a<a' \), ya que la igualdad está descartada, pues \( a\notin \mathcal Df \). Sea \( b'=f(a') \). Esto significa que existe una semejanza \( g: (A_{a'}^{\leq},\leq)\longrightarrow (B_{b'}^{\leq},\leq) \). Sea \( b=g(a) \). Entonces, es claro que \( g|_{A_a^\leq}: (A_{a}^{\leq},\leq)\longrightarrow (B_{b}^{\leq},\leq) \), luego \( a\in \mathcal Df \), contradicción.

Similarmente se prueba que, o bien \( \mathcal Rf=B \) o bien existe un \( b\in B \) tal que \( \mathcal Rf=B_b^< \).

Esto nos da cuatro posibilidades, de las cuales las tres primeras son las que hemos de probar y sólo nos falta descartar la cuarta:

1) \( \mathcal Df=A\land \mathcal Rf=B \), con lo que los conjuntos dados son semejantes.

2) \( \mathcal Df=A\land \mathcal Rf=B_b^< \), con lo que \( A \) es semejante a un segmento de \( B \).

3) \( \mathcal Df=A_a^<\land \mathcal Rf=B \), con lo que \( B \) es semejante a un segmento de \( A \).

4) \( f: (A_a^<,\leq)\longrightarrow (B_b^<,\leq) \) semejanza.

Este caso no puede darse, pues esto significa que el par \( (a,b) \) cumple la definición de \( f \), luego \( a\in \mathcal Df \), contradicción.

[cerrar]

Con esto tenemos suficiente para definir los ordinales:

Definición: Si \( (A,\leq) \) es un conjunto bien ordenado, definimos su ordinal como el conjunto de todos los conjuntos bien ordenados semejantes a \( (A,\leq) \), es decir,

\( \mbox{ord}(A,\leq)\equiv\{x\mid \exists B\leq_B f\ f: (A,\leq)\longrightarrow (B,\leq_B)\text{ semejanza}\} \).

Observamos que el término \( \mbox{ord}(A,\leq) \) está estratificado y tiene tipo una unidad mayor que el de \( A \) y el de \( \leq \).

Llamaremos \( \text{Ord} \) al conjunto de todos los ordinales, es decir:

\( \text{Ord}\equiv \{\alpha\mid \exists A\leq((A,\leq)\text{ es un c.b.o}\land \alpha=\text{ord}(A,\leq))\} \)

Razonando exactamente igual que con los cardinales (cambiando biyección por semejanza) se prueba que:

Teorema: Si \( (A,\leq_A) \) y \( (B,\leq_B) \) son dos conjuntos bien ordenados, entonces

\( \text{ord}(A,\leq_A)=\text{ord}(B,\leq_B)\leftrightarrow \exists f\ f: (A,\leq_A)\longrightarrow (B,\leq_B)\text{ semejanza} \).

Como en el caso de los cardinales, podemos definir una relación de orden en el conjunto de los ordinales:

\( \leq\ \equiv\ \{(\alpha,\beta)\mid \exists A\leq_AB\leq_B\ (\alpha=\text{ord}(A,\leq_A)\land \beta=\text{ord}(B,\leq_B)\land
 \)

\(
(\alpha=\beta\lor \exists bg(b\in B\land g: (A,\leq_A)\longrightarrow (B_b^<,\leq_B)\text{ semejanza})))\} \)

La demostración del teorema siguiente es también análoga a la correspondiente para cardinales (y en ella está implícito que  la definición de la relación de orden no depende de la elección del conjunto ordenado que representa a cada ordinal):

Teorema: Si \( (A,\leq_A) \) y \( (B,\leq_B) \) son conjuntos bien ordenados, entonces

\( \text{ord}(A,\leq_A)\leq \text{ord}(B,\leq_B)\leftrightarrow \exists f\ f:(A,\leq_A)\longrightarrow (B,\leq_B)\text{ semejanza}\lor
 \)

\(
\exists fb\ (b\in B\land f:(A,\leq_A)\longrightarrow (B_b^<,\leq_B)\text{ semejanza}) \).

En definitiva: un conjunto bien ordenado tiene ordinal menor o igual que otro si ambos son semejantes (y entonces los ordinales son iguales) o bien el primero es semejante a un segmento inicial del segundo.

Observemos que si un conjunto bien ordenado es semejante a un segmento inicial de otro, entonces no pueden ser semejantes entre sí, pues entonces el segundo sería semejante a un segmento inicial propio, y ya hemos visto que eso es imposible. Por lo tanto, podemos precisar:

Teorema: Si \( (A,\leq_A) \) y \( (B,\leq_B) \) son conjuntos bien ordenados, entonces

\( \text{ord}(A,\leq_A)< \text{ord}(B,\leq_B)\leftrightarrow \exists fb\ (b\in B\land f:(A,\leq_A)\longrightarrow (B_b^<,\leq_B)\text{ semejanza}) \).

Más informalmente: el ordinal de \( A \) es menor que el ordinal de \( B \) si para ordenar un conjunto como \( B \) hay que empezar ordenando parte de sus elementos como \( A \) y luego añadir unos cuantos más detrás.

Hemos probado que, dados dos conjuntos bien ordenados, o bien son semejantes, o bien uno es semejante a un segmento del otro. Esto tiene la traducción inmediata según la cual dados dos ordinales \( \alpha \) y \( \beta \), o bien \( \alpha=\beta \), o bien \( \beta<\alpha \), o bien \( \alpha=\beta \). En definitiva, la relación de orden en \( \text{Ord} \) es total. Más aún:

Teorema: \( (\text{Ord},\leq) \) es un conjunto bien ordenado.

Demostración

Sea \( X\subset \text{Ord} \) no vacío. Sea \( \alpha\in X \), sea \( (A,\leq) \) un conjunto bien ordenado tal que \( \alpha=(A,\leq) \). Consideramos el conjunto (bien definido)

\( Y=\{a\mid a\in A\land \text{ord}(A_a^<,\leq)\in X\} \).

Si \( Y=\emptyset \), entonces, para cada \( \beta\in X \), tenemos que \( \beta=\text{ord}(B,\leq_B) \) para un cierto conjunto bien ordenado \( (B,\leq_B) \) que no es semejante a ninguna sección inicial de \( A \), ya que en tal caso \( \beta\in Y \). Por lo tanto \( \alpha\leq \beta \) y concluimos que \( \alpha \) es el mínimo de \( X \).

Si \( Y\neq \emptyset \) podemos tomar \( a=\min Y \), así como el ordinal \( \alpha_0=\text{ord}(A_a^<,\leq)\in X \). Se cumple que \( \alpha_0 \) es el mínimo de \( X \), pues para todo \( \beta=\text{ord}(B,\leq_B)\in X \), se cumple que \( (B,\leq_B) \) no es semejante a ninguna sección inicial de \( (A_a^<,\leq) \), es decir, a un conjunto de la forma \( (A_a^<)_x^<=A_x^< \) para un \( x\in A \) con \( x<a \), pues en tal caso \( x\in Y \) sería un elemento menor que el mínimo. Por consiguiente, \( \alpha_0\leq \beta \).

[cerrar]

En particular es fácil ver que el menor ordinal es el ordinal cero, definido como

\( 0=\text{ord}(\emptyset,\emptyset) \),

es decir el ordinal del conjunto vacío con la relación vacía, que es trivialmente un buen orden en el conjunto vacío, por la lógica "cínica" del vacío.

Teorema: No existe un máximo ordinal o, equivalentemente, todo ordinal \( \alpha \) tiene un ordinal inmediatamente mayor al que llamaremos \( \alpha+1 \).

Demostración

Sea \( \alpha=\text{ord}(A',\leq_{A'}) \). Sea \( A=A'\times\{0\} \) con el orden dado por

\( (x,0)\leq_A (y,0)\leftrightarrow x\leq_{A'}y \).

Es claro que \( A \) con este orden es semejante a \( A' \), por lo que también \( \alpha=\text{ord}(A,\leq_A) \), pero ahora podemos tomar \( u=(0,1) \) con la garantía de que \( u\notin A \), y podemos formar el conjunto \( B=A\cup\{u\} \). Si extendemos el orden de \( A \) de modo que \( u \) sea el máximo de \( B \), es claro que tenemos un buen orden y que \( A=B^<_u \), luego \( \alpha=\text{ord}(A,\leq_A)<\text{ord}(B,\leq_B) \).

Con esto ya hemos probado que \( \alpha \) tiene un ordinal posterior, y la buena ordenación da que hay un mínimo ordinal mayor que \( \alpha \), pero vamos a ver que dicho mínimo es precisamente \( \alpha+1=\text{ord}(B,\leq_B) \).

Para ello tomamos un ordinal \( \gamma>\alpha \). Esto significa que \( \gamma=\text{ord}(C,\leq_C) \) y que existe una semejanza \( f:(A,\leq_A)\longrightarrow (C_c^<;\leq_C) \). Extendemos \( f \) a \( g:(B,\leq_B)\longrightarrow (C,\leq_C) \) haciendo \( g(u)=c \).

Hay dos posibilidades: o bien \( c \) es el máximo de \( C \) y así \( C=C_c^<\cup\{c\} \), con lo que \( g \) es una semejanza y \( \alpha+1=\gamma \), o bien \( c \) tiene un inmediato posterior \( c' \), de modo que \( g:(B,\leq_B)\longrightarrow (C_{c'}^<,\leq_C) \) semejanza, con lo que \( \alpha+1<\gamma \).

En ambos casos \( \alpha+1\leq \gamma \), luego \( \alpha+1 \) es el mínimo ordinal mayor que \( \alpha \).

[cerrar]

Notemos que el término \( \alpha+1 \) está estratificado con el mismo tipo que \( \alpha \), pues puede definirse como \( \alpha+1\equiv \min\{\beta\mid \beta\in \text{Ord}\land \beta>\alpha\} \). (Las llaves suben el tipo una unidad, pero el mínimo lo vuelve a bajar.)

Notemos que hay una diferencia notable entre cardinales y ordinales: mientras que hay un máximo cardinal \( \kappa_0 = |V| \), no hay un máximo ordinal.

Añado un último teorema elemental que hará falta luego:

Teorema: Si \( (A,\leq) \) es un conjunto bien ordenado y \( B\subset A \), entonces \( \text{ord}(B,\leq)\leq \text{ord}(A,\leq) \)

Demostración

Si fuera \( \text{ord}(A,\leq)< \text{ord}(B,\leq) \), existiría un \( b\in B \) y una semejanza \( f: (A\leq)\longrightarrow (B_b^<,\leq) \), que es una aplicación \( f:A\longrightarrow A \) inyectiva tal que conserva el orden y \( f(b)<b \). Hemos visto antes que esto es imposible.

[cerrar]

Esbozamos a continuación las definiciones de suma y producto de ordinales sin entrar en detalles, porque no nos van a ser necesarias posteriormente.

Definición: Si \( (A,\leq_A) \) y \( (B,\leq_B) \) son dos conjuntos bien ordenados definimos su suma como el conjunto bien ordenado \( ((A\times\{0\})\cup (B\times\{1\}),\leq) \), donde la relación viene dada por

\( (x,u)\leq (y,v)\leftrightarrow (u=0\land v=1)\lor (u=v\land x\leq y) \),

Es decir, la suma es un conjunto que contiene un subconjunto ordenado como \( A \) y otro ordenado como \( B \), de modo que todos los elementos de \( A \) son anteriores a los de \( B \). Es fácil probar que si \( A \) es semejante a \( A' \) y \( B \) es semejante a \( B' \) entonces la suma de \( A \) y \( B \) es semejante a la suma de \( A' \) y \( B' \), lo cual permite definir una operación

\( +:\text{Ord}\times \text{Ord}\longrightarrow \text{Ord} \)

de modo que \( \alpha+\beta \) se calcula tomando un conjunto de ordinal \( \alpha \), otro de ordinal \( \beta \) y haciendo \( \alpha+\beta \) igual al ordinal de la suma.

Si llamamos

\( 1\equiv \text{Ord}(\{\emptyset\},\{(\emptyset,\emptyset)\}) \),

es decir, el ordinal del conjunto \( \{\emptyset\} \) con la única relación de orden que podemos definir en él, es fácil ver que el ordinal \( \alpha+1 \) que hemos construido algo más arriba como el mínimo ordinal mayor que \( \alpha \) no es sino la suma de \( \alpha \) y \( 1 \) según la definición general.

También podemos definir una aplicación \( \cdot:\text{Ord}\times \text{Ord}\longrightarrow \text{Ord} \) a partir del producto lexicográfico, de dos conjuntos bien ordenados \( (A,\leq_A) \) y \( (B,\leq_B) \), que es el buen orden en \( (A\times B) \) dado por

\( (a,b)\leq (a',b')\leftrightarrow b<b'\lor (b=b'\land a\leq a') \)

Es decir, para comparar dos pares comparamos su componente de la derecha y, en caso de empate, miramos la otra. Así, el ordinal \( \alpha\beta \) se define como el ordinal del producto lexicográfico de un conjunto de ordinal \( \alpha \) por otro de ordinal \( \beta \).

A partir de estas definiciones se pueden demostrar las propiedades usuales de la suma y el producto de ordinales (la asociatividad, la no conmutatividad, la distributividad, etc.) Como ya hemos indicado, no necesitaremos nada de esto, y por ello lo pasamos por encima.


Para terminar definimos una aplicación que conecta los ordinales y los cardinales: Es evidente que si dos conjuntos bien ordenados \( (A,\leq_A) \) y \( (B,\leq_B) \) son semejantes, en particular los conjuntos \( A \) y \( B \) son equipotentes, porque las semejanzas son biyecciones, luego podemos definir la aplicación

\( \text{card}: \text{Ord}\longrightarrow K \)

mediante

\( \text{card}\equiv\{(\alpha,\kappa)\mid \exists A\leq\ ((A,\leq)\text{ es un c.b.o.}\land \alpha=\text{ord}(A,\leq)\land \kappa = |A|)\} \)

Así \( \text{card}(\alpha) \) es el cardinal de cualquier conjunto bien ordenado cuyo ordinal sea \( \alpha \).

Observemos que si \( \alpha<\beta \), entonces \( \alpha=\text{ord}(A,\leq_A) \), \( \beta=\text{ord}(B,\leq_B) \), y existe un \( b\in B \) y una semejanza \( f: (A,\leq_A)\longrightarrow (B_b^<,\leq_B) \), que en particular es una aplicación inyectiva \( f:A\longrightarrow B \). Por lo tanto \( |A|\leq |B| \), y esto es trivialmente cierto si \( \alpha=\beta \), luego hemos probado:

Teorema: \( \forall \alpha\beta\in\text{Ord}\ (\alpha\leq\beta\rightarrow \text{card}(\alpha)\leq \text{card}(\beta)) \).

De las definiciones de suma y producto de ordinales se deduce fácilmente que

\( \text{card}(\alpha+\beta)=\text{card}(\alpha)+\text{card}(\beta),\qquad \text{card}(\alpha\beta)=\text{card}(\alpha)\text{card}(\beta) \)

(donde a la izquierda del igual tenemos las operaciones con ordinales y a la derecha las operaciones con cardinales).

No necesitaremos estas dos últimas fórmulas. A lo sumo el caso de \( \alpha+1 \) que sí que hemos descrito con detalle. En la construcción de \( \alpha+1 \) se ve que si \( \alpha=(A,\leq) \), entonces \( \alpha+1=\text{ord}(A\cup \{u\},\leq) \), con \( A\cap \{u\}=\emptyset \), luego \( |A\cup\{u\}|=|A|+1 \), y así:

\( \text{card}(\alpha+1)=\text{card}(\alpha)+1 \),

donde el primer \( 1 \) es ordinal y el segundo cardinal.