1.4: Conjuntos contables e incontables
- Page ID
- 111527
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Definición 1.18
Un conjunto\(S\) es contable si hay una biyección\(f : \mathbb{N} \rightarrow S\). Un conjunto infinito para el que no existe tal bijección se llama incontable.
Proposición 1.19
Cada conjunto infinito\(S\) contiene un subconjunto contable.
Proposición 1.19
Cada conjunto infinito\(S\) contiene un subconjunto contable.
- Prueba
-
Elige un elemento\(s_{1}\) de\(S\). Ahora no\(S-\{s_{1}\}\) está vacío porque no\(S\) es finito. Entonces, elige\(s_{2}\) entre\(S-\{s_{1}\}\). Entonces no\(S-\{s_{1}, s_{2}\}\) está vacío porque no\(S\) es finito. De esta manera, podemos eliminar\(s_{n+1}\) de\(S-\{s_{1}, s_{2}, \cdots, s_{n}\}\) para todos\(n\). Entonces el conjunto\(\{s_{1}, s_{2}, \cdots\}\) es contable y está contenido en\(S\).
Entonces, los conjuntos contables son los conjuntos infinitos más pequeños en el sentido de que no hay conjuntos infinitos que no contengan ningún conjunto contable. Pero ciertamente hay conjuntos más grandes, como veremos a continuación.
Teorema 1.20
El conjunto\(\mathbb{R}\) es incontable.
- Prueba
-
La prueba es uno de los argumentos más famosos de las matemáticas: el argumento diagonal de Cantor [8]. El argumento se desarrolla en dos pasos.
Dejar\(T\) ser el conjunto de secuencias semi-infinitas formadas por los dígitos 0 y 2. Un elemento\(t \in T\) tiene la forma\(t = t_{1}t_{2}t_{3} \dots\) donde\(t_{i} \in \{0, 2\}\). El primer paso de la prueba es demostrar que\(T\) es incontable. Entonces supongamos que es contable. Entonces una biyección\(t\) entre\(\mathbb{N}\) y nos\(T\) permite definir de manera única la secuencia\(t(n)\), la secuencia única asociada a\(n\). Además, forman una lista exhaustiva de los elementos de\(T\). Por ejemplo,
\[t(1) = \textbf{0},0,0,0,0,0,0,0,0,0,0, \dots \nonumber\]
\[t(2) = 2, \textbf{0},2,0,2,0,2,0,2,2,2, \dots \nonumber\]
\[t(3) = 0,0, \textbf{0},2,2,2,2,2,2,2,2, \dots \nonumber\]
\[t(4) = 2,2,2, \textbf{2},2,2,0,0,0,0,0, \dots \nonumber\]
\[t(5) = 0,0,0,2, \textbf{2},0,2,0,0,2,0, \dots \nonumber\]
\[t(6) = 2,0,0,0,0, \textbf{2},0,0,0,2,2, \dots \nonumber\]
\[\vdots \nonumber\]
Construir de la\(t^{*}\) siguiente manera: para cada\(n\), su enésimo dígito difiere del dígito enésimo de\(t(n)\). En el ejemplo anterior,\(t^{*} = \textbf{2}, \textbf{2}, \textbf{2}, \textbf{0}, \textbf{2}, \textbf{0}, \dots\). Pero ahora tenemos una contradicción, porque el elemento\(t^{*}\) no puede aparecer en la lista. En otras palabras, no hay sobrejección de\(\mathbb{N}\) a\(T\). De ahí que no haya bijección entre\(\mathbb{N}\) y\(T\).
El segundo paso es demostrar que hay un subconjunto\(K\) de\(\mathbb{R}\) tales que no hay sobrejección (y por lo tanto no bijección) de\(\mathbb{N}\) a\(K\). Dejar\(t\) ser una secuencia con dígitos\(t_{i}\). Definir de\(f : T \rightarrow \mathbb{R}\) la siguiente manera
\[f(t) = \sum_{i=1}^{\infty}t_{i}3^{-i} \nonumber\]
Si\(s\) y\(t\) son dos secuencias distintas en\(T\), entonces para algunos\(k\) comparten los primeros\(k-1\) dígitos pero\(t_{k} = 2\) y\(s_{k} = 0\). Entonces
\[f(t)-f(s) = 2 \cdot 3^{-k}+\sum_{i=k+1}^{\infty} (t_{i}-s_{i}) 3^{-i} \ge 2 \cdot 3^{-k}-2 \sum_{i=k+1}^{\infty} 3^{-i} = 3^{-k} \nonumber\]
Así\(f\) es inyectivo. Por lo tanto,\(f\) es una bijección entre\(T\) y el subconjunto\(K = f(T)\) de\(\mathbb{R}\). Si hay una sobrejección\(g\) de\(\mathbb{N}\) a\(K = f(T)\), entonces,
\[\mathbb{N} \xrightarrow{\text{g}} K \xleftarrow{\text{f}} T \nonumber\]
Y así\(f^{-1} g\) es una sobrejección de\(\mathbb{N}\) a\(T\). Por el primer paso, esto es imposible. Por lo tanto, no hay surjección\(g\) de\(\mathbb{N}\) a\(K\), mucho menos de\(\mathbb{N}\) a\(\mathbb{R}\).
Corolario 1.21
(i) El conjunto de secuencias infinitas en\(\{1,2,\cdots, b-1\}^{\mathbb{N}}\) es incontable.
(ii) El conjunto de secuencias finitas (pero sin ligadas) en\(\{1, 2, \cdots, b-1\}^{\mathbb{N}}\) es contable.
- Prueba
-
La prueba de (i) es la misma que la prueba que\(T\) es incontable en la prueba del Teorema 1.20. El comprobante de (ii) consiste en escribir primero todas\(b\) las palabras de longitud 1, luego todas\(b^{2}\) las palabras de longitud 2, y así sucesivamente. Cada cadena finita aparecerá en la lista.
Teorema 1.22
(i) El conjunto\(\mathbb{Z}^2\) es contable.
(ii)\(\mathbb{Q}\) es contable.
- Prueba
-
(i) La prueba se basa en la Figura 2. En ella,\(\gamma\) se traza un camino dirigido que pasa por todos los puntos de\(\mathbb{Z}^2\). Imagina que comienzas\((0, 0)\) y viajas junto\(\gamma\) con la velocidad de la unidad. Mantener un contador\(c \in \mathbb{N}\) que marque el punto\((0, 0)\) con un “1”. Sube el valor del contador en 1 cada vez que golpeas un punto de\(\mathbb{Z}^2\). Esto establece una bijección entre\(\mathbb{N}\) y\(\mathbb{Z}^2\).
Figura 2. Un camino dirigido\(\gamma\) que pasa por todos los puntos de\(\mathbb{Z}^2\).
(ii) De nuevo viajar junto\(\gamma\) con la velocidad de la unidad. Mantener un contador\(c \in \mathbb{N}\) que marque el punto\((0, 1)\) con un “1”. Subir el valor del contador en 1. Continúa recorriendo el camino hasta llegar al siguiente punto\((p, q)\) que no es múltiplo de ningún anterior y tal no\(q\) es cero. Marcar ese punto con el valor del contador. \(\mathbb{Q}\)contiene\(\mathbb{N}\) y así es infinito. Identificar cada punto marcado\((p, q)\) con el número racional\(\frac{p}{q}\) establece la contabilidad de\(\mathbb{Q}\).
Observe que este argumento realmente nos dice que el producto de un conjunto contable y otro conjunto contable sigue siendo contable. Lo mismo se aplica a cualquier producto finito de conjunto contable. Dado que un conjunto incontable es estrictamente más grande que un contable, intuitivamente esto significa que un conjunto incontable debe ser mucho más grande que un conjunto contable. De hecho, una extensión del argumento anterior muestra que el conjunto de números algebraicos es contable. Y así, en cierto sentido, forma un pequeño subconjunto de todos los reales. Tanto más notable, que casi todos los reales de los que sabemos algo son números algebraicos, situación a la que nos referimos al final de la Sección 1.4.
Es útil e importante tener una definición más general de cuando dos conjuntos “tienen el mismo número de elementos”.
Definición 1.23
Se dice que dos conjuntos A y B tienen la misma cardinalidad si hay una biyección\(f : A \rightarrow B\). Está escrito como\(|A| = |B|\). Si hay una inyección\(f : A \rightarrow B\), entonces\(|A| \le |B|\).
Definición 1.24
Una relación de equivalencia en un conjunto\(A\) es un (sub) conjunto\(\mathbb{R}\) de pares ordenados\(A \times A\) que satisfacen tres requisitos.
- \((a, a) \in \mathbb{R}\)(reflexividad).
- Si\((a, b) \in \mathbb{R}\), entonces\((b, a) \in \mathbb{R}\) (simetría).
- Si\((a, b) \in \mathbb{R}\) y\((b, c) \in \mathbb{R}\), entonces Si\((a, c) \in \mathbb{R}\) (transitividad).
Por lo general\((a, b) \in \mathbb{R}\) se abrevía a\(a \sim b\). El símbolo matemático “\(=\)” es una equivalencia.
Es fácil demostrar que tener la misma cardinalidad es una relación de equivalencia en conjuntos (ejercicio 1.23). Tenga en cuenta que la cardinalidad de un conjunto finito es solo el número de elementos que contiene. Una excelente introducción a la cardinalidad de los conjuntos infinitos en el contexto de la ingenua teoría de conjuntos se puede encontrar en [15].