6.5: La teoría de los conjuntos

Template:MathJaxZach

Casi todas las matemáticas se pueden desarrollar en la teoría de conjuntos. El desarrollo de las matemáticas en esta teoría implica una serie de cosas. Primero, requiere de un conjunto de axiomas para la relación\(\in\). Se han desarrollado varios sistemas de axiomas diferentes, a veces con propiedades contradictorias de\(\in\). Destaca el sistema de axiomas conocido como\(\Log{ZFC}\), la teoría de conjuntos de Zermelo-Fraenkel con el axioma de elección: es con mucho el más utilizado y estudiado, porque resulta que sus axiomas bastan para probar casi todas las cosas que los matemáticos esperan poder probar. Pero antes de que eso pueda establecerse, primero es necesario dejar claro cómo podemos incluso expresar todas las cosas que a los matemáticos les gustaría expresar. Para empezar, el lenguaje no contiene símbolos constantes o símbolos de función, por lo que parece a primera vista poco claro que podemos hablar de conjuntos particulares (como\(\emptyset\) o\(\Nat\)), se puede hablar de operaciones en conjuntos (como\(X \cup Y\) y\(\Pow{X}\) ), y mucho menos otras construcciones que involucren cosas distintas a los conjuntos, como las relaciones y las funciones.

Para empezar, “es un elemento de” no es la única relación que nos interesa: “es un subconjunto de” parece casi igual de importante. Pero podemos definir “es un subconjunto de” en términos de “es un elemento de”. Para ello, tenemos que encontrar una fórmula\(A(x, y)\) en el lenguaje de la teoría de conjuntos que sea satisfecha por un par de conjuntos\(\tuple{X, Y}\) iff\(X \subseteq Y\). Pero\(X\) es un subconjunto de\(Y\) por si acaso todos los elementos de también\(X\) son elementos de\(Y\). Entonces podemos definir\(\subseteq\) por la fórmula\[\lforall{z}{(z \in x \lif z \in y)}\nonumber\] Ahora, siempre que queramos usar la relación\(\subseteq\) en una fórmula, podríamos usar esa fórmula (con\(x\) y\(y\) adecuadamente reemplazada, y la variable enlazada \(z\)renombrado si es necesario). Por ejemplo, la extensibilidad de los conjuntos significa que si alguno de los conjuntos\(x\) y\(y\) están contenidos entre sí, entonces\(x\) y\(y\) debe ser el mismo conjunto. Esto se puede expresar por\(\lforall{x}{\lforall{y}{((x \subseteq y \land y \subseteq x) \lif x = y)}}\), o, si reemplazamos\(\subseteq\) por la definición anterior, por\[\lforall{x}{\lforall{y}{((\lforall{z}{(z \in x \lif z \in y)} \land \lforall{z}{(z \in y \lif z \in x)}) \lif x = y)}}.\nonumber\] Este es de hecho uno de los axiomas de\(\Log{ZFC}\), el “axioma de la extensionalidad”.

No hay símbolo constante para\(\emptyset\), pero podemos expresar “\(x\)está vacío” por\(\lnot \lexists{y}{y \in x}\). Entonces “\(\emptyset\)existe” se convierte en la oración\(\lexists{x}{\lnot \lexists{y}{y \in x}}\). Este es otro axioma de\(\Log{ZFC}\). (Obsérvese que el axioma de la extensibilidad implica que solo hay un conjunto vacío). Siempre que queramos hablar\(\emptyset\) en el lenguaje de la teoría de conjuntos, escribiríamos esto como “hay un conjunto que está vacío y...” Como ejemplo, para expresar el hecho de que\(\emptyset\) es un subconjunto de cada conjunto, podríamos escribir\[\lexists{x}{(\lnot\lexists{y}{y \in x} \land \lforall{z}{x \subseteq z})}\nonumber\] donde, por supuesto, \(x \subseteq z\)a su vez tendría que ser sustituido por su definición.

Para hablar de operaciones en sets, tal tiene\(X \cup Y\) y\(\Pow{X}\), tenemos que usar un truco similar. No hay símbolos de función en el lenguaje de la teoría de conjuntos, pero podemos expresar las relaciones funcionales\(X \cup Y = Z\) y\(\Pow{X} = Y\)\[\begin{aligned} & \lforall{u}{((u \in x \lor u \in y) \liff u \in z)}\\ & \lforall{u}{(u \subseteq x \liff u \in y )}\end{aligned}\nonumber\] ya que los elementos de\(X \cup Y\) son exactamente los conjuntos que son elementos de\(X\) o elementos de\(Y\), y los elementos de\(\Pow{X}\) son exactamente los subconjuntos de\(X\). Sin embargo, esto no nos permite usar\(x \cup y\) ni\(\Pow{x}\) como si fueran términos: sólo podemos usar todas las fórmulas que definen las relaciones\(X \cup Y = Z\) y\(\Pow{X} = Y\). De hecho, no sabemos que estas relaciones estén siempre satisfechas, es decir, no sabemos que los sindicatos y los conjuntos de poder siempre existen. Por ejemplo, la oración\(\lforall{x}{\lexists{y}{\Pow{x} = y}}\) es otro axioma de\(\Log{ZFC}\) (el axioma del conjunto de poder).

