9.5: Conjuntos contables

Para su uso en la prueba de teoremas, las ideas encontradas en la discusión del Hotel Infinity necesitan ser enunciadas de manera más formal. Empecemos por las definiciones que forman la base del tema.

Definición\(9.6.1\).

Supongamos\(A\) y\(B\) son conjuntos.

1. \(A\)y\(B\) tienen la misma cardinalidad si hay una biyección de\(A\) a\(B\).
2. \(A\)es contablemente infinito si tiene la misma cardinalidad que\(\mathbb{N}^{+}\).
3. \(A\)es contable si\(A\) es finito o\(A\) es infinitamente infinito.
4. \(A\)es incontable iff no\(A\) es contable.

Observaciones\(9.5.2\).

1. En la terminología del apartado anterior, un conjunto es contable si y sólo si todos sus elementos pueden recibir habitaciones en Hotel Infinity (ver Ejercicio\(9.5.6(3)\)).
2. Si te dicen que demuestres que\(A\) es contablemente infinito, directamente desde la definición, entonces deberías encontrar una bijección de\(A\) a\(\mathbb{N}^{+}\). Sin embargo, debido a que es tan conocido que la inversa de una biyección es una biyección, es aceptable encontrar una biyección de\(\mathbb{N}^{+}\) a\(A\), en su lugar.

Observaciones\(9.5.3\).

Uno puede (y debería) pensar en conjuntos contables como los conjuntos cuyos elementos se pueden enumerar en una secuencia. La secuencia puede tener solo finitamente muchos términos, o puede continuar para siempre:

1. Un conjunto\(A\) es finito si sus elementos se pueden enumerar en una secuencia\(a_{1}, a_{2}, \ldots, a_{n}), for some \(n\).
2. Si los elementos de se\(A\) pueden enumerar en una secuencia infinita\(a_{1}, a_{2}, a_{3}, \ldots), then we may define a bijection \(f: \mathbb{N}^{+} \rightarrow A) by \(f(i)=a_{i}\). Por lo tanto,\(A\) es contablemente infinito.
3. Por el contrario, si\(A\) es contablemente infinito, entonces hay una biyección que\(f: \mathbb{N}^{+} \rightarrow A), so letting \(a_{i}=f(i)\) produce una secuencia infinita\(a_{1}, a_{2}, a_{3}, \ldots) that lists the elements of \(A\).

Ejercicio\(9.5.4\).

Definir una relación binaria\(\approx\) en la colección de todos los conjuntos mediante\[A \approx B \quad \text { iff } \quad A \text { and } B \text { have the same cardinality. }\]

1. Demostrar que\(\approx\) es una relación de equivalencia.
2. ¿Cuál es la clase de equivalencia\(\mathbb{N}^{+}\)?

El siguiente resultado fundamental muestra que los conjuntos infinitos más pequeños son los contables:

Teorema\(9.5.5\).

1. Cada conjunto infinito contiene un subconjunto infinitamente contable.
2. Cada subconjunto de un conjunto contable es contable.

Prueba

1. Dado un conjunto infinito\(A\), basta con construir una secuencia infinita\(a_{1}, a_{2}, a_{2}, \ldots\) de elementos distintos de\(A\), pues entonces\(\left\{a_{1}, a_{2}, a_{3}, \ldots\right\}\) es un subconjunto contablemente infinito de\(A\).
   1. Ya que\(A\) es infinito, desde luego no está vacío, por lo que tiene algunos elementos. \(a_{1}\)Sea cualquiera de estos elementos de\(A\).
   2. Ya que\(A\) es infinito, sabemos que a1 no es su único elemento. Dejar\(a_{2}\) ser cualquier elemento de\(A\) otro que no sea\(a_{1}\). Entonces\(a_{1}\) y\(a_{2}\) son elementos distintos de\(A\).
   3. Ya que\(A\) es infinito, lo sabemos\(a_{1}\) y no\(a_{2}\) son sus únicos elementos. Dejar\(a_{3}\) ser cualquier elemento de\(A\) otro que no sea\(a_{1}\) y\(a_{2}\). Entonces\(a_{1}\),\(a_{2}\), y\(a_{3}\) son elementos distintos de
      A.
      .
      .
      i. Como\(A\) es infinito, sabemos que no\(a_{1}, a_{2}, a_{3}, \ldots, a_{i-1}\) son sus únicos elementos. Dejar\(a_{i}\) ser cualquier elemento de\(A\) otro que no sea\(a_{1}, a_{2}, a_{3}, \ldots, a_{i-1}\). Entonces los elementos\(a_{1}, a_{2}, a_{3}, \ldots, a_{i}\) son distintos.
      .
      .
      .

