1.6: Cardenalidad

\(\newcommand{\R}{\mathbb{R}}\)\(\newcommand{\N}{\mathbb{N}}\)\(\newcommand{\Z}{\mathbb{Z}}\)\(\newcommand{\Q}{\mathbb{Q}}\)\(\newcommand{\A}{\mathbb{A}}\)\(\newcommand{\bs}{\boldsymbol}\)

Teoría Básica

Definiciones

Supongamos que\(\mathscr{S}\) es una colección no vacía de conjuntos. Definimos una relación\(\approx\) sobre\(\mathscr{S}\)\(A \approx B\) si y solo si existe una función uno a uno\(f\) de\(A\) hacia\(B\). La relación\(\approx\) es una relación de equivalencia sobre\(\mathscr{S}\). Es decir, para todos\( A, \, B, \, C \in \mathscr{S} \),

1. \( A \approx A \), la propiedad reflexiva
2. Si\( A \approx B \) entonces\( B \approx A \), la propiedad simétrica
3. Si\( A \approx B \) y\( B \approx C \ \) entonces\( A \approx C \), la propiedad transitiva

Prueba

1. La función de identidad\( I_A \) en\( A \), dada por\( I_A(x) = x \) for\( x \in A \), mapea\( A \) uno a uno en\( A \). De ahí\( A \approx A \)
2. Si\( A \approx B \) entonces existe una función uno a uno\( f \) de\( A \) hacia\( B \). Pero entonces\( f^{-1} \) es una función uno a uno de\( B \) en adelante\( A \), entonces\( B \approx A \)
3. Supongamos que\( A \approx B \) y\( B \approx C \). Luego existe una función uno a uno\( f \) desde\( A \) hacia\( B \) y una función uno a uno\( g \) desde\( B \) hacia\( C \). Pero entonces\( g \circ f \) es una función uno a uno de\( A \) en adelante\( C \), entonces\( A \approx C \).

Una función uno a uno\( f \) de\( A \) hacia a veces\( B \) se llama biyección. Así si\( A \approx B \) entonces\( A \) y\( B \) están en correspondencia uno a uno y se dice que tienen la misma cardinalidad. Las clases de equivalencia bajo esta relación de equivalencia capturan la noción de tener el mismo número de elementos.

Vamos\(\N_0 = \emptyset\), y para\(k \in \N_+\), vamos\(\N_k = \{0, 1, \ldots k - 1\}\). Como siempre,\( \N = \{0, 1, 2, \ldots\} \) es el conjunto de todos los números naturales.

Supongamos que\( A \) es un conjunto.

