Ordinales (I)

Abstract. This is the first post of a series concerning ordinals. I start by motivating their need by means of Cantor-Bendixson derivative, and then develop some of the basic concepts (induction, recursion, arithmetic).

Comenzaré discutiendo una operación sobre los subconjuntos de un espacio topológico. Es en algún sentido dual a la clausura, porque en vez de agrandar, achica.

Una Derivada Topológica.   

Definición 1 Sea {X} espacio topológico. La derivada de Cantor-Bendixson de {X} es {X'\mathrel{\mathop:}= \{x\in X : x \text{ no es aislado}\}}.

De hecho, aplicar la clausura a un conjunto le agrega todos los puntos de acumulación, y aplicarla a un conjunto cerrado no hace nada. En cambio, la derivada de Cantor-Bendixson sólo deja los puntos de acumulación y se puede aplicar varias veces y obtener cosas distintas cada vez. Para no escribir cosas como {X'''''''}, definimos:

\displaystyle X^{(0)}\mathrel{\mathop:}= X; \qquad X^{(n+1)}\mathrel{\mathop:}= \bigl(X^{(n)}\bigr)'.

Notemos que esta derivada es decreciente, {X^{(n)}\supseteq X^{(n+1)}} y que cualquiera sea {X}, {X'} es cerrado.

Ejercicio 1 Probar lo anterior, y encontrar {X\subseteq {\mathbb R}} tal que {X'} y {X''} sean distintos. (¿Y que {X''\neq X^{(3)}}? ¿Etcétera?)

En general, para cada {n}, hay subconjuntos {X} de los reales tales que todos los {X^{(j)}} son distintos con {j<n}. Más aún, hay un {X} tal que {X^{(n)}} es una sucesión infinita estrictamente decreciente.

Tomando {\ensuremath{\omega}} como símbolo greco-judeo-cristiano de infinito, podríamos definir

\displaystyle X^{(\ensuremath{\omega})} \mathrel{\mathop:}= \bigcap_{n\in{\mathbb N}} X^{(n)}.

¿Se puede seguir aplicando {(\cdot)'}? ¿Obtenemos algo nuevo? Sí: existe un subconjunto cerrado {\Omega} de {{\mathbb R}} tal que {\Omega^{(\ensuremath{\omega})}\neq\Omega^{(n)}} para todo {n\in{\mathbb N}} y {\bigl(\Omega^{(\ensuremath{\omega})}\bigr)'\neq\Omega^{(\ensuremath{\omega})}}. Definimos entonces

\displaystyle X^{(\ensuremath{\omega}+1)} \mathrel{\mathop:}= \bigl(X^{(\ensuremath{\omega})}\bigr)'.

G.~Cantor vio que en un espacio topológico general, este proceso podría aplicarse indefinidamente, e indizó este proceso con los ordinales.

Los ordinales son las “formas posibles” (tipos de isomorfismo) de cierta clase de conjuntos (totalmente) ordenados, los buenos órdenes.

Buenos órdenes.   

Definición 2 Un conjunto bien ordenado {\langle X,\preceq\rangle } es un conjunto {X} con una relación de orden (total) {\preceq} tal que todo {Y\subseteq X} no vacío tiene elemento mínimo según {\preceq}:

\displaystyle \forall Y\subseteq X : \exists y\in Y . \forall z\in Y \; (y\preceq z).

En este caso decimos que {\preceq} es un buen orden (sobre {X}).

El ejemplo paradigmático de conjunto bien ordenado es {\langle {\mathbb N},\leq\rangle }. Otros ejemplos son los siguientes (Fraenkel, [Fra61]): {\langle \mathbb{Z},\preceq\rangle }, donde {\preceq} coincide con la relación {\leq} para pares de números no negativos, se invierte para pares de números negativos, y estipula que todos los números negativos son mayores que todos los positivos:

\displaystyle 0, 1, 2, 3, \dots, -1, -2, -3,\dots, \ \ \ \ \ (1)

El siguiente es un buen orden sobre {\mathbb{Q}^+}:

\displaystyle 1, 2, 3, \dots, \frac{1}{2}, \frac{3}{2}, \frac{5}{2}, \dots, \frac{1}{3}, \frac{2}{3}, \frac{4}{3},\dots,\frac{1}{4}, \frac{3}{4}, \frac{5}{4}, \dots \ \ \ \ \ (2)

También, de manera trivial, todo conjunto finito totalmente ordenado es un buen orden (incluimos en este caso al conjunto vacío). En nuestra definición estamos suponiendo que el orden {\preceq} corresponde a una relación de “menor o igual”. Para referirnos al orden estricto usaremos a veces {\prec} y en general también diremos que {\langle X,\prec\rangle } es un buen orden (como es usual, {x\prec y} si y sólo si {x\preceq y} y {x\neq y}).

Se sigue de la definición que si {\langle X,\preceq\rangle } es un buen orden entonces para todo {Y\subseteq X}, {\langle Y,{\preceq}\cap (Y\times Y)\rangle } está bien ordenado. Se obtiene fácilmente:

Proposición 3 {\langle X,\preceq\rangle } está bien ordenado si y sólo si no existen sucesiones estrictamente {\preceq}-decrecientes infinitas.

Cuidado: la prueba, aunque “obvia”, necesita del axioma de elección.

Finalmente, para decir que dos órdenes tienen la misma forma, necesitamos la siguiente

Definición 4 Un isomorfismo entre dos conjuntos ordenados {\langle X,\preceq\rangle } y {\langle Y,\trianglelefteq\rangle } es una función biyectiva {f:X\rightarrow Y} tal que {a\preceq b \iff f(a)\trianglelefteq f(b)}. Decimos que {\langle X,\preceq\rangle } y {\langle Y,\trianglelefteq\rangle } son isomorfos si hay un isomorfismo entre ellos.

Ejercicio 2 Sea {\trianglelefteq} el siguiente orden en {{\mathbb N}\times\{0,1\}}:

{(a,b)\trianglelefteq (c,d)\iff b<d}, o bien si {b = d} y {a\leq b}

Convencerse de que {\langle {\mathbb N}\times\{0,1\},\trianglelefteq\rangle } es isomorfo al orden de arriba sobre {\mathbb{Z}}.

Ejercicio 3 Encontrar 4 buenos órdenes no isomorfos a los anteriores (y no isomorfos entre sí).

…Continuará

Bibliografía

[Fra61] Abraham A. Fraenkel. Abstract Set Theory. Studies in Logic and Foundations of Mathematics. North-Holland, Amsterdam, second edition, 1961.

Los axiomas de la Teoría de Conjuntos

Abstract. Just introducing the ZFC axioms very briefly, with a slight hint of what first-order logic is.

Se afirma que toda la Matemática se puede basar en la Teoría de Conjuntos. No voy a dedicar este post a justificar esta afirmación (quizá es un tema que se puede discutir en los comentarios a esta nota), sino simplemente voy a enumerar las propiedades de los conjuntos que permiten que esto pase.

Los axiomas que voy a introducir se conocen por los apellidos de Zermelo, Fraenkel y se incluye en su nombre explícitamente a uno de ellos (el de elección, o Axiom of Choice (AC) en inglés); para acortar ponemos ZFC.

La mayor parte de estos axiomas dan cuenta de operaciones “obvias” de construcción de conjuntos, o bien propiedades de clausura de los mismos. Hay uno, que quizá algún lector no conozca, que va en la dirección contraria. Seré deliberadamente vago (como en muchos aspectos de mi vida) con algunos detalles de la presentación, pero quisiera que estos mismos descuidos motiven (indignen) lo suficiente como para que la persona lectora pueda consultar (increpar) en los comentarios. Un ejemplo de esta vaguedad es que las fórmulas que formalizan los axiomas quizá dicen más, o ligeramente otra cosa, que los enunciados textuales; otro, que no defino algunos símbolos ({\varnothing} es uno de ellos).

Quería cometer un último acto de vaguedad al no hablar del lenguaje en el que estoy expresando los axiomas, pero hay dos de ellos que piden a gritos que uno sea preciso al respecto. Antes de satisfacer esta necesidad, sólo diré provisoriamente que {\neg,\wedge,\vee,\rightarrow,\leftrightarrow} se leen, respectivamente, “no”, “y”, “ó”, “implica”, “si y sólo si”. En la enumeración que sigue, todas las variables se refieren a conjuntos.

  • Existencia. Existe al menos un conjunto.

    \displaystyle \exists x : x=x.

  • Extensionalidad. Dos conjuntos son iguales si y sólo si tienen los mismos elementos.

    \displaystyle \forall x,y : x =y \leftrightarrow \forall z (z \in x \leftrightarrow z \in y).

  • Pares. Dados {x} e {y}, existe un conjunto que contiene (como elementos) exactamente a ambos.

    \displaystyle \forall x,y \exists c :\forall z (z \in c \leftrightarrow z =x \vee z = y).

  • Unión. Dado un conjunto {x}, la unión {\bigcup x } de todos los conjuntos que pertenecen a {x} es un conjunto.

    \displaystyle \forall x \exists u : \forall z \bigl(z \in u \leftrightarrow \exists y \in x ( z \in y )\bigr).

  • Conjunto Potencia o de Partes. Dado un conjunto {x}, existe un conjunto {\mathcal { P}(x)} que contiene a todos los subconjuntos de {x}.

    \displaystyle \forall x \exists p : \forall y \bigl(y \in p \leftrightarrow \forall z \in y ( z \in x )\bigr).

  • Separación. Para todo {x}, parámetros {\bar x = x_1,\dots,x_n} y toda “propiedad definible” de {(n+1)}-tuplas {\varphi}, existe un conjunto {\{y\in x : \varphi(y,\bar x)\}} que contiene exactamente a los elementos de {x} que cumplen con {\varphi(\cdot,\bar x)}.

    \displaystyle \forall x \forall \bar x \exists s : \forall y (y \in s \leftrightarrow \varphi(y,\bar x) \wedge y \in x).

  • Infinito. Existe un conjunto infinito.

    \displaystyle \exists x : \varnothing\in x \wedge \forall y (y \in x \rightarrow y\cup \{y\}\in x).

  • Reemplazo. Para cada “función definible” con parámetros {\bar x} (con gráfico {\psi(\cdot,\cdot,\bar x)}), la imagen de un conjunto por esa función es otro conjunto.

    \displaystyle \forall x, \bar x: \bigl(\forall y\in x \exists!z : \psi(y,z,\bar x)\bigr) \rightarrow \exists r : \forall w \bigl( w\in r \leftrightarrow \exists t\in x : \psi(t,w,\bar x)\bigr).

  • Regularidad. No hay sucesiones estrictamente decrecientes de pertenencia.

    \displaystyle \forall x \exists y : \forall z \in x (z\notin y).

  • Elección. Para todo conjunto {x} de conjuntos disjuntos no vacíos, existe un conjunto que corta a cada uno en exactamente un punto.

    \displaystyle \forall x \Bigl(\bigl(\forall y,w\in x: y \neq \varnothing \wedge \neg\exists t: t\in y \wedge t \in w \bigr) \rightarrow \exists c: \forall y \in x \bigl(\exists! z (z\in y \wedge z\in c)\bigr)\Bigr).

Tanto el axioma de Separación como el de Reemplazo son realmente listas de axiomas, uno para cada {\varphi} y {\psi}, respectivamente. Y ambos requieren que uno defina qué significa ser definible. En nuestro caso, una propiedad {\varphi(\cdot)} será definible si se puede expresar usando los símbolos que usamos para escribir los axiomas: los conectivos proposicionales, los cuantificadores {\forall} y {\exists}, la igualdad {=}, el símbolo de pertenencia {\in} y variables (éste es el lenguaje de la lógica de primer orden. Por ejemplo, la propiedad “{y} es el singulete {\{x\}}” es una propiedad definible {\varphi(x,y)} de pares, puesto que se puede escribir

\displaystyle \varphi(x,y) \equiv \forall z (z \in y \leftrightarrow z = x).

De hecho, {\varphi} también es (el gráfico de) una función definible. Esto es cierto gracias al axioma de Extensionalidad: supongamos que hay {y,y'} tales que {\varphi(x,y)} y {\varphi(x,y')}. Pero eso quiere decir que, para cada {z},

\displaystyle z \in y \leftrightarrow z = x \leftrightarrow z \in y',

y entonces {y=y'}. Notemos un punto importante, que {\varphi} define una función módulo los axiomas de la teoría ZFC; en muchas ocasiones es crucial saber específicamente cuáles son los que necesito para tener probar “buena definición”.

Me despido con algunos ejercicios, habiendo pasado el límite razonable de cantidad de palabras.

  1. Probar que {y = \varnothing} es un propiedad definible.
  2. Probar que {x \mapsto \mathcal{P}(x)} es una función definible.
  3. Probar que sin el requerimiento de que los conjuntos sean disjuntos, AC es falso. Es decir, no es cierto que

    \displaystyle \forall x \Bigl(\bigl(\forall y\in x : y \neq \varnothing \bigr) \rightarrow \exists c: \forall y \in x \bigl(\exists! z (z\in y \wedge z\in c)\bigr)\Bigr).

  4. (*) Probar que el axioma de Separación es falso si uno no pide un ambiente {x}. Es decir, no vale que:

    \displaystyle \forall \bar x \exists s : \forall y (y \in s \leftrightarrow \varphi(y,\bar x)).

Pressing the word…

This is my very first post.

Plans for the next few months: expository posts on 6 or 7 results (hope interesting enough), and maintain some discussion on basic set theory, aiming to develop this area in the neighboring region of my university (this will probably be in Spanish, and if times permits, also in English).