Continuando con este proceso inductivo produce la secuencia infinita deseada\(a_{1}, a_{2}, a_{3}, \ldots\) de distintos elementos de\(A\).

2. Dado un subconjunto\(M\) de un conjunto contable\(A\), deseamos mostrar que\(M\) es contable. Podemos suponer que\(M\) es infinito, pues de lo contrario es obviamente contable. Por lo que deseamos mostrar que hay una secuencia\(m_{1}, m_{2}, m_{3}, \ldots\) que enumera todos los elementos de\(M\).
   Para simplificar la notación, consideremos primero el caso donde\(A=\mathbb{N}^{+}\).
   1. Caso 1. Asumir\(A=\mathbb{N}^{+}\). Let
      1. \(m_{1}\)ser el elemento más pequeño de\(M\),
      2. \(m_{2}\)ser el elemento más pequeño de\(M \backslash\left\{m_{1}\right\}\),
      3. \(m_{3}\)ser el elemento más pequeño de\(M \backslash\left\{m_{1}, m_{2}\right\}\),
      4. \(m_{4}\)ser el elemento más pequeño de\(M \backslash\left\{m_{1}, m_{2}, m_{3}\right\}\),
         .
         .
         .
         (i)\(m_{i}\) ser el elemento más pequeño de\(M \backslash\left\{m_{1}, m_{2}, \ldots, m_{i-1}\right\}\). (En otras palabras,\(m_{i}\) es el elemento más pequeño de\(M\) que no está en\(\left\{m_{1}, m_{2}, \ldots, m_{i-1}\right\}\).)
         .
         .
         .

Para cada uno\(m \in M), notice that if we let \(k\) el número de elementos de\(M\) que son menores que\(m\), entonces\(m_{k+1}=m\). Por lo tanto, cada elemento\(m\) de\(M\) aparece en la secuencia\(m_{1}, m_{2}, m_{3}, \ldots\).

2. Caso 2. El caso general. Esto se deja como ejercicio.

Ejercicio\(9.5.6\).

1. Completa el Caso 2 en la prueba del Teorema\(9.5.5\). [Pista: Si\(M\) es infinito, entonces\(A\) debe ser infinito (¿por qué?). Enumerar los elementos de\(A\) en una secuencia\(a_{1}, a_{2}, a_{3}, \ldots\), y aplicar el argumento del Caso 1.]
2. Supongamos que eso\(f: A \rightarrow B\), eso\(f\) es uno a uno, y eso\(B\) es contable. Demostrar que\(A\) es contable.
   [Pista: Si no\(f\) está en, querrá usar el hecho de que cada subconjunto de un conjunto contable es contable.]
3. Mostrar que un conjunto\(A\) es contable si existe una función uno a uno\(f: A \rightarrow \mathbb{N}^{+}\).

OBSERVACIÓN\(9.5.7\).

Los matemáticos piensan que los conjuntos contables son pequeños —aunque puedan ser infinitos, son casi como conjuntos finitos. Considere las siguientes propiedades básicas de los conjuntos finitos:

1. Cualquier subconjunto de un conjunto finito es finito.
2. La unión de dos conjuntos finitos es finita.
3. De manera más general, la unión de finitamente muchos conjuntos finitos es finita.
4. Si tienes dos conjuntos finitos, entonces puedes hacer solo finitamente muchos pares ordenados a partir de ellos. (Es decir, el producto cartesiano de dos conjuntos finitos es finito.)
5. Si solo tienes finitamente muchos dardos para lanzar, entonces solo puedes golpear finitamente muchas cosas con ellos. Es decir, si\(f: A \rightarrow B\), y\(A\) es finito, entonces la imagen\(f(A)\) es finita

Todas las aseveraciones anteriores siguen siendo ciertas cuando la palabra “finito” es reemplazada por “contable”. La primera aseveración se estableció en Tm. \(9.5.5(2)\); los otros están contenidos en el siguiente teorema importante:

Teorema\(9.5.8\).

1. Una unión contable de conjuntos contables es contable.
2. El producto cartesiano de dos conjuntos contables es contable.
3. La imagen de un conjunto contable es contable.

OBSERVACIÓN\(9.5.9\).

Aquí hay declaraciones más precisas de las aseveraciones del Teorema\(9.5.8\):

