Saltar al contenido principal

# 4.6: Conjuntos incontables

$$\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}$$

Template:MathJaxZach

Algunos conjuntos, como el conjunto$$\PosInt$$ de enteros positivos, son infinitos. Hasta ahora hemos visto ejemplos de conjuntos infinitos que eran todos contables. Sin embargo, también hay infinitos conjuntos que no tienen esta propiedad. Tales conjuntos se llaman incontables.

En primer lugar, quizás ya sea sorprendente que haya conjuntos incontables. Para cualquier conjunto contable$$A$$ hay una función suryectiva$$f \colon \PosInt \to A$$. Si un conjunto es incontable no existe tal función. Es decir, ninguna función que mapee los infinitamente muchos elementos de$$\PosInt$$ a$$A$$ puede agotar todos$$A$$. Entonces hay “más” elementos de$$A$$ que los infinitamente muchos enteros positivos.

¿Cómo se probaría que un conjunto es incontable? Hay que demostrar que no puede existir tal función suryectiva. Equivalentemente, hay que demostrar que los elementos de$$A$$ no se pueden enumerar en una lista infinita de una manera. La mejor manera de hacerlo es demostrar que cada lista de elementos de$$A$$ debe dejar al menos un elemento fuera; o que ninguna función$$f\colon \PosInt \to A$$ puede ser surjectiva. Podemos hacer esto usando el método diagonal de Cantor. Dada una lista de elementos de$$A$$, digamos,$$x_1$$,$$x_2$$,..., construimos otro elemento del$$A$$ cual, por su construcción, no puede estar posiblemente en esa lista.

Nuestro primer ejemplo es el conjunto$$\Bin^\omega$$ de todas las secuencias infinitas, no gappy de$$0$$'s y$$1$$'s.

Teorema$$\PageIndex{1}$$

$$\Bin^\omega$$es incontable.

Prueba. Supongamos, a modo de contradicción, eso$$\Bin^\omega$$ es contable, es decir, supongamos que hay una lista$$s_{1}$$,$$s_{2}$$,$$s_{3}$$,$$s_{4}$$,... de todos los elementos de$$\Bin^\omega$$. Cada uno de estos$$s_i$$ es en sí mismo una secuencia infinita de$$0$$$$1$$'s y's Llamemos al$$j$$ -ésimo elemento de la$$i$$ -ésima secuencia en esta lista$$s_i(j)$$. Entonces la secuencia$$i$$ -ésima$$s_i$$ es$s_i(1), s_i(2), s_i(3), \dots\nonumber$

Podemos organizar esta lista, y los elementos de cada secuencia$$s_i$$ en ella, en una matriz:$\begin{array}{c|c|c|c|c|c} & 1 & 2 & 3 & 4 & \dots \\\hline 1 & \mathbf{s_{1}(1)} & s_{1}(2) & s_{1}(3) & s_1(4) & \dots \\\hline 2 & s_{2}(1)& \mathbf{s_{2}(2)} & s_2(3) & s_2(4) & \dots \\\hline 3 & s_{3}(1)& s_{3}(2) & \mathbf{s_3(3)} & s_3(4) & \dots \\\hline 4 & s_{4}(1)& s_{4}(2) & s_4(3) & \mathbf{s_4(4)} & \dots \\\hline \vdots & \vdots & \vdots & \vdots & \vdots & \mathbf{\ddots} \end{array}\nonumber$ Las etiquetas al lado dan el número de la secuencia en la lista$$s_1$$,$$s_2$$,...; los números en la parte superior etiquetan los elementos del individuo secuencias. Por ejemplo,$$s_{1}(1)$$ es un nombre para cualquier número, a$$0$$ o a$$1$$, es el primer elemento de la secuencia$$s_{1}$$, y así sucesivamente.

Ahora construimos una secuencia infinita,$$\overline{s}$$, de$$0$$'s y$$1$$'s que posiblemente no puede estar en esta lista. La definición de$$\overline{s}$$ dependerá de la lista$$s_1$$,$$s_2$$,... Cualquier lista infinita de secuencias infinitas de$$0$$'s y$$1$$'s da lugar a una secuencia infinita$$\overline{s}$$ que se garantiza que no aparecerá en la lista.

