El producto cartesiano infinito de conjuntos contables es incontable

Question

Sea $\{E_n\}_{n\in\mathbb{N}}$ sea una secuencia de conjuntos contables y sea $S=E_1\times\cdots\times E_n\times\cdots $ . Mostrar $S$ es incontable. Demostrar que la misma afirmación es válida si cada $E_n=\{0,1\}$ .

Por la definición de producto cartesiano de conjuntos,

$$\displaystyle S=\Pi_{n\in\mathbb{N}} \{f\colon\mathbb{N}\rightarrow\cup_{n\in\mathbb{N}}E_n\mid\forall n, f(n)\in E_n\}$$

Si $E_n=\{ 0,1\}$ entonces

$$\displaystyle S_{01}=\Pi_{n\in\mathbb{N}}\{0,1\}=E^{\mathbb{N}}$$ donde $E=\{0,1\}$ .

Por un teorema, $\cup_{n\in\mathbb{N}} E_n$ es contable ya que la secuencia es contable.

No estoy seguro de cómo seguir a partir de aquí para mostrar $S$ es incontable. ¿Podemos decir algo sobre la función $f$ que mapea un $\mathbb{N}$ a otra unión contable de secuencia de conjuntos contables?

Answer 1

Puedes reproducir el truco de la diagonal de Cantor para ambos problemas.

Supongamos que $S$ es contable. Sea $(F_n: n\in\mathbb N)$ sea una enumeración de $S$ . Para cada $n$ elige dos puntos $a_n,b_n\in E_n$ . A continuación, defina una nueva función $F\in S$ como sigue: $$F(m)= \begin{cases} b_m &\mbox{if } F_m(m)=a_m \\ a_m & \mbox{otherwise } \end{cases}$$ De ello se deduce que $F\in S$ pero es diferente de todos $F_n$ que es una contradicción.

Answer 2

Cuando dice "contable", ¿quiere decir "contablemente infinito"? Este resultado no tiene por qué ser cierto en caso contrario; tomemos, por ejemplo, el caso en que $E_n=\{0\}$ para todos $n$ .

Suponiendo que quisieras decir "contablemente infinito": la idea habitual aquí es lo que se llama un argumento de diagonalización .

Supongamos que $S$ es contable, de modo que todos los elementos de $S$ puede enumerarse como $a_1,a_2,\ldots$ . Sea $a_n^m$ denotan el $m$ elemento de la tupla que representa $a_n$ .

Construyamos una secuencia que no esté en la lista. Elija $b_1\in E_1$ tal que $a_1^1\neq b_1$ . Elija $b_2\in E_2$ tal que $a_2^2\neq b_2$ . Continúe así, eligiendo $b_n\in E_n$ tal que $a_n^n\neq b_n$ .

El elemento $(b_n)_{n=1}^{\infty}$ debe aparecer en algún lugar de la lista; sin embargo, no puede ser el primer elemento, ya que difieren en la primera coordenada; no puede ser el segundo, ya que difieren en la segunda coordenada; etc.

Answer 3

Ok en primer lugar si $E_n$ es $\{0,1\}$ entonces usted está tratando de demostrar que el infinito $0-1$ son incontables. Asume ab absurdo que puedes contarlas.

Entonces

