${ \mathbb{N} }^{ \left\{ 0,1 \right\} }$ ${ \left\{ 0,1 \right\} }^{ \mathbb{N} }$ , para ser más específicos, y hay una contables subconjunto en cada uno de ellos? Cómo los puedo encontrar?
Respuestas
¿Demasiados anuncios?
La sintaxis $X^Y$ donde $X$ $Y$ son conjuntos es el conjunto de funciones de$Y$$X$.
Recordar para los siguientes que la de von Neumann ordinal $2 = \left\{0,1\right\}$.
A menudo identificamos el powerset $\mathcal{P}(X)$ con el conjunto de funciones de $2^X$, ya que podemos pensar de este último como el conjunto de funciones características de los subconjuntos de a $X$. Deje $f \in 2^X$ ser una función y deje $Z \subseteq X$. Podemos estipular que si $f(x) = 1$$x \in Z$, y si $f(x) = 0$$x \not\in Z$.
La notación de exponente tiene sentido porque de la siguiente identidad de cardenal de la aritmética:
$$|X|^{|Y|} = |X^Y|.$$
Es decir, la cardinalidad de un cardenal elevado a la potencia de otro es simplemente la cardinalidad de las funciones de la última a la primera. El nombre de 'powerset' también tiene sentido una vez que pensaba en estos términos, ya que se puede construir fácilmente un bijection entre el $\mathcal{P}(X)$ $2^X$ mediante la identificación de subconjuntos con sus funciones características de $X$.
Como Rahul Narain puntos, el conjunto $X^2$ es, naturalmente, identificado con el producto cartesiano $X \times X$. Cada función de $f \in X^2$ será de la forma $\left\{(0, x), (1, y)\right\}$$x, y \in X$. Tomando $f(0)$ como el primer componente y $f(1)$ como la segunda, podemos construir un par de $(f(0) = x, f(1) = y)$. La colección de todos los pares será sólo el producto cartesiano de a $X$ con sí mismo.
Deje $X$ ser un conjunto infinito. Buscamos mostrar que $X^2$ $2^X$ son infinitas, por lo que muestra que ambos tienen infinitos subconjuntos. Esto se hace fácilmente mediante la construcción de un bijection entre los subconjuntos de e $X$. En primer lugar, supongamos que
$$Y = \left\{ f : f(0) = f(1), f \in X^2 \right\}.$$
Claramente $Y \subseteq X$. Ahora vamos a $G : Y \rightarrow X$, $G(f) = f(0)$. Esta es una inyección desde la singularidad de $f(0)$ está garantizada por la construcción de $Y$. La función inversa $G^{-1} : X \rightarrow Y$ es fácil de definir como
$$G^{-1}(x) = \left\{ (0, x), (1, x) \right\}$$
que una vez más debe ser una inyección. Tenga en cuenta que la identidad de la relación de $1_X = \left\{ (x, x) : x \in X \right\}$ guarda la misma relación con $Y$ como el producto cartesiano completo ¿a $X^2$.
La prueba de que $2^X$ es infinito ingresos obtenidos por el mismo método básico. Vamos
$$Z = \left\{ f : \exists{x} ( f(x) = 1 \wedge \forall{y} ( y \in X \wedge y \neq x \rightarrow f(y) = 0 ) ), f \in 2^X \right\}.$$
Vamos a construir un bijection entre el$Z$$X$. Vamos $H : Z \rightarrow X$, $H(f) = x$ donde $f(x) = 1$. A continuación, vamos a $H^{-1} : X \rightarrow Z$, $H^{-1}(x) = f$ para el único $f$ tal que $f(x) = 1$$\forall{y} ( y \neq x \rightarrow f(y) = 0)$.
Tenga en cuenta que lo que hemos esencialmente hecho aquí es crear un bijection entre el $X$ y todos sus subconjuntos que son los únicos. Más precisamente, el bijection se entre $X$ y las funciones características de los embarazos únicos. Desde $X$ es infinito, $Z$ debe ser infinito y por lo tanto así es $2^X$.
Sin embargo, algo mucho más fuerte también sostiene: la cardinalidad de a $2^X$ es estrictamente mayor que la cardinalidad de a $X$. Este es el Cantor del teorema.
Por último, desde la $\mathbb{N}$ es infinita, por lo que se $\mathbb{N}^2$$2^\mathbb{N}$: simplemente tome $X = \mathbb{N}$ en la anterior prueba. $Y$ $Z$ serán computables desde la prueba de construcciones bijections entre ellos y $X$, y por tanto tienen la misma cardinalidad como $\mathbb{N}$, es decir,$\aleph_0$.
riza
Puntos
170
De hecho, podemos identificar una función $f:Y\to X$ con un elemento de $\prod_Y X$ (un producto directo de copias de $X$ indexados por $Y$) considerando el componente con el índice de $y$ la imagen de $y$ bajo $f$. Esto conduce a lo que yo siento es una forma intuitiva de recordar el significado de $X^Y$ con muy poco esfuerzo.
Para números enteros $n$,$a^n=\underbrace{a\times a\times\cdots\times a}_n$. Del mismo modo para los conjuntos podemos optar por escribir
$$X^Y\cong \underbrace{X\times X\times \cdots \times X}_Y.$$
Mejor si uno ya está acostumbrado a pensar de indexado tuplas como las funciones del conjunto de índices.
