¿Hay alguna forma de resolver este problema utilizando el método de diagonalización? Sé que hay una prueba que usa $\mathcal{P}(\mathbb{N})$ = conjunto de todos los subconjuntos finitos $\cup$ conjunto de todos los subconjuntos infinitos, pero estoy intentando resolverlo específicamente utilizando el método de diagonalización. Estaba pensando que podemos suponer que ambos tienen la misma cardinalidad y llegar a una contradicción, pero no sé cómo llegar allí. ¿Cómo podemos mostrar que tiene que haber algún conjunto infinito en el conjunto de todos los subconjuntos infinitos que no puede emparejarse 1 a 1 con un número natural?
Respuestas
¿Demasiados anuncios?
Supongamos que el conjunto de todos los subconjuntos infinitos (y por lo tanto todos son numerables) de $\mathbb N$ fuera numerable. Supongamos entonces que $\{A_n\}_{n\in \mathbb N}$ es una lista de todos los subconjuntos numerables de $\mathbb N$, y escribimos $A_n=\{a_{n,1},\cdots, a_{n,k},\cdots \}$. Ahora diagonalizamos definiendo $b_n$ como algún entero diferente de $\{b_j\}_{1\le j < n}$ y también $b_n\ne a_{n,n}$ y mostramos que $\{b_n\}_{n\in \mathbb N}$ no está en tu lista, pero es un subconjunto infinito de $\mathbb N$.
oym
Puntos
1622
Supongamos que $\mathcal{P}(\mathbb{N})$ tiene una cardinalidad igual a $\mathbb{N}$.
Eso significa que podemos poner cada conjunto $ \: S_i \in \mathcal{P}(\mathbb{N}) $ en una correspondencia uno a uno con un número natural $\: i $. Ahora consideremos $ J \subset \mathbb{N} $ definido como $ J = \{\: i \in \mathbb{N} \:| \: i \notin S_i \}$ . Por construcción, $ \forall \: i, \: J \neq S_i$ porque al comparar con cualquier $S_i \:$, $i$ está en $J$ (por definición) solo si NO está en $S_i$. Por lo tanto, la correspondencia uno a uno no es posible.
dtldarek
Puntos
23441
Sea $\mathcal{I}$ el conjunto de todos los subconjuntos infinitos de $\mathbb{N}$, es decir, $$\mathcal{I} = \Big\{ A \subseteq \mathbb{N}\ \Big|\ |A| = |\mathbb{N}| \Big\}.$$
Supongamos que $\mathcal{I}$ es numerable, es decir, $|\mathcal{I}| = |\mathbb{N}|$, y así, existe una biyección $f : \mathbb{N} \to \mathcal{I}$.
Denotemos por $g_n(S)$ al $n$-ésimo número más pequeño de $S$ para cualquier conjunto $S \in \mathcal{I}$ (tal número siempre existe, porque $\langle\mathbb{N},\leq\rangle$ es bien fundamentado y $S$ es infinito): $$ g_n(S) = k \iff \Big|S \cap \{0,1,\ldots,k\}\Big| = n.$$ Ahora definamos una secuencia no decreciente $x_n$ y el conjunto $X$ de sus elementos \begin{align} x_n &= 1 + \max_{k \leq n} g_n\big(f(k)\big) & \text{ para } n \in \mathbb{N},\\ X &= \{x_n \mid n \in \mathbb{N}\}, \end{align} y observemos que por definición de $\mathcal{I}$ tenemos $X \in\mathcal{I}$. Sea $\chi = f^{-1}(X)$ y consideremos $$ \color{red}{g_\chi(X)} \stackrel{(1)}\geq x_\chi \stackrel{(2)}= 1+\max_{k \leq \chi} g_\chi(f(k)) \stackrel{(3)}\geq 1+g_\chi(f(\chi)) \stackrel{(4)}= \color{red}{1+g_\chi(X)} $$ donde
- $x_n$ es no decreciente, por lo tanto $g_k(X) \geq x_k$ para cualquier $k \in \mathbb{N}$,
- definición de $x_n$,
- propiedad del $\max$ para $k = \chi$,
- $f$ es una biyección,
lo que lleva a $\color{red}{g_\chi(X)} \geq \color{red}{1+g_\chi(X)}$, es decir, contradicción.
Espero que esto ayude $\ddot\smile$
