¿Por qué debería de $|2^\mathbb{N}|>|\mathbb{N}^2|$ ser verdad?

Question

He estado pensando un poco sobre el infinito de las cosas últimamente, y esta pregunta me había preguntado acerca volvió a mí.

Uno de los clásicos de exposición manifestaciones de Cantor del trabajo son los dos igual de sorprendente hechos que no son como muchos racionales como los números naturales, pero no son más reales que los números naturales. Esto puede ser reducida a una declaración en la que el cardenal aritmética, a saber, que $$|2^\mathbb{N}|>|\mathbb{N}^2|$$

Ahora, podemos pensar que estos conjuntos como dos colecciones de funciones, $2^\mathbb{N}=\{f:\mathbb{N}\to \{0,1\}\}$$\mathbb{N}^2=\{f:\{0,1\}\to\mathbb{N}\}$. Así que parece que lo esta declaración (y otros similares) que está diciendo, es que si quieres más funciones, es mejor que tener un gran dominio de un gran codominio.

Hay una intuitiva explicación de por qué esto debe ser así?

Answer 1

La desigualdad es un poco plausible por la observación de que $|\mathbb N^2|$ es casi el conteo del número de $1$-elemento y $2$-elemento de los conjuntos de números naturales, mientras que $|2^{\mathbb N}|$ cuenta todos los conjuntos de números naturales. ("Casi" se refiere a los hechos que cada una de las $2$-element set $\{a,b\}$ es contada dos veces, como $(a,b)$ y $(b,a)$.)

Answer 2

Esta respuesta que escribí explica por qué la $\mathbb N^2$ es countably infinito.

Una manera de demostrar que $2^{\mathbb N}$ es de la onucountably infinito es por Cantor de la diagonal argumento, que yo creo que ha sido reiterado en stackexchange muchas veces.

Answer 3

Intuitivamente, es porque mientras que las funciones tienen que estar bien definidos, que pueden no ser inyectiva, por lo que si usted está colocando las flechas entre los elementos de dos objetos, tienes mucha más libertad para elegir dónde hacer sus flechas punto de donde usted puede elegir dónde hacerlos punto de.

Para decirlo de forma más sucinta, usted puede encontrar más maneras de enviar las cosas en un objeto que usted puede encontrar maneras de enviar cosas fuera de un objeto; por ejemplo, grupos y anillos, generalmente tienen más subobjetos que el cociente de los objetos.

Answer 4

Para un conjunto $X$, la $2^X$, su juego de poder, debería ser mucho más grande que la de $X$. Cantor de la diagonal argumento da una prueba de ello, y sugiero que la contradicción en el argumento de Cantor da algún tipo de indicación de por qué este es el caso.

Si aceptamos esto, entonces solo tenemos la intuición de por qué $\mathbb{N}, \mathbb{N}^2$ son del mismo tamaño. De alguna manera esto no es más que sorprendente. Por ejemplo, hay $| \mathbb{N}|$ muchos números primos, y podemos asociar cada una de las $n \in \mathbb{N}$ con su descomposición en factores primos que nos puede llevar a ser una tupla de tal manera que cada entrada es un número primo y el $i$th entrada es $\leq$ $i+1$th. Entonces ya tenemos un inyectiva mapa de $f: \mathbb{N}^2 \to \mathbb{Z}$ $(a, b)$ corresponde a $p_a \cdot p_b$ si $ a \leq b$ $-p_a \cdot p_b$ lo contrario.

El punto de esto es que el $\mathbb{N}$ es el conjunto de $1$-tuplas de productos naturales y $\mathbb{N}^2$ es sólo el conjunto de $2$-tuplas y no debería parecer tan sorprendente que podemos volver a índice cosas para transformar uno en el otro.

Answer 5

Continuando con Andreas respuesta es que para cualquier $n \in \mathbb{N}$ tenemos que $\left \vert \mathbb{N}^n \right \vert = \left\vert \mathbb{N} \right\vert$, e incluso a la $\left\vert \mathbb{N}^{<\omega} \right\vert = \left\vert \bigcup \{ \mathbb{N}^{n} \mid n \in \mathbb{N} \} \right\vert = \left\vert \mathbb{N} \right\vert$.

Usted puede pensar en las funciones de $n \to \mathbb{N}$ como secuencias de longitud $n$ con valores en $\mathbb{N}$, así que lo que está diciendo es que la unión de todas las secuencias finitas de números naturales es todavía contables!

En un sentido, esto puede ser claro si ustedes recuerdan la frase muy citada declaración de que "una contables de la unión de conjuntos contables es contable." Pero como usted señala es todavía muy confuso. Infinitos tomar tiempo para acostumbrarse, pero una cosa siempre se puede sostener es que el powerset operación siempre te dará una mayor cardinalidad, pero en general exponenciación no (a menos que usted está criando a un tamaño lo suficientemente grande como por ejemplo,$\left| \mathbb{N}^{\mathbb{N}} \right| = \left| 2^{\mathbb{N}} \right|$).