$$ N_1=x_{11}x_{12}x_{13}.... $$ $$ N_2=x_{21}x_{22}x_{23}... $$ Y así sucesivamente. Definir una secuencia $y$ por $y=y_1y_2y_3...$ donde $y_i=1-x_{ii}$ (por lo que si $x_{ii}$ es $1$ te da $0$ y si su $0$ te da $1$ .

¿Puede demostrar que $y$ no es igual a ningún $N_k$ ?

Answer 4

Pista: existe una biyección entre $\mathbb R$ y $\{0,1\}^{\mathbb N}$ y se puede crear una función inyectiva a partir de $\{0,1\}^{\mathbb N}$ tо $S$ si al menos un amоunt infinito de la $E_i$ tienen dos o más elementos.

Answer 5

Se puede mostrar, sin utilizar ninguna parte del axioma de elección ,
que el producto no es contablemente infinito.

Por definición, $\;\; \omega \: = \: \big\{\hspace{-0.02 in}0,\hspace{-0.04 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\hspace{-0.05 in}\big\} \;\;\;$ .

Sea $\:\langle \hspace{.02 in}E_{\hspace{.03 in}0}\hspace{.02 in},\hspace{-0.01 in}E_{\hspace{.02 in}1},E_{\hspace{.03 in}2}\hspace{.02 in},E_{\hspace{.03 in}3}\hspace{.02 in},...\hspace{-0.02 in}\rangle\:$ sea una secuencia de conjuntos, infinitamente muchos de los cuales tienen más de

un elemento. $\;\;\;\;\;\;$ Sea $\;\; S \: = \: \displaystyle\prod_{n=0}^{\infty} E_{\hspace{.02 in}n} \;\;\;$ . $\;\;\;\;\;\;$ Si $\;\; S \: = \: \{\} \;\;$ , $\;\;$ entonces $S$ no es contablemente infinito.

Supongamos $\;\; S \: \neq \: \{\} \;\;$ , $\;\;$ y que $\: \hspace{.05 in}f : \omega \to S \:$ sea una función arbitraria.
Sea $\;\; D \: = \: \{n\in \omega : (\exists m)((\hspace{.045 in}f(m))(n) \neq (\hspace{.045 in}f(0))(n))\} \;\;\;$ .

Si $D$ es finito, entonces
[
Sea $i$ sea el menor elemento de $\:\omega\hspace{-0.04 in}-\hspace{-0.04 in}D\:$ tal que $E_{\hspace{.02 in}i}$ tiene más de
un elemento, y que $x$ sea un elemento de $E_{\hspace{.02 in}i}$ que no sean $(\hspace{.045 in}f(0))(i\hspace{.02 in})$ .
Sea $s$ sea el elemento de $S$ dado por si $\:n=i\:$ entonces $\:s(n) = x\:$ si no $\:\: s(n) = (\hspace{.045 in}f(0))(i\hspace{.02 in}) \;\;$ .
Para todos los elementos $n$ de $\omega$ , $\:(\hspace{.045 in}f(n))(i\hspace{.02 in}) = (\hspace{.045 in}f(0))(i\hspace{.02 in}) \neq x = s(i)\;$ .
Para todos los elementos $n$ de $\omega$ , $\:\hspace{.045 in}f(n) \neq s \;$ . $\;\;\;$ $s$ no es un elemento de $\operatorname{Range}(\hspace{.045 in}f\hspace{.025 in})$ . $\;$ $\hspace{.045 in}f$ no es suryectiva.
]

Si $D$ es infinito, entonces
[
Sea $\: h : \omega \to D \:$ sea la biyección natural.
Sea $\: g : D\to \omega \:$ viene dada por $\:\:g(n)$ es el menor elemento $m$ de $\omega$ tal que $\:(\hspace{.045 in}f(m))(n) \neq (\hspace{.045 in}f(0))(n)\;\;$ .
Sea $s$ sea el elemento de $S$ dada por
si $\:$ [ $n\in D\:$ y $\:(\hspace{.045 in}f(h^{-1}(n)))(n) = (\hspace{.045 in}f(0))(n)$ ] $\:$ entonces $\: s(n) = (\hspace{.045 in}f(g(n)))(n) \:$ si no $\: s(n) = (\hspace{.045 in}f(0))(n)\;$ .
Para todos los elementos $n$ de $\omega$ , $\:\:$ si $\: (\hspace{.045 in}f(h^{-1}(h(n))))(h(n)) = (\hspace{.045 in}f(0))(h(n)) \:$ entonces
$(\hspace{.045 in}f(n))(h(n)) = (\hspace{.045 in}f(h^{-1}(h(n))))(h(n)) = (\hspace{.045 in}f(0))(h(n)) \neq (\hspace{.045 in}f(g(h(n))))(h(n)) = s(h(n)) \;$ .
Para todos los elementos $n$ de $\omega$ , $\:\:$ si $\: (\hspace{.045 in}f(h^{-1}(h(n))))(h(n)) \neq (\hspace{.045 in}f(0))(h(n)) \:$ entonces
$(\hspace{.045 in}f(n))(h(n)) = (\hspace{.045 in}f(h^{-1}(h(n))))(h(n)) \neq (\hspace{.045 in}f(0))(h(n)) = s(h(n)) \;$ .
Para todos los elementos $n$ de $\omega$ , $\: (\hspace{.045 in}f(n))(h(n)) \neq s(h(n)) \;$ . $\;\;\;$ Para todos los elementos $n$ de $\omega$ , $\: \hspace{.05 in}f(n) \neq s \;$ .
$s$ no es un elemento de $\operatorname{Range}(\hspace{.045 in}f\hspace{.025 in})$ . $\;$ $\hspace{.045 in}f$ no es suryectiva.
]

Si $D$ es finito entonces $\hspace{.045 in}f$ no es suryectiva. $\:$ Si $D$ es infinito entonces $\hspace{.045 in}f$ no es suryectiva. $\:$ $\hspace{.045 in}f$ no es suryectiva.
Eso suponiendo $\: S\neq \{\} \:$ , $\:$ por lo que tenemos $\;\;$ "Si $\: S\neq \{\} \:$ entonces $S$ no es contablemente infinito" $\;\;$ .
Por lo tanto $S$ no es contablemente infinito.

QED