Demostrando un conjunto de funciones de $\mathbb{N}$ $\{1,0\}$ es contable

Question

La pregunta es para probar que el conjunto $S$ de todas las funciones de $f:\mathbb{N}\to \{0,1\}$, por lo que $f^{-1}(\{1\})$ es finito, es contable.

Después de considerar esto por un tiempo, yo no entiendo lo que significa, pero no tengo idea de cómo resolverlo. ¿Cómo puedo incluso hacer una función de neutro números de funciones y cómo puedo probar que tal función es bijective?

Ni siquiera estoy seguro de cómo empezar esto, así que voy a ser feliz con cualquier empuje en la dirección correcta.

edit: Gracias a ustedes por sus respuestas. de ellos me di cuenta de que me estoy perdiendo algo, ya que yo no entiendo la mitad de lo que usted dijo. Aunque estoy un poco sorprendido ya que solo he perdido 1 hora de conferencia una vez y no recuerdo discutiendo la mayoría de lo escrito aquí. El ejercicio en sí es debido en un poco menos de una semana. Voy a ir a estudiar un poco y volver a este pronto. Se deja abierta la pregunta en el ínterin.

Edit 2: VALE, después de preguntar un poco y leyendo algunas cosas, y después de estar sentado durante 15 minutos sólo thining acerca de todas las piezas, creo que por fin entiendo de esto. Yo no he escrito la prueba todavía, pero siento que sé cómo hacerlo, así que voy a ser el cierre de la pregunta. Gracias otra vez a todos.

Answer 1

Usted no debe tratar de encontrar un bijection: que se vuelve muy desordenado muy rápidamente. Usted debe buscar un argumento indirecto.

Aquí está un posible enfoque. Hay una fácil bijection entre el conjunto de funciones y el conjunto de los subconjuntos finitos de $\Bbb N$: par una función de $f$$\{k\in\Bbb N:f(k)=1\}$. Para cada una de las $n\in\Bbb N$ deje $[\Bbb N]^n$ el conjunto de los subconjuntos de a $\Bbb N$ tener exactamente $n$ elementos. Si usted puede demostrar que cada una de las $[\Bbb N]^n$ es contable, entonces puede utilizar el hecho de que la unión de una contables de la familia de conjuntos contables es contable.

Para mostrar que $[\Bbb N]^n$ es contable, encontrar una inyección (uno-a-uno de mapeo) de $[\Bbb N]^n$ a $\Bbb N^n$, el conjunto de $n$-tuplas de números naturales. (Estoy asumiendo aquí que ya has demostrado que $\Bbb N^n$ es contable.) SUGERENCIA: puede hacer una lista de cualquier conjunto de números naturales en orden creciente.

Answer 2

Consejo: Cualquier número natural puede escribirse en binario. Anteponer una secuencia infinita de ceros al frente de una representación binaria y luego invertirlo.

Answer 3

Tal función está únicamente determinada por $f^{-1}({1})$, puede construir una biyección entre el conjunto de tales funciones y el conjunto de todos los subconjuntos finitos de $\mathbb N$.

Así, tenemos que demostrar que el conjunto de todos los subconjuntos finitos de $\mathbb N$ es contable...

Sugerencia ¿Puede demostrar que para cada $n$, el conjunto de subconjuntos de $\mathbb N$ $n$ elementos es contable?

¿Puede resolver el problema desde aquí?

Answer 4

Sugerencia: primero intentar demostrar que el conjunto de todas las funciones que $|f^{-1}({1})|=1$ es contable. Luego lo mismo para el conjunto de todas las funciones que $|f^{-1}({1})|=2$. Luego generalizar.