Para definir$$\overline{s}$$, especificamos cuáles son todos sus elementos, es decir, especificamos$$\overline{s}(n)$$ para todos$$n \in \PosInt$$. Hacemos esto leyendo la diagonal de la matriz anterior (de ahí el nombre “método diagonal”) y luego cambiando cada$$1$$ a a$$0$$ y cada$$0$$ a$$1$$. De manera más abstracta,$$\overline{s}(n)$$ definimos ser$$0$$ o$$1$$ según si el$$n$$ -ésimo elemento de la diagonal,$$s_n(n)$$, es$$1$$ o$$0$$. $\overline{s}(n) = \begin{cases} 1 & \text{if s_{n}(n) = 0}\\ 0 & \text{if s_{n}(n) = 1}. \end{cases}\nonumber$Si te gustan más las fórmulas que las definiciones por casos, también podrías definir$$\overline{s}(n) = 1 - s_n(n)$$.

Claramente$$\overline{s}$$ es una secuencia infinita de$$0$$'s y$$1$$'s, ya que es solo la secuencia espejo a la secuencia de$$0$$'s y$$1$$'s que aparecen en la diagonal de nuestra matriz. Entonces$$\overline{s}$$ es un elemento de$$\Bin^\omega$$. Pero no puede estar en la lista$$s_1$$,$$s_2$$,... ¿Por qué no?

No puede ser la primera secuencia de la lista,$$s_1$$, porque difiere de$$s_1$$ en el primer elemento. Sea lo que$$s_1(1)$$ sea, definimos como$$\overline{s}(1)$$ lo contrario. No puede ser la segunda secuencia de la lista, porque$$\overline{s}$$ difiere de$$s_2$$ en el segundo elemento: if$$s_2(2)$$ is$$0$$,$$\overline{s}(2)$$ is$$1$$, y viceversa. Y así sucesivamente.

Más precisamente: si$$\overline{s}$$ estuvieran en la lista, habría algunos$$k$$ así que eso$$\overline{s} = s_{k}$$. Dos secuencias son idénticas si coinciden en cada lugar, es decir, para cualquier$$n$$,$$\overline{s}(n) = s_{k}(n)$$. Entonces en particular, tomando$$n = k$$ como caso especial,$$\overline{s}(k) = s_{k}(k)$$ tendría que aguantar. $$s_k(k)$$es$$0$$ o$$1$$. Si es$$0$$ entonces$$\overline{s}(k)$$ debe ser$$1$$ —así es como definimos$$\overline{s}$$. Pero si$$s_k(k) = 1$$ entonces, de nuevo por la forma en que definimos$$\overline{s}$$,$$\overline{s}(k) = 0$$. En cualquier caso$$\overline{s}(k) \neq s_{k}(k)$$.

Empezamos asumiendo que hay una lista de elementos de$$\Bin^\omega$$,,$$s_1$$$$s_2$$,... De esta lista construimos una secuencia$$\overline{s}$$ que probamos que no puede estar en la lista. Pero definitivamente es una secuencia de$$0$$'s y$$1$$'s si todos los$$s_i$$ son secuencias de$$0$$'s y$$1$$'s, es decir,$$\overline{s} \in \Bin^\omega$$. Esto muestra en particular que no puede haber lista de todos los elementos de$$\Bin^\omega$$, ya que para cualquier lista de este tipo también podríamos construir una secuencia$$\overline{s}$$ garantizada para no estar en la lista, por lo que la suposición de que hay una lista de todas las secuencias en $$\Bin^\omega$$lleva a una contradicción. ◻

Este método de prueba se llama “diagonalización” porque usa la diagonal de la matriz para definir$$\overline{s}$$. La diagonalización no necesita involucrar la presencia de una matriz: podemos mostrar que los conjuntos no son contables usando una idea similar incluso cuando no hay matriz y ninguna diagonal real está involucrada.

Teorema$$\PageIndex{2}$$