1. Si\(A_{1}, A_{2}, A_{3}, \ldots\) hay alguna secuencia de conjuntos contables, entonces la unión\[\bigcup_{i=1}^{\infty} A_{i}=A_{1} \cup A_{2} \cup A_{3} \cup \cdots\]
   es contable. Además, si\(A_{1}, A_{2}, A_{3}, \ldots, A_{n}\) hay alguna secuencia finita de conjuntos contables, entonces la unión\[\bigcup_{i=1}^{n} A_{i}=A_{1} \cup A_{2} \cup A_{3} \cup \cdots \cup A_{n}\]
   es contable.
2. Si\(A\) y\(B\) son conjuntos contables, entonces\(A \times B\) es contable.
3. Si\(f: A \rightarrow B\), y\(A\) es contable, entonces\(f(A)\) es contable.

Prueba

1. Dada ya sea una secuencia infinita\(A_{1}, A_{2}, A_{3}, \ldots\) de conjuntos contables, o una secuencia finita\(A_{1}, A_{2}, A_{3}, \ldots, A_{n}\), An de conjuntos contables, deseamos mostrar que la unión de los conjuntos es contable. Los subconjuntos de un conjunto contable son contables, por lo que no hay ningún daño en asumir:
   • la secuencia es infinita (porque agregar términos adicionales a la secuencia hará que la unión sea más grande), y
   • cada uno de los conjuntos es infinito (porque reemplazar\(A_{i}\) con un superconjunto infinito hará que la unión sea más grande).

Ahora bien, el método de numeración de Eg. \(9.4.3(7)\)muestra que hay una función onto\(g: \mathbb{N}^{+} \rightarrow \bigcup_{i=1}^{\infty} A_{i}\). Entonces, a partir del 3., concluimos que\(\bigcup_{i=1}^{\infty} A_{i}\) es contable.

2. Dados conjuntos contables\(A\) y\(B\), deseamos mostrar que\(A \times B\) es contable. Los subconjuntos de un conjunto contable son contables, por lo que no hay daño en asumir que\(A\) y\(B\) son infinitos (porque reemplazar A y B con superconjuntos infinitos hará que el producto cartesiano sea más grande). Let
   • \(a_{1}, a_{2}, a_{3}, \ldots\)ser una lista de los elementos de\(A\), y
   • \(b_{1}, b_{2}, b_{3}, \ldots\)ser una lista de los elementos de\(B\),

Entonces los elementos de\(A \times B\) se listan en la siguiente tabla (o matriz):\ [\ begin {array} {cccccc}
\ left (a_ {1}, b_ {1}\ right) &\ left (a_ {1}, b_ {2}\ right) &\ left (a_ {1}, b_ {3}\ right) &\ left (a_ {1}, b_ {4}\ derecha) &\ izquierda (a_ {1}, b_ {5}\ derecha) &\ cdots\
\ izquierda (a_ {2}, b_ {1}\ derecha) &\ izquierda (a_ {2}, b_ {2}\ derecha) &\ izquierda (a_ {2}, b_ {3}\ derecha) &\ izquierda (a_ {2}, b_ {4}\ derecha) &\ izquierda (a_ {2}, b_ {5}\ derecha) &\ cdots\
\ izquierda (a_ {3}, b_ {1}\ derecha) &\ izquierda (a_ {3}, b_ {2}\ derecha) &\ izquierda (a_ {3}, b_ {3}\ derecha) &\ izquierda (a_ {3}, b_ {4}\ derecha) & ;\ izquierda (a_ {3}, b_ {5}\ derecha) &\ cdots\
\ izquierda (a_ {4}, b_ {1}\ derecha) &\ izquierda (a_ {4}, b_ {2}\ derecha) &\ izquierda (a_ {4}, b_ {3}\ derecha) &\ izquierda (a_ {4}, b_ {4} derecha\) &\ izquierda (a_ {4}, b_ {5}\ derecha) &\ cdots\
\ izquierda (a_ {5}, b_ {1}\ derecha) &\ izquierda (a_ {5}, b_ {2}\ derecha) & ;\ izquierda (a_ {5}, b_ {3}\ derecha) &\ izquierda (a_ {5}, b_ {4}\ derecha) &\ izquierda (a_ {5}, b_ {5}\ derecha) &\ cdots\\ vdots &
\ vdots &\ vdots &\ vdots &\ vdots &\ vdots &\ ddots
\ end {array}\]