1. \(A\)es finito si\(A \approx \N_k\) para algunos\(k \in \N\), en cuyo caso\(k\) es la cardinalidad de\(A\), y escribimos\(\#(A) = k\).
2. \( A \)es infinito si no\( A \) es finito.
3. \( A \)es contablemente infinito si\( A \approx \N \).
4. \( A \)es contable si\( A \) es finito o contablemente infinito.
5. \( A \)es incontable si no\( A \) es contable.

En la parte (a),\(\N_k\) pensemos como un conjunto de referencia con\(k\) elementos; cualquier otro conjunto con\(k\) elementos debe ser equivalente a éste. Estudiaremos la cardinalidad de los conjuntos finitos en las siguientes dos secciones sobre Medida de conteo y Estructuras combinatorias. En esta sección, nos concentraremos principalmente en conjuntos infinitos. En la parte (d), un conjunto contable es aquel que se puede enumerar o contar poniendo los elementos en correspondencia uno a uno con\( \N_k \) para algunos\( k \in \N \) o con todos\( \N \). Un conjunto incontable es aquel que no se puede contar así. Los conjuntos contables juegan un papel especial en la teoría de la probabilidad, como en muchas otras ramas de las matemáticas. Apriori, no está claro que haya conjuntos incontables, pero pronto veremos ejemplos.

Ejemplos Preliminares

Si\( S \) es un conjunto, recuerde que\(\mathscr{P}(S)\) denota el conjunto de potencia de\(S\) (el conjunto de todos los subconjuntos de\(S\)). Si\( A \) y\( B \) son conjuntos, entonces\( A^B \) es el conjunto de todas las funciones desde\( B \) dentro\( A \). En particular,\(\{0, 1\}^S\) denota el conjunto de funciones desde\(S\) dentro\(\{0, 1\}\).

Si\(S\) es un conjunto entonces\(\mathscr{P}(S) \approx \{0, 1\}^S\).

Prueba

El mapeo que toma un conjunto\(A \in \mathscr{P}(S)\) en su función de indicador\(\boldsymbol{1}_A \in \{0, 1\}^S\) es uno a uno y sobre. Específicamente, si\( A, \, B \in \mathscr{P}(S) \) y\( \bs{1}_A = \bs{1}_B \), entonces\( A = B \), entonces el mapeo es uno a uno. Por otro lado, si\( f \in \{0, 1\}^S \) entonces\( f = \bs{1}_A \) donde\( A = \{x \in S: f(x) = 1\} \). De ahí que el mapeo esté en.

A continuación se presentan algunos ejemplos de conjuntos contabilizadamente infinitos.

Los siguientes conjuntos son contablemente infinitos:

1. El conjunto de números naturales pares\(E = \{0, 2, 4, \ldots\}\)
2. El conjunto de números enteros\(\Z\)

Prueba

1. La función\(f: \N \to E\) dada por\(f(n) = 2 n\) es uno a uno y on.
2. La función\(g: \N \to \Z\) dada por\(g(n) = \frac{n}{2}\) si\( n \) es par y\(g(n) = -\frac{n + 1}{2}\) si\( n \) es impar, es uno a uno y on.

En un nivel, podría parecer que\( E \) tiene sólo la mitad de elementos que\( \N \) while\( \Z \) tiene el doble de elementos que\( \N \). como muestra el resultado anterior, ese punto de vista es incorrecto:\( \N \),\( E \), y\( \Z \) todos tienen la misma cardinalidad (y son contablemente infinitos ). El siguiente ejemplo muestra que efectivamente hay conjuntos incontables.

Si\(A\) es un conjunto con al menos dos elementos entonces\(S = A^\N\), el conjunto de todas las funciones de\(\N\) a\(A\), es incontable.

Prueba

La prueba es por contradicción, y utiliza un bonito truco conocido como el método de diagonalización. Supongamos que\(S\) es contablemente infinito (claramente no es finito), para que los elementos de\(S\) puedan ser enumerados:\(S = \{f_0, f_1, f_2, \ldots\}\). Dejar\(a\) y\(b\) denotar elementos distintos de\(A\) y definir\(g: \N \to A\) por\(g(n) = b\) si\(f_n(n) = a\) y\(g(n) = a\) si\(f_n(n) \ne a\). Tenga en cuenta que\(g \ne f_n\) para cada uno\(n \in \N\), así\(g \notin S\). Esto contradice el hecho de que\(S\) es el conjunto de todas las funciones desde\(\N\) dentro\(A\).

Subconjuntos de Conjuntos Infinitos

Seguramente un conjunto debe ser tan mínimo tan grande como cualquiera de sus subconjuntos, en términos de cardinalidad. Por otro lado, con el ejemplo (4), el conjunto de números naturales\( \N \), el conjunto de números naturales pares\( E \) y el conjunto de enteros\( \Z \) tienen exactamente la misma cardinalidad, aunque sea\( E \subset \N \subset \Z \). En esta subsección, exploraremos algunos resultados interesantes y algo paradójicas que se relacionan con subconjuntos de conjuntos infinitos. En el camino, veremos que el infinito contable es el más pequeño de los infinitos.

Si\(S\) es un conjunto infinito entonces\(S\) tiene un subconjunto infinito contable.

Prueba

Seleccione\(a_0 \in S\). Es posible hacer esto ya que\(S\) es infinito y por lo tanto no vacío. Inductivamente, habiendo elegido\(\{a_0, a_1, \ldots, a_{k-1}\} \subseteq S\), seleccione\(a_k \in S \setminus \{a_0, a_1, \ldots, a_{k-1}\}\). Nuevamente, es posible hacer esto ya que no\(S\) es finito. Manifestadamente,\(\{a_0, a_1, \ldots \}\) es un subconjunto contablemente infinito de\(S\).

Un conjunto\(S\) es infinito si y solo si\(S\) es equivalente a un subconjunto apropiado de\(S\).

Prueba

Si\(S\) es finito, entonces no\(S\) es equivalente a un subconjunto apropiado según el principio del casillero. Si\(S\) es infinito, entonces\(S\) tiene subconjunto contablemente infinito\(\{a_0, a_1, a_2, \ldots\}\) por el resultado anterior. Definir la función\( f: S \to S \)\( f \left(a_n\right) = a_{2 n} \) por\(n \in \N\) y\( f(x) = x \) para\(x \in S \setminus \{a_0, a_1, a_2, \ldots\}\). Luego\( f \) mapea\(S\) uno a uno en\(S \setminus \{a_1, a_3, a_5, \ldots\}\).

Cuando\(S\) era infinito en la prueba del resultado anterior, no solo mapeamos\(S\) uno a uno en un subconjunto adecuado, en realidad tiramos un subconjunto contablemente infinito y seguimos manteniendo la equivalencia. De igual manera, podemos agregar un conjunto contablemente infinito a un conjunto infinito\(S\) sin cambiar la cardinalidad.

Si\(S\) es un conjunto infinito y\(B\) es un conjunto contable, entonces\(S \approx S \cup B\).

Prueba

Consideremos el caso más extremo donde\(B\) es contablemente infinito y disjunta de\(S\). Entonces\(S\) tiene un subconjunto contablemente infinito\(A = \{a_0, a_1, a_2, \ldots\}\) por el resultado anterior, y\(B\) puede ser enumerado, entonces\(B = \{b_0, b_1, b_2, \ldots\}\). Defina la función\( f: S \to S \cup B \) por\(f\left(a_n\right) = a_{n/2}\) si\( n \) es par,\( f\left(a_n\right) = b_{(n-1)/2} \) si\( n \) es impar y\( f(x) = x \) si\( x \in S \setminus \{a_0, a_1, a_2, \ldots\} \). Luego\( f \) mapea\( S \) uno a uno en\( S \cup B \).

En particular, si\(S\) es incontable y\(B\) es contable entonces\(S \cup B\) y\(S \setminus B\) tienen la misma cardinalidad que\(S\), y en particular son incontables. En términos de las dicotomías finito-infinito y contable-incontable, un conjunto es, en efecto, al menos tan grande como un subconjunto. Primero necesitamos un resultado preliminar.

Si\(S\) es contablemente infinito y\(A \subseteq S\) entonces\(A\) es contable.

Prueba

Basta con mostrar que si\( A \) es un subconjunto infinito de\( S \) entonces\( A \) es contablemente infinito. Dado que\(S\) es contablemente infinito, se puede enumerar:\(S = \{x_0, x_1, x_2, \ldots\}\). Dejar\(n_i\) ser el\(i\) th índice más pequeño tal que\(x_{n_i} \in A\). Entonces\(A = \{x_{n_0}, x_{n_1}, x_{n_2}, \ldots\}\) y por lo tanto es contablemente infinito.

Supongamos que\(A \subseteq B\).

1. Si\(B\) es finito entonces\(A\) es finito.
2. Si\(A\) es infinito entonces\(B\) es infinito.
3. Si\(B\) es contable entonces\(A\) es contable.
4. Si\(A\) es incontable entonces\(B\) es incontable.

Prueba

1. Esto queda claro a partir de la definición de un conjunto finito.
2. Este es el contrapositivo de (a).
3. Si\( A\) es finito, entonces\( A \) es contable. Si\( A \) es infinito, entonces\( B \) es infinito por (b) y por lo tanto es contablemente infinito. Pero entonces\( A \) es contablemente infinito por (9).
4. Este es el contrapositivo de (c).

Comparaciones por funciones uno a uno y sobre

Analizaremos más profundamente la cuestión general de cuándo un conjunto es al menos tan grande como otro, en el sentido de cardinalidad. No es sorprendente que esto conduzca eventualmente a un orden parcial sobre las clases de equivalencia de cardinalidad.

Primero tenga en cuenta que si existe una función que mapea un conjunto\(A\) uno a uno en un conjunto\(B\), entonces en cierto sentido, hay una copia de\(A\) contenido en\(B\). De ahí que\(B\) deba ser por lo menos tan grande como\(A\).

Supongamos que\(f: A \to B\) es uno a uno.

1. Si\(B\) es finito entonces\(A\) es finito.
2. Si\(A\) es infinito entonces\(B\) es infinito.
3. Si\(B\) es contable entonces\(A\) es contable.
4. Si\(A\) es incontable entonces\(B\) es incontable.

Prueba

Tenga en cuenta que los\(f\) mapas\(A\) uno a uno en\(f(A)\). De ahí\( A \approx f(A) \) y\(f(A) \subseteq B\). Los resultados ahora siguen de (10):

1. Si\( B \) es finito entonces\( f(A) \) es finito y por lo tanto\( A \) es finito.
2. Si\( A \) es infinito entonces\( f(A) \) es infinito y por lo tanto\( B \) es infinito.
3. Si\( B \) es contable entonces\( f(A) \) es contable y por lo tanto\( A \) es contable.
4. Si\( A \) es incontable entonces\( f(A) \) es incontable y por lo tanto\( B \) es incontable.

Por otro lado, si existe una función que mapea un conjunto\(A\) sobre un conjunto\(B\), entonces en cierto sentido, hay una copia de\(B\) contenido en\(A\). De ahí que\(A\) deba ser por lo menos tan grande como\(B\).

Supongamos que eso\(f: A \to B\) es sobre.

1. Si\(A\) es finito entonces\(B\) es finito.
2. Si\(B\) es infinito entonces\(A\) es infinito.
3. Si\(A\) es contable entonces\(B\) es contable.
4. Si\(B\) es incontable entonces\(A\) es incontable.

Prueba

Para cada uno\(y \in B\), selecciona un específico\(x \in A\) con\(f(x) = y\) (si eres persnickety, es posible que necesites invocar el axioma de elección). \(C\)Sea el conjunto de puntos elegidos. Luego\(f\) mapea\(C\) uno a uno en\(B\), entonces\( C \approx B \) y\(C \subseteq A\). Los resultados ahora siguen de (11):

1. Si\( A \) es finito entonces\( C \) es finito y por lo tanto\( B \) es finito.
2. Si\( B \) es infinito entonces\( C \) es infinito y por lo tanto\( A \) es infinito.
3. Si\( A \) es contable entonces\( C \) es contable y por lo tanto\( B \) es contable.
4. Si\( B \) es incontable entonces\( C \) es incontable y por lo tanto\( A \) es incontable.

El ejercicio anterior también podría probarse a partir del anterior, ya que si existe una función\(f\) mapeando\(A\) sobre\(B\), entonces existe una función que\(g\) mapea\(B\) uno a uno en\(A\). Esta dualidad se demuestra en la discusión del axioma de elección. Un corolario simple y útil de los dos teoremas anteriores\(B\) es que si es un conjunto dado contablemente infinito, entonces un conjunto\(A\) es contable si y solo si existe una función uno a uno\(f\) desde\(A\) dentro\(B\), si y solo si existe una función\(g\) de \(B\)sobre\(A\).

Si\(A_i\) es un conjunto contable para cada uno\(i\) en un conjunto de índices contables\(I\), entonces\(\bigcup_{i \in I} A_i\) es contable.

Prueba

Consideremos el caso más extremo en el que el conjunto de índices\(I\) es contablemente infinito. Dado que\( A_i \) es contable, existe una función\(f_i\) que se\(\N\) mapea\(A_i\) para cada uno\(i \in \N\). Vamos\(M = \left\{2^i 3^j: (i, j) \in \N \times \N\right\}\). Tenga en cuenta que los puntos en\( M \) son distintos, es decir,\( 2^i 3^j \ne 2^m 3^n \) si\( (i, j), \, (m, n) \in \N \times \N \) y\( (i, j) \ne (m, n) \). De ahí\(M\) que sea infinito, y desde entonces\( M \subset \N \),\( M \) es contablemente infinito. La función\(f\) dada por\(f\left(2^i 3^j\right) = f_i(j)\) for\((i, j) \in \N \times \N\) maps\( M \) onto\( \bigcup_{i \in I} A_i \), y por lo tanto este último conjunto es contable.

Si\(A\) y\(B\) son contables entonces\(A \times B\) es contable.

Prueba

Existe una función\(f\) que se mapea\(\N\) sobre\(A\), y existe una función\(g\) que se mapea\(\N\) sobre\(B\). Nuevamente, recordemos que eso\(M\) es contablemente infinito.\(M = \left\{2^i 3^j: (i, j) \in \N \times \N \right\}\) Definir\(h: M \to A \times B\) por\(h\left(2^i 3^j\right) = \left(f(i), g(j)\right)\). Luego se\(h\)\( M \) mapea\( A \times B \) y por lo tanto este último conjunto es contable.

El último resultado también podría probarse a partir del anterior, al señalar que

\[ A \times B = \bigcup_{a \in A} \{a\} \times B \]

Ambas pruebas funcionan porque el conjunto\(M\) es esencialmente una copia de\(\N \times \N\), incrustado dentro de\(\N\). El último teorema generaliza a la afirmación de que un producto finito de conjuntos contables sigue siendo contable. Pero, a partir de (5), un producto de infinitamente muchos conjuntos (con al menos 2 elementos cada uno) será incontable.

El conjunto de números racionales\(\Q\) es contablemente infinito.

Prueba

Los conjuntos\(\Z\) y\(\N_+\) son contablemente infinitos y por lo tanto el conjunto\(\Z \times \N_+\) es contablemente infinito. La función\(f: \Z \times \N_+ \to \Q\) dada por\(f(m, n) = \frac{m}{n}\) es onto.

Un número real es algebraico si es la raíz de una función polinómica (de grado 1 o más) con coeficientes enteros. Los números racionales son algebraicos, al igual que las raíces racionales de los números racionales (cuando se definen). Además, los números algebraicos se cierran bajo suma, multiplicación y división. Un número real es trascendental si no es algebraico. Los números\(e\) y\(\pi\) son trascendentales, pero no conocemos muchos otros números trascendentales por nombre. No obstante, como veremos, la mayoría (en el sentido de cardinalidad) los números reales son trascendentales.

El conjunto de números algebraicos\(\A\) es contablemente infinito.

Prueba

Dejar\(\Z_0 = \Z \setminus \{0\}\) y dejar\(\Z_n = \Z^{n-1} \times \Z_0\) para\(n \in \N_+\). El conjunto\(\Z_n\) es contablemente infinito para cada uno\(n\). Vamos\(C = \bigcup_{n=1}^\infty \Z_n\). Piense en\(C\) como el conjunto de coeficientes y anote que\(C\) es contablemente infinito. Dejar\(P\) denotar el conjunto de polinomios de grado 1 o más, con coeficientes enteros. La función\(C\) se\((a_0, a_1, \ldots, a_n) \mapsto a_0 + a_1\,x + \cdots + a_n\,x^n\) mapea sobre\(P\), y por lo tanto\( P \) es contable. Para\( p \in P \), vamos a\( A_p \) denotar el conjunto de raíces de\( p \). Un polinomio de grado\(n\) en\(P\) tiene como máximo\(n\) raíces, por el teorema fundamental del álgebra, por lo que en particular\( A_p \) es finito para cada uno\( p \in P \). Por último, tenga en cuenta que\( \A = \bigcup_{p \in P} A_p \) y así\( \A \) es contable. Por supuesto\( \N \subset \A \), así\( \A \) es contablemente infinito.

Ahora veamos algunos conjuntos incontables.

El intervalo\([0, 1)\) es incontable.

Prueba

Recordemos que\( \{0, 1\}^{\N_+} \) es el conjunto de todas las funciones desde\( \N_+ \) dentro\(\{0, 1\}\), que en este caso, se puede considerar como secuencias infinitas o cadenas de bits:\[ \{0, 1\}^{\N_+} = \left\{\bs{x} = (x_1, x_2, \ldots): x_n \in \{0, 1\} \text{ for all } n \in \N_+\right\} \] By (5), este conjunto es incontable. Let\( N = \left\{\bs{x} \in \{0, 1\}^{\N_+}: x_n = 1 \text{ for all but finitely many } n\right\}\), el conjunto de cadenas de bits que finalmente terminan en todos los 1s. Tenga en cuenta que\( N = \bigcup_{n=1}^\infty N_n \) donde\( N_n = \left\{\bs{x} \in \{0, 1\}^{\N_+}: x_k = 1 \text{ for all } k \ge n\right\} \). Claramente\( N_n \) es finito para todos\( n \in \N_+ \), así\( N \) es contable, y por lo tanto\( S = \{0, 1\}^{\N_+} \setminus N \) es incontable. De hecho,\( S \approx \{0, 1\}^{\N_+} \). La función\[\bs{x} \mapsto \sum_{n = 1}^\infty \frac{x_n}{2^n} \] mapea\( S \) uno a uno en\( [0, 1) \). En palabras, cada número en\( [0, 1) \) tiene una expansión binaria única en forma de una secuencia en\( S \). De ahí\( [0, 1) \approx S \) y en particular, es incontable. La razón para eliminar las cadenas de bits que terminan en 1s es asegurar la singularidad, de modo que el mapeo sea uno a uno. La cadena de bits\( x_1 x_2 \cdots x_k 0 1 1 1\cdots \) corresponde al mismo número\( [0, 1) \) que la cadena de bits\( x_1 x_2 \cdots x_k 1 0 0 0\cdots \).

Los siguientes conjuntos tienen la misma cardinalidad, y en particular todos son incontables:

1. \(\R\), el conjunto de números reales.
2. Cualquier intervalo\(I\) de\(\R\), siempre y cuando el intervalo no esté vacío o un solo punto.
3. \(\R \setminus \Q\), el conjunto de números irracionales.
4. \(\R \setminus \A\), el conjunto de números trascendentales.
5. \(\mathscr{P}(\N)\), el conjunto de poder de\(\N\).

Prueba

1. El mapeo\( x \mapsto \frac{2 x - 1}{x (1 - x)} \) mapea\( (0, 1) \) uno a uno sobre\( \R \) así\( (0, 1) \approx \R \). Pero\( (0, 1) = [0, 1) \setminus \{0\} \), así\( (0, 1] \approx (0, 1) \approx \R \), y todos estos conjuntos son incontables por el resultado anterior.
2. Supongamos\( a, \, b \in \R \) y\( a \lt b \). El mapeo\( x \mapsto a + (b - a) x \) mapea\( (0, 1) \) uno a uno sobre\( (a, b) \) y por lo tanto\( (a, b) \approx (0, 1) \approx \R \). También,\( [a, b) = (a, b) \cup \{a\} \),\( (a, b] = (a, b) \cup\{b\} \), y\( [a, b] = (a, b) \cup \{a, b\} \), entonces\( (a, b) \approx [a, b) \approx (a, b] \approx [a, b]\approx \R \). La función\( x \mapsto e^x \) mapea\( \R \) uno a uno en\( (0, \infty) \), entonces\( (0, \infty) \approx \R \). Para\( a \in \R \), la función\( x \mapsto a + x \) mapea\( (0, \infty) \) uno a uno en\( (a, \infty) \) y el mapeo\(x \mapsto a - x \) mapea\( (0, \infty) \) uno a uno en\( (-\infty, a) \) así\( (a, \infty) \approx (-\infty, a) \approx (0, \infty) \approx \R \). A continuación,\( [a, \infty) = (a, \infty) \cup \{a\} \) y\( (-\infty, a] = (-\infty, a) \cup \{a\} \), entonces\( [a, \infty) \approx (-\infty, a] \approx \R \).
3. \( \Q \)es contablemente infinito, entonces\( \R \setminus \Q \approx \R \).
4. Del mismo modo,\( \A \) es contablemente infinito, así\( \R \setminus \A \approx \R \).
5. Si\( S \) es contablemente infinito, entonces por el resultado anterior y (a),\( \mathscr{P}(S) \approx \mathscr{P}(\N_+) \approx \{0, 1\}^{\N_+} \approx [0, 1) \).

El orden parcial de la cardenalidad

Supongamos que\(\mathscr{S}\) es una colección no vacía de conjuntos. Definimos la relación\(\preceq\) on\(\mathscr{S}\) por\(A \preceq B\) si y solo si existe una función uno a uno\(f\) de\(A\) dentro\(B\), si y solo si existe una función\(g\) de\(B\) hacia\(A\). A la luz del subapartado anterior,\(A \preceq B\) debe plasmar la noción que\(B\) es al menos tan grande como\(A\), en el sentido de cardinalidad.

La relación\(\preceq\) es reflexiva y transitiva.

Prueba

Para\( A \in \mathscr{S} \), la función de identidad\( I_A: A \to A \) dada por\( I_A(x) = x \) es uno a uno (y también on), entonces\( A \preceq A \). Supongamos eso\( A, \, B, \, C \in \mathscr{S} \) y eso\( A \preceq B \) y\( B \preceq C \). Entonces existen funciones uno-a-uno\( f: A \to B \) y\( g: B \to C \). Pero entonces\( g \circ f: A \to C \) es uno a uno, entonces\( A \preceq C \).

Así, podemos usar la construcción en la sección sobre Relaciones de Equivalencia para definir primero una relación de equivalencia sobre\(\mathscr{S}\), y luego extender\(\preceq\) a un verdadero orden parcial sobre la colección de clases de equivalencia. La única pregunta que queda es si la relación de equivalencia que obtenemos de esta manera es la misma que la que venimos utilizando en nuestro estudio de la cardinalidad. Reformulada, la pregunta es la siguiente: Si existe una función uno a uno desde\(A\) dentro\(B\) y una función uno a uno desde\(B\) dentro\(A\), ¿existe necesariamente una función uno a uno de\(A\) hacia dentro\(B\)? Afortunadamente, la respuesta es sí; el resultado se conoce como el Teorema de Schröder-Bernstein, llamado así por Ernst Schröder y Felix Bernstein.

Si\(A \preceq B\) y\(B \preceq A\) entonces\(A \approx B\).

Prueba

La inclusión de conjunto\(\subseteq\) es un orden parcial sobre\(\mathscr{P}(A)\) (el conjunto de poder de\(A\)) con la propiedad que cada subcolección\(\mathscr{P}(A)\) tiene un supremo (es decir, la unión de la subcolección). Supongamos que\(f\) mapea\(A\) uno a uno en\(B\) y\(g\) mapea\(B\) uno a uno en\(A\). Definir la función\(h: \mathscr{P}(A) \to \mathscr{P}(A)\) por\(h(U) = A \setminus g[B \setminus f(U)]\) for\(U \subseteq A\). Entonces\(h\) va aumentando:\ begin {align} U\ subseteq V &\ implica f (U)\ subseteq f (V)\ implica B\ setmenos f (V)\ subseteq B\ setmenos f (U)\\ &\ implica g [B\ setmenos f (V)]\ subseteq g [B\ setmenos f (U)]\ implica A\ setmenos g [B\ setmenos f (U)]\ subseteq A\ setmenos g [B\ setmenos f (V)]\ end {align} Del teorema de punto fijo para conjuntos parcialmente ordenados, existe\(U \subseteq A\) tal que\(h(U) = U\). De ahí\(U = A \setminus g[B \setminus f(U)]\) y por lo tanto\(A \setminus U = g[B \setminus f(U)]\). Ahora defina\(F: A \to B\) por\(F(x) = f(x)\) si\(x \in U\) y\(F(x) = g^{-1}(x)\) si\(x \in A \setminus U\).

\( f \)mapea\( U \) uno a uno en\( f(U) \);\( g \) mapea\( B \setminus f(U) \) uno a uno en\( A \setminus U \)

A continuación mostramos que\( F \) es uno a uno. Supongamos que\( x_1, \, x_2 \in A \) y\( F(x_1) = F(x_2) \). Si\( x_1, \, x_2 \in U \) entonces es\( f(x_1) = f(x_2) \) así\( x_1 = x_2 \) ya que\( f \) es uno a uno. Si\( x_1, \, x_2 \in A \setminus U \) entonces es\( g^{-1}(x_1) = g^{-1}(x_2) \) así\( x_1 = x_2 \) ya que\( g^{-1} \) es uno a uno. Si\( x_1 \in U \) y\( x_2 \in A \setminus U \). Entonces\( F(x_1) = f(x_1) \in f(U) \) mientras\( F(x_2) = g^{-1}(x_2) \in B \setminus f(U) \), así\( F(x_1) = F(x_2) \) es imposible.

Por último demostramos que\( F \) está sobre. Vamos\( y \in B \). Si\( y \in f(U) \) entonces\( y = f(x) \) para algunos\( x \in U \) así\( F(x) = y \). Si\( y \in B \setminus f(U) \) entonces\( x = g(y) \in A \setminus U \) es así\( F(x) = g^{-1}(x) = y \).

Vamos a escribir\(A \prec B\) si\(A \preceq B\), pero\(A \not \approx B\), Es decir, existe una función uno-a-uno de\(A\) dentro\(B\), pero no existe una función de\(A\) en adelante\(B\). Tenga en cuenta que\(\prec\) tendría su significado habitual si se aplicara a las clases de equivalencia. Es decir,\([A] \prec [B]\) si y sólo si\([A] \preceq [B]\) pero\([A] \ne [B]\). Intuitivamente, por supuesto,\(A \prec B\) significa que\(B\) es estrictamente más grande que\(A\), en el sentido de cardinalidad.

\(A \prec B\)en cada uno de los siguientes casos:

1. \(A\)y\(B\) son finitos y\(\#(A) \lt \#(B)\).
2. \(A\)es finito y\(B\) es contablemente infinito.
3. \(A\)es contablemente infinito y\(B\) es incontable.

Cerramos nuestra discusión con la observación de que para cualquier conjunto, siempre hay un conjunto mayor.

Si\(S\) es un conjunto entonces\(S \prec \mathscr{P}(S)\).

Prueba

Primero, es trivial mapear\(S\) uno a uno en\(\mathscr{P}(S)\); solo mapear\(x\) a\(\{x\}\). Supongamos ahora que\(S\) se\(f\) mapea\(\mathscr{P}(S)\) y deja\(R = \{x \in S: x \notin f(x)\}\). Ya que\(f\) está en, existe\(t \in S\) tal que\(f(t) = R\). Tenga en cuenta que\(t \in f(t)\) si y solo si\(t \notin f(t)\).

La prueba de que un conjunto no puede mapearse en su conjunto de poder es similar a la paradoja de Russell, llamada así por Bertrand Russell.

La hipótesis del continuum es la afirmación de que no existe un conjunto cuya cardinalidad esté estrictamente entre la de\(\N\) y\(\R\). La hipótesis del continuum en realidad comenzó como la conjetura del continuum, hasta que se demostró que era consistente con los axiomas habituales del sistema de números reales (por Kurt Gödel en 1940), e independiente de esos axiomas (por Paul Cohen en 1963).

Asumiendo la hipótesis del continuo, si\( S \) es incontable entonces existe\( A \subseteq S \) tal que\( A \) y\( A^c \) son incontables.

Prueba

Bajo la hipótesis del continuum, si\( S \) es incontable entonces\( [0, 1) \preceq S \). De ahí que exista una función uno-a-uno\( f: [0, 1) \to S \). Vamos\( A = f\left[0, \frac{1}{2}\right) \). Entonces\( A \) es incontable, y desde entonces\( f\left[\frac{1}{2}, 1\right) \subseteq A^c \),\( A^c \) es incontable.

Hay una prueba más complicada del último resultado, sin la hipótesis del continuo y solo usando el axioma de elección.