3.2: Conjuntos contables e incontables
- Page ID
- 108962
Se dice que una función\(\varphi: A \rightarrow B\) es una correspondencia uno a uno si\(\varphi\) es tanto uno a uno como a uno.
Decimos conjuntos\(A\) y\(B\) tenemos la misma cardinalidad si existe una correspondencia uno a uno\(\varphi: A \rightarrow B\).
Denotamos el hecho\(A\) y\(B\) tenemos la misma cardinalidad por escrito\(|A|=|B| .\)
Defina una relación en conjuntos estableciendo\(A \sim B\) si y solo si\(|A|=|B| .\) Mostrar que esta relación es una relación de equivalencia.
\(A\)Déjese ser un conjunto. Si, porque\(n \in \mathbb{Z}^{+}, A\) tiene la cardinalidad del conjunto\(\{1,2,3, \ldots, n\},\) decimos\(A\) es finito y escribimos\(|A|=n .\) Si\(A\) tiene la cardinalidad de\(\mathbb{Z}^{+},\) decimos\(A\) es contable y escribimos\(|A|=\aleph_{0} .\)
Si definimos\(\varphi: \mathbb{Z}^{+} \rightarrow \mathbb{Z}\) por
\[\varphi(n)=\left\{\begin{array}{ll}{\frac{n-1}{2},} & {\text { if } n \text { is odd, }} \\ {-\frac{n}{2},} & {\text { if } n \text { is even, }}\end{array}\right.\]
entonces\(\varphi\) es una correspondencia uno a uno. Así\(|\mathbb{Z}|=\aleph_{0}\).
Dejado\(A\) ser el conjunto de enteros pares. \(|A|=\aleph_{0}\)Demuéstralo.
Verifica cada uno de los siguientes:
a. Si\(A\) es un subconjunto no vacío de\(\mathbb{Z}^{+},\) entonces\(A\) es finito o contable.
b. Si\(A\) es un subconjunto no vacío de un conjunto contable\(B,\), entonces\(A\) es finito o contable.
Supongamos\(A\) y\(B\) son conjuntos contables. Entonces el conjunto\(C=\)\(A \cup B\) es contable.
- Prueba
-
Supongamos\(A\) y\(B\) son disjuntos, es decir,\(A \cap B=\emptyset .\) Dejar\(\varphi: \mathbb{Z}^{+} \rightarrow A\) y\(\psi: \mathbb{Z}^{+} \rightarrow B\) ser correspondencias uno-a-uno. Definir\(\tau: \mathbb{Z}^{+} \rightarrow C\) por
\[\tau(n)=\left\{\begin{array}{ll}{\varphi\left(\frac{n+1}{2}\right),} & {\text { if } n \text { is odd, }} \\ {\psi\left(\frac{n}{2}\right),} & {\text { if } n \text { is even. }}\end{array}\right.\]
Entonces\(\tau\) es una correspondencia uno a uno, mostrando que\(C\) es contable.
Si\(A\) y no\(B\) son disjuntos, entonces\(\tau\) está sobre pero no uno a uno. Sin embargo, en ese caso\(C\) tiene la cardinalidad de un subconjunto infinito de\(\mathbb{Z}^{+},\) y así es contable. \(\quad\)Q.E.D.
Se dice que un conjunto no vacío que no es finito es infinito. Se dice que un conjunto infinito que no es contable es incontable.
Supongamos que\(A\) es incontable y\(B \subset A\) es contable. Demostrar que\(A \backslash B\) es incontable.
Supongamos\(A\) y\(B\) son contables. Entonces\(C=A \times B\) es contable.
- Prueba
-
Dejar\(\varphi: \mathbb{Z}^{+} \rightarrow A\) y\(\psi: \mathbb{Z}^{+} \rightarrow B\) ser correspondencias uno a uno. Dejar\(a_{i}=\varphi(i)\) y\(b_{i}=\psi(i) .\) definir\(\tau: \mathbb{Z}^{+} \rightarrow C\) dejando
\[\tau(1)=\left(a_{1}, b_{1}\right),\]
\[\tau(2)=\left(a_{1}, b_{2}\right),\]
\[\tau(3)=\left(a_{2}, b_{1}\right),\]
\[\tau(4)=\left(a_{1}, b_{3}\right),\]
\[\tau(5)=\left(a_{2}, b_{2}\right),\]
\[\tau(6)=\left(a_{3}, b_{1}\right),\]
\[\tau(7)=\left(a_{1}, b_{4}\right),\]
\[\vdots = \vdots\]
Es decir, formar la matriz infinita con\(\left(a_{i}, b_{j}\right)\) en la fila\(i\)\(j\) th y th columna, y luego contar las entradas leyendo las diagonales de derecha a izquierda. Entonces\(\tau\) es una correspondencia uno a uno y\(C\) es contable.
\(\mathbb{Q}\)es contable.
- Prueba
-
Por la proposición anterior,\(\mathbb{Z} \times \mathbb{Z}\) es contable. Let
\[A=\{(p, q): p, q \in \mathbb{Z}, q>0, p \text { and } q \text { relatively prime }.\}\]
Entonces\(A\) es infinito y\(A \subset \mathbb{Z} \times \mathbb{Z},\) así\(A\) es contable. Pero claramente\(|\mathbb{Q}|=|A|,\) así\(\mathbb{Q}\) es contable. \(\quad\)Q.E.D.
Supongamos que para cada uno\(i \in \mathbb{Z}^{+}, A_{i}\) es contable. Entonces
\[B=\bigcup_{i=1}^{\infty} A_{i}\]
es contable.
- Prueba
-
Supongamos que los conjuntos\(A_{i}, i \in \mathbb{Z}^{+},\) son disjuntos por pares, es decir,\(A_{i} \cap A_{j}=\emptyset\)\(i, j \in \mathbb{Z}^{+} .\) para todos Para cada\(i \in \mathbb{Z}^{+},\) dejar\(\varphi_{i}: \mathbb{Z}^{+} \rightarrow A_{i}\) ser una correspondencia uno a uno. Luego\(\psi: \mathbb{Z}^{+} \times \mathbb{Z}^{+} \rightarrow B\) definido por
\[\psi(i, j)=\varphi_{i}(j)\]
es una correspondencia uno a uno, y así\(|B|=\left|\mathbb{Z}^{+} \times \mathbb{Z}^{+}\right|=\aleph_{0}\).
Si los conjuntos no\(A_{i}, i \in \mathbb{Z}^{+},\) son disjuntos, entonces\(\psi\) está sobre pero no uno a uno. Pero entonces existe un subconjunto\(P\) de\(\mathbb{Z}^{+} \times \mathbb{Z}^{+}\) tales que\(\psi: P \rightarrow B\) es una correspondencia uno a uno. Dado que\(P\) es un subconjunto infinito de un conjunto contable,\(P\) es contable y así\(|B|=\aleph_{0} .\)\(\quad\) Q.E.D.
Si en la proposición anterior permitimos que, para cada uno\(i \in \mathbb{Z}^{+}, A_{i}\) sea finito o contable, entonces\(B=\bigcup_{i=1}^{\infty} A_{i}\) será finito o contable.