$$\Pow{\PosInt}$$no es contable.

Prueba. Procedemos de la misma manera, mostrando que por cada lista de subconjuntos de$$\PosInt$$ hay un subconjunto de los$$\PosInt$$ cuales no puede estar en la lista. Supongamos que lo siguiente es una lista dada de subconjuntos de$$\PosInt$$: Ahora$Z_{1}, Z_{2}, Z_{3}, \dots\nonumber$ definimos un conjunto$$\overline{Z}$$ tal que para cualquier$$n \in \PosInt$$,$$n \in \overline{Z}$$ iff$$n \notin Z_{n}$$:$\overline{Z} = \Setabs{n \in \PosInt}{n \notin Z_n}\nonumber$$$\overline{Z}$$ es claramente un conjunto de enteros positivos, ya que por suposición cada uno$$Z_n$$ es, y por lo tanto$$\overline{Z} \in \Pow{\PosInt}$$. Pero$$\overline{Z}$$ no puede estar en la lista. Para mostrar esto, estableceremos eso para cada uno$$k \in \PosInt$$,$$\overline{Z} \neq Z_k$$.

Así que$$k \in \PosInt$$ seamos arbitrarios. Hemos definido$$\overline{Z}$$ así que para cualquier$$n \in \PosInt$$,$$n \in \overline{Z}$$ iff$$n \notin Z_n$$. En particular, tomando$$n=k$$,$$k \in \overline{Z}$$ iff$$k \notin Z_k$$. Pero esto demuestra que$$\overline{Z} \neq Z_k$$, ya que$$k$$ es un elemento de uno pero no del otro, y así$$\overline{Z}$$ y$$Z_k$$ tienen elementos diferentes. Ya que$$k$$ fue arbitrario, no$$\overline{Z}$$ está en la lista$$Z_1$$,$$Z_2$$,... ◻

La prueba anterior no mencionaba una diagonal, pero se puede pensar en ella como que involucra una diagonal si la imaginas de esta manera: Imagina los conjuntos$$Z_1$$,$$Z_2$$,..., escritos en una matriz, donde cada elemento$$j \in Z_i$$ está listado en la$$j$$ -ésima columna. Digamos que los primeros cuatro conjuntos de esa lista son$$\{1,2,3,\dots\}$$,$$\{2, 4, 6, \dots\}$$,$$\{1,2,5\}$$, y$$\{3,4,5,\dots\}$$. Entonces la matriz comenzaría con$\begin{array}{r@{}rrrrrrr} Z_1 = \{ & \mathbf{1}, & 2, & 3, & 4, & 5, & 6, & \dots\}\\ Z_2 = \{ & & \mathbf{2}, & & 4, & & 6, & \dots\}\\ Z_3 = \{ & 1, & 2, & & & 5\phantom{,} & & \}\\ Z_4 = \{ & & & 3, & \mathbf{4}, & 5, & 6, & \dots\}\\ \vdots & & & & & \ddots \end{array}\nonumber$ Entonces$$\overline{Z}$$ es el conjunto obtenido bajando la diagonal, dejando fuera cualquier número que aparezca a lo largo de la diagonal e incluya aquellos$$j$$ donde la matriz tenga un hueco en la$$j$$ -ésima fila/columna. En el caso anterior, dejaríamos fuera$$1$$ y$$2$$, incluiríamos$$3$$, dejaríamos fuera$$4$$, etc.

Problema$$\PageIndex{1}$$

Demostrar que$$\Pow{\Nat}$$ es incontable por un argumento diagonal.

Problema$$\PageIndex{2}$$

Mostrar que el conjunto de funciones$$f \colon \PosInt \to \PosInt$$ es incontable por un argumento diagonal explícito. Es decir, mostrar que si$$f_1$$,$$f_2$$,..., es una lista de funciones y cada una$$f_i\colon \PosInt \to \PosInt$$, entonces hay algunas que$$\overline{f}\colon \PosInt \to \PosInt$$ no están en esta lista.

This page titled 4.6: Conjuntos incontables is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. (Open Logic Project) .