Ahora, ¿qué pasa con hablar de pares ordenados o funciones? Aquí tenemos que explicar cómo podemos pensar en pares ordenados y funciones como tipos especiales de conjuntos. Una forma de definir el par ordenado\(\tuple{x, y}\) es como el conjunto\(\{\{x\}, \{x, y\}\}\). Pero como antes, no podemos introducir un símbolo de función que nombre a este conjunto; solo podemos definir la relación\(\tuple{x, y} = z\), es decir,\(\{\{x\}, \{x, y\}\} = z\):\[\lforall{u}{(u \in z \liff (\lforall{v}{(v \in u \liff v = x)} \lor \lforall{v}{(v \in u \liff (v = x \lor v = y))}))}\nonumber\] Esto dice que los elementos\(u\) de\(z\) son exactamente aquellos conjuntos que tienen \(x\)como su único elemento o tener\(x\) y\(y\) como sus únicos elementos (es decir, aquellos conjuntos que son idénticos\(\{x\}\) o idénticos a\(\{x, y\}\)). Una vez que tengamos esto, podemos decir más cosas, por ejemplo, que\(X \times Y = Z\):\[\lforall{z}{(z \in Z \liff \lexists{x}{\lexists{y}{(x \in X \land y \in Y \land \tuple{x, y} = z)}})}\nonumber\]

Una función\(f \colon X \to Y\) puede pensarse como la relación\(f(x) = y\), es decir, como el conjunto de pares\(\Setabs{\tuple{x,y}}{f(x) = y}\). Entonces podemos decir que un conjunto\(f\) es una función de\(X\) a\(Y\) si (a) es una relación\(\subseteq X \times Y\), (b) es total, es decir, para todos\(x \in X\) hay algunos\(y \in Y\) tales que\(\tuple{x, y} \in f\) y (c ) es funcional, es decir, cuando sea\(\tuple{x, y}, \tuple{x, y'} \in f\),\(y = y'\) (porque los valores de las funciones deben ser únicos). Entonces “\(f\)es una función de\(X\) a\(Y\)” se puede escribir como:\[\begin{aligned} \lforall{u}{(u \in f \lif {}} & \lexists{x}{\lexists{y}{(x \in X \land y \in Y \land \tuple{x, y} = u)}}) \land {}\\ \lforall{x}{(x \in X \lif {}} & (\lexists{y}{(y \in Y \land \mathrm{maps}(f, x, y))} \land {}\\ & (\lforall{y}{\lforall{y'}{((\mathrm{maps}(f, x, y) \land \mathrm{maps}(f, x, y')) \lif y = y')}}))\end{aligned}\nonumber\] donde se\(\mathrm{maps}(f, x, y)\) abrevia\(\lexists{v}{(v \in f \land \tuple{x, y} = v)}\) (esta fórmula expresa “\(f(x) = y\)”).

Ahora tampoco es difícil expresar que\(f\colon X \to Y\) es inyectivo, por ejemplo:\[\begin{gathered} f \colon X \to Y \land \lforall{x}{\lforall{x'}{((x \in X \land x' \in X \land {}}} \\ \lexists{y}{(\mathrm{maps}(f, x, y) \land \mathrm{maps}(f, x', y))}) \lif x = x')\end{gathered}\nonumber\] Una función\(f\colon X \to Y\) es iff inyectiva, siempre que se\(f\) mapee\(x, x' \in X\) a una sola\(y\),\(x = x'\). Si abreviamos esta fórmula como\(\mathrm{inj}(f, X, Y)\), ya estamos en condiciones de afirmar en el lenguaje de la teoría de conjuntos algo tan no trivial como el teorema de Cantor: no hay función inyectiva de\(\Pow{X}\) a\(X\):\[\lforall{X}{\lforall{Y}{(\Pow{X} = Y \lif \lnot\lexists{f}{\mathrm{inj}(f, Y, X)})}}\nonumber\]

Se podría pensar que la teoría de conjuntos requiere otro axioma que garantice la existencia de un conjunto para cada propiedad definitoria. Si\(A(x)\) es una fórmula de teoría de conjuntos con la variable\(x\) libre, podemos considerar la oración\[\lexists{y}{\lforall{x}{(x \in y \liff A(x))}}.\nonumber\] Esta frase establece que hay un conjunto\(y\) cuyos elementos son todos y sólo aquellos\(x\) que satisfacen \(A(x)\). A este esquema se le llama el “principio de comprensión”. Se ve muy útil; desafortunadamente es inconsistente. Tomemos\(A(x) \ident \lnot x \in x\), entonces el principio de comprensión establece\[\lexists{y}{\lforall{x}{(x \in y \liff x \notin x)}},\nonumber\] es decir, establece la existencia de un conjunto de todos los conjuntos que no son elementos de sí mismos. No puede existir tal conjunto, esta es la Paradoja de Russell. \(\Log{ZFC}\), de hecho, contiene una versión restringida y consistente de este principio, el principio de separación:\[\lforall{z}{\lexists{y}{\lforall{x}{(x \in y \liff (x \in z \land A(x))}}}.\nonumber\]

Problema\(\PageIndex{1}\)

Demostrar que el principio de comprensión es inconsistente al dar una derivación que muestra\[\lexists{y}{\lforall{x}{(x \in y \liff x \notin x)}} \Proves \lfalse.\nonumber\] Puede ayudar a mostrar primero\((A \lif \lnot A) \land (\lnot A \lif A) \Proves \lfalse\).