4.9: Conjuntos de diferentes tamaños y teorema de Cantor

Template:MathJaxZach

Hemos ofrecido una declaración precisa de la idea de que dos conjuntos tienen el mismo tamaño. También podemos ofrecer una declaración precisa de la idea de que un conjunto es más pequeño que otro. Nuestra definición de “es menor que (o equinúmero)” requerirá, en lugar de una biyección entre los conjuntos, una inyección del primer conjunto al segundo. Si existe tal función, el tamaño del primer conjunto es menor o igual que el tamaño del segundo. Intuitivamente, una inyección de un conjunto a otro garantiza que el rango de la función tenga al menos tantos elementos como el dominio, ya que no hay dos elementos del dominio mapeados al mismo elemento del rango.

Definición\(\PageIndex{1}\)

\(A\)no es mayor que\(B\)\(\cardle{A}{B}\), escrito, si hay una inyección\(f \colon A \to B\).

Es claro que se trata de una relación reflexiva y transitiva, pero que no es simétrica (esto se deja como ejercicio). También podemos introducir una noción, que establece que un conjunto es (estrictamente) más pequeño que otro.

Definición\(\PageIndex{2}\)

\(A\)es menor que\(B\), escrito\(\cardless{A}{B}\), si hay una inyección\(f\colon A \to B\) pero no biyección\(g\colon A \to B\), es decir,\(\cardle{A}{B}\) y\(\cardneq{A}{B}\).

Es claro que esta relación es antirreflexiva y transitiva. (Esto se deja como un ejercicio.) Usando esta notación, podemos decir que un conjunto\(A\) es enumerable iff\(\cardle{A}{\Nat}\), y que no\(A\) es enumerable iff\(\cardless{\Nat}{A}\). Esto nos permite reafirmar el Teorema 4.6.2 como la observación de que\(\cardless{\Nat}{\Pow{\Nat}}\). De hecho, Cantor (1892) demostró que este último punto es perfectamente general:

Teorema\(\PageIndex{1}\) (Cantor)

\(\cardless{A}{\Pow{A}}\), para cualquier conjunto\(A\).

Comprobante. El mapa\(f(x) = \{x\}\) es una inyección\(f \colon A \to \Pow{A}\), ya que si\(x \neq y\), entonces también\(\{x\} \neq \{y\}\) por extensionalidad, y así\(f(x) \neq f(y)\). Entonces tenemos eso\(\cardle{A}{\Pow{A}}\).

Demostramos que no puede haber una función suryectiva\(g\colon A \to \Pow{A}\), let alone a bijective one, and hence that \(\cardneq{A}{\Pow{A}}\). For suppose that \(g\colon A \to \Pow{A}\). Since \(g\) is total, every \(x \in A\) is mapped to a subset \(g(x) \subseteq A\). We show that \(g\) cannot be surjective. To do this, we define a subset \(\overline{A} \subseteq A\) which by definition cannot be in the range of \(g\). Let \[\overline{A} = \Setabs{x \in A}{x \notin g(x)}.\nonumber\] Since \(g(x)\) is defined for all \(x \in A\), \(\overline{A}\) is clearly a well-defined subset of \(A\). But, it cannot be in the range of \(g\). Let \(x \in A\) be arbitrary, we show that \(\overline{A} \neq g(x)\). If \(x \in g(x)\), then it does not satisfy \(x \notin g(x)\), and so by the definition of \(\overline{A}\), we have \(x \notin \overline{A}\). If \(x \in \overline{A}\), it must satisfy the defining property of \(\overline{A}\), i.e., \(x \in A\) and \(x \notin g(x)\). Since \(x\) was arbitrary, this shows that for each \(x \in \overline{A}\), \(x \in g(x)\) iff \(x \notin \overline{A}\), and so \(g(x) \neq \overline{A}\). In other words, \(\overline{A}\) cannot be in the range of \(g\), contradicting the assumption that \(g\) is surjective. ◻

Es instructivo comparar la prueba del Teorema \(\PageIndex{1}\)con la del Teorema 4.6.2. Ahí mostramos que para cualquier lista\(Z_1\), \(Z_2\), …, of subsets of \(\PosInt\) one can construct a set \(\overline{Z}\) of numbers guaranteed not to be on the list. It was guaranteed not to be on the list because, for every \(n \in \PosInt\), \(n \in Z_n\) iff \(n \notin \overline{Z}\). This way, there is always some number that is an element of one of \(Z_n\) or \(\overline{Z}\) but not the other. We follow the same idea here, except the indices \(n\) are now elements of \(A\) instead of \(\PosInt\). The set \(\overline{B}\) is defined so that it is different from \(g(x)\) for each \(x \in A\), because \(x \in g(x)\) iff \(x \notin \overline{B}\). Again, there is always an element of \(A\) which is an element of one of \(g(x)\) and \(\overline{B}\) but not the other. And just as \(\overline{Z}\) therefore cannot be on the list \(Z_1\), \(Z_2\), …, \(\overline{B}\) cannot be in the range of \(g\).

También vale la pena comparar la prueba con la prueba de la Paradoja de Russell, Teorema 1.6.1. En efecto, el teorema de Cantor fue la inspiración para la propia paradoja de Russell.

Problema\(\PageIndex{1}\)

Demostrar que no puede haber una inyección\(g\colon \Pow{A} \to A\), para ningún conjunto\(A\). Pista: Supongamos que\(g\colon \Pow{A} \to A\) es inyectable. Considerar\(D = \Setabs{g(B)}{B \subseteq A \text{ and } g(B) \notin B}\). Vamos\(x = g(D)\). Utilizar el hecho de que\(g\) es inyectivo para derivar una contradicción.