Probar que un conjunto es incontable.

Question

Necesito demostrar que el conjunto de todas las funciones $\mathcal{F}:\mathbb{N}\rightarrow \left \{ 0,1 \right \}$ es incontable.

No estoy muy seguro del todo de cómo hacerlo. Mi idea inicial era intentar mostrar que $\mathcal{F} \rightarrow \mathbb{N}$ no fue un bijection pero no me queda claro del todo y la necesidad de algunos de gran ayuda.

Gracias!!!

Answer 1

NO voy a hacer de esto una prueba por contradicción.

Deje $f_1,f_2,f_3,\ldots$ ser cualquier secuencia de dichas secuencias. Por lo tanto $f_1$ es la secuencia de las $f_1(1),f_1(2),f_1(3),\ldots$.

Tratamos de demostrar que la secuencia de $(1-f_k(k))_{k=1}^\infty$ no es una de las secuencias de $f_1,f_2,f_3,\ldots$, aunque se trata de un miembro de $\mathcal F$.

Answer 2

Usted debe tratar de una diagonalisation argumento, como Cantor.

Supongamos que hay una completa contables lista de funciones, es que debe ser fácil dar una construcción de una nueva función que varía con cada uno.

Answer 3

Su conjunto $\mathcal F$ es equipotenciales para el juego de poder de $\mathbb N$. El Cantor del teorema luego le dice que debe ser de multitud de cardinalidad. Usted puede comprobar aquí: https://en.wikipedia.org/wiki/Cantor%27s_theorem

Answer 4

Sugerencia. Usted probablemente ya sabe que $P(\mathbb{N})$ es incontable. Si es así, sería suficiente para mostrar que no es un bijection entre el $P(\mathbb{N})$ y el conjunto de funciones de$\mathbb{N}$$\{0,1\}$. Para encontrar un bijection, pensar acerca de cómo usted puede codificar un subconjunto $A$ $\mathbb{N}$ como una secuencia infinita de ceros y unos.