El método de numeración de Eg. \(9.4.3(7)\)define una biyección de\(A \times B \text { to } \mathbb{N}^{+}\). Así\(A \times B\) es contable.

3. Supongamos\(f: A \rightarrow B\), y\(A\) es contable. Al reemplazar\(B\) con\(f(A)\), podemos asumir que\(f\) está en; entonces deseamos demostrar que\(B\) es contable. Por Ejercicio\(9.5.6(2)\), basta con definir una función uno-a-uno\(g: B \rightarrow A\). La función\(f\) es onto, entonces, para cada uno\(b \in B\), hay alguna\(a \in A\), tal que\(f(a)=b\); así, para cada uno\(b \in B\), podemos\(g(b)\) elegir ser un elemento de\(A\) tal que\[f(g(b))=b\]
   Entonces\(g: B \rightarrow A\), y todo lo que queda es demostrar que g es uno- a-uno. Dado\(b_{1}, b_{2} \in B\), tal que\(g\left(b_{1}\right)=g\left(b_{2}\right)\), tenemos\(f\left(g\left(b_{1}\right)\right)=b_{1}\) y\(f\left(g\left(b_{2}\right)\right)=b_{2}\). Por lo tanto,\[b_{1}=f\left(g\left(b_{1}\right)\right)=f\left(g\left(b_{2}\right)\right)=b_{2}\]
   Así\(g\) es uno-a-uno, según se desee.

Los teoremas de esta sección facilitan mostrar que muchos conjuntos son contables. Aquí hay algunos ejemplos importantes:

Ejercicio\(9.5.10\).

Demostrar que cada uno de los siguientes conjuntos es contable.

1. \(\mathbb{N}^{+}\).
2. \(\mathbb{N}\). [Pista:\(\mathbb{N}=\mathbb{N}^{+} \cup\{0\}\).]
3. \(\mathbb{Z}\). [Pista: Vamos\(\mathbb{Z}^{-}=\{n \in \mathbb{Z} \mid n<0\}\), entonces\(\mathbb{Z}=\mathbb{N} \cup \mathbb{Z}^{-}\). El conjunto\(\mathbb{Z}^{−}\) es la imagen de\(\mathbb{N}^{+}\) debajo de una función.]
4. \(\mathbb{Q}\). [Pista: Dejar\(\mathbb{Z}^{+}\) ser el conjunto de enteros positivos, así\(\mathbb{Q}\) es la imagen de\(\mathbb{Z} \times \mathbb{Z}^{\times}\) debajo de la función\(f(a, b)=a / b\).]

Es muy importante recordar que\(\mathbb{Q}\) es contable. Dado que\(\mathbb{N}\) y\(\mathbb{Z}\) son subconjuntos de\(\mathbb{Q}\), esto implica eso\(\mathbb{N}\) y también\(\mathbb{Z}\) son contables.

Ejercicio\(9.5.11\).

1. Supongamos que\(A\) es contablemente infinito, y\(b \notin A\). Mostrar, directamente desde la definición, que\(A \cup\{b\}\) es contablemente infinito.
2. Supongamos que\(A\) es contablemente infinito, y\(a \in A\). Mostrar, directamente desde la definición, que\(A \backslash\{a\}\) es contablemente infinito.
3. Supongamos\(A\) y\(B\) son contablemente infinitos y disjuntos. Mostrar, directamente desde la definición, que\(A \cup B\) es contablemente infinito.
4. Supongamos\[A_{1} \text { is disjoint from } B_{1}, \quad A_{1} \text { and } A_{2} \text { have the same cardinality, }\]
   \[A_{2} \text { is disjoint from } B_{2}, \text { and } B_{1} \text { and } B_{2} \text { have the same cardinality. }\]
   Mostrar que (\(A_{1} \cup B_{1}\)) tiene la misma cardinalidad que (\(A_{2} \cup B_{2}\)).
5. Supongamos que\(A\) es infinito. Mostrar que hay un subconjunto propio\(B\) de\(A\), tal que\(B\) tiene la misma cardinalidad que\(A\). [Pista: Combina el teorema\(9.5.5(1)\) con los ejercicios (2) y (4).]

OTRA TERMINOLOGÍA.

Algunos matemáticos no consideran que los conjuntos finitos sean “contables”, por lo que los términos “contable” y “contablemente infinito” son sinónimos de ellos. Entonces, se dice que un conjunto que es finito o contablemente infinito es “a lo sumo contable”. Otros matemáticos dicen que un conjunto contablemente infinito es “denumerable.