¿Cuál es el conjunto de todas las funciones de $\{0, 1\}$ $\mathbb{N}$equinumerous? Me han resuelto la pregunta cuando es al revés, pero yo no estoy haciendo ningún progreso aquí. Lo peor es que, no sé qué pensar de este tipo de problemas, e incluso cuando estaba funciones de$\mathbb{N}$$\{0, 1\}$, nunca me hubiera metido yo mismo sin ayuda. Cuando pienso acerca de esto pienso en lo siguiente: es una función, de modo que una cosa no puede ser enviado a dos+ cosas, pero las dos cosas puede ser enviado a la misma cosa. Así que al menos, estamos de asignación de 0 y 1 para el mismo elemento, y en la mayoría de los que estamos en un mapa de dos elementos diferentes. Pero que realmente no me dan nada... Gracias!
Respuestas
¿Demasiados anuncios?
$|\{\text{functions } \{0,1\} \to \mathbb{N} \}|= |\mathbb{N}^{\{0,1\}}|= |\mathbb{N}^2|$
De hecho, si usted está pensando en $\mathbb{N}^2$ como el conjunto de pares ordenados de números naturales, entonces la función
$\varphi: \{\text{functions } \{0,1\} \to \mathbb{N} \} \to \mathbb{N}^2$ se define como $\varphi(f)= (f(0),f(1))$
es un bijection.
Se trata de un inyectable: si $f\not=g$, $f(0)\not=g(0)$ o $f(1)\not=g(1)$, por lo tanto $\varphi(f)\not= \varphi(g)$.
Es un surjection: dado $(m,n)\in \mathbb{N}^2$, definir $f:\{0,1\} \to \mathbb{N}$ $f(0)=m$, $f(1)=n$. A continuación,$\varphi(f)=(m,n)$.
De hecho, para algunos la intuición, creo que lo que esta bijection está diciendo es que una función $\{0,1\}\to \mathbb{N}$ está totalmente determinado por un par de números naturales. Que podían ser sino $f(0)$$f(1)$? :)
Así que, ahora me reclama que $|\mathbb{N}^2|=|\mathbb{N}|$. De hecho, es el producto cartesiano de dos conjuntos contables, y el producto cartesiano de un número finito de conjuntos contables es contable, por lo tanto el conjunto de funciones de $\{0,1\} \to \mathbb{N}$ es contable, es decir, equinumerous a $\mathbb{N}$.
Comentar no puede usar el cardenal aritmética: una más constructiva de la prueba debería exhibir un bijection. Ver a esta pregunta: ¿Cómo se obtiene la fórmula para este bijection de $\mathbb{N}\times\mathbb{N}$ a $\mathbb{N}$? que ataca el problema de mostrar que $|\mathbb{N}\times \mathbb{N}|=|\mathbb{N}|$ más directamente.
AÑADIDO: Una obvia de que la generalización de la anterior conduce a que el hecho de que, para $n\in \mathbb{N}$, $|\{\text{functions } \{0,\dots,n-1\} \to \mathbb{N}\}| = |\mathbb{N}^n|$. Teniendo esto en mente, ahora se olvida jamás definidas $\mathbb{N}^k$ cualquier $k\in \mathbb{N}$. Vamos a tener un enfoque diferente.
Deje $I$ ser cualquier conjunto dado. Definir $\mathbb{N}^I$ $$\mathbb{N}^I := \{\text{functions } I \to \mathbb{N}\}$$
Esta es la notación habitual para el conjunto de las funciones de$I$$\mathbb{N}$.
Ahora, en el conjunto de la teoría de Zermelo-Fraenkel), el número de $k\in \mathbb{N}$ es definido como el conjunto $\{0,\dots,k-1\}$. ¿Qué tal si nos tomamos $I=\{0,\dots,k-1\}$? Tenemos que $$\mathbb{N}^k=\mathbb{N}^{\{0,\dots,k-1\}} = \{\text{functions } \{0,\dots,k-1\} \to \mathbb{N}\}$$
En particular, con $k=2$, obtenemos que $\mathbb{N}^2=\{\text{functions } \{0,1\} \to \mathbb{N} \}= \{\text{functions } 2 \to \mathbb{N}\}$. Ahora la anterior prueba demuestra que nuestro nuevo $\mathbb{N}^2$ es equinumerous para el conjunto de pares ordenados de números naturales. Esto es agradable. Por qué?
Bueno, en primer lugar observar que equinumerous conjuntos son indistinguibles desde el punto de vista de la teoría de conjuntos (en palabras de fantasía: bijections son isomorphisms en Conjunto). Así que si dos conjuntos son equinumerous, no hay ningún daño hecho con tomar cualquiera de ellos como la definición de la serie.
Entonces, observar que esta definición es en mucho mayor generalidad. Hemos definido $\mathbb{N}^I$ para cualquier conjunto $I$. Con nuestra definición anterior, sólo se pudo extender la generalidad para cualquier finito set $I$, es decir, la definición de $\mathbb{N}^I$ como el conjunto de $|I|$-uples de números naturales: esta definición no tiene sentido a priori infinitas $I$.
Una última observación: en este último anexo, $\mathbb{N}$ puede ser tomado a cualquier conjunto, por supuesto.
DanV
Puntos
281
El conjunto de funciones de $\{0,1\}$ $\mathbb N$(denotado por $A$ de aquí a final) puede ser visto como el conjunto de todos los pares ordenados en $\mathbb N\times\mathbb N$.
Vamos a demostrar que:
Supongamos $f\in A$,$f(0)\in\mathbb N$$f(1)\in\mathbb N$, por lo tanto el par $\langle f(0),f(1)\rangle\in\mathbb N\times\mathbb N$, esto significa que esta asignación es de hecho bien definidos.
Supongamos $f,g\in A$ dos funciones diferentes, $f(0)\neq g(0)$ o $f(1)\neq g(1)$. De cualquier manera $\langle f(0),f(1)\rangle\neq\langle g(0),g(1)\rangle$, también tenemos que esta asignación es inyectiva (envía dos elementos diferentes a resultados diferentes).
Supongamos $\langle a,b\rangle\in\mathbb N\times\mathbb N$, definir $f\in A$ $f(0)=a, f(1)=b$ $f$ se asigna a $\langle a,b\rangle$, por lo que la asignación es a $\mathbb N\times\mathbb N$.
Con todo, tenemos la asignación es un bijection, por lo que es suficiente para entender cuál es el tamaño de $\mathbb N\times\mathbb N$.
La cardinalidad de esta colección es, de hecho,$\aleph_0$. Hay dos formas comunes para mostrar que:
Cantor de la función de sincronización, $\langle a,b\rangle\mapsto \frac{(a+b)(a+b+1)}{2}+a$, y la muestra es de hecho un bijection.
Cantor-Bernstein del teorema, nos encontramos con inyecciones de $\mathbb N$ a $\mathbb N\times\mathbb N$ y vice-versa. Claramente $\mathbb N$ no es de mayor cardinalidad (por $n\mapsto \langle 0,n\rangle$, lo que es claramente inyectiva), por otro lado $\langle a,b\rangle\mapsto 2^a3^b$ es también un inyectiva de asignación, lo que implica la $|\mathbb N\times\mathbb N|\le|\mathbb N|$, y por lo tanto $\mathbb N$ $\mathbb N\times\mathbb N$ tienen la misma cardinalidad.
David HAust
Puntos
2696
% Toque $\rm\quad\ \ |Maps(\{0,1\},\mathbb N)| \le |\mathbb N|\ $$\rm\ f\:\mapsto\: 2^{\:f(0)}\ 3^{\:f(1)}\ $es inyectiva (uno a uno).
Reverso $\rm\:|Maps(\{0,1\},\mathbb N)| \ge |\mathbb N|\:$ que incluye el $\rm\:|\mathbb N|\:$ constante de los mapas $\rm\:f_{\:n}\:$asignación $\rm\ 0,1\:$ $\rm\:n\:.$
Justin Dearing
Puntos
695
Que $f$ sea una función de $\{0,1\}$ $\mathbb{N}$. A continuación, $f$ está únicamente determinado por sus valores en $0$ y $1$. $f(0)$ puede ser cualquier número natural y puede así $f(1)$. Así que esto corresponde a $\mathbb{N}^2$. Otra manera de decirlo es que el mapa $f \rightarrow (f(0),f(1))$ es una biyección del conjunto de todas las funciones de $\{0,1\} $ $\mathbb{N}$ $\mathbb{N}^2$.
