Question

Why set of all functions $f:N \rightarrow$ {0,1} is uncountably infinite?

Comments

chnage the question to set of all functions

Answer 1

Here is how I proved that set of all numbers from N -> {0,1} is uncountably infinite. It is similar to how cantor proved that real numbers are countably infinite.

 

Let us assume there are countably infinite functions from N -> {0,1}. So every natural number is mapped to either 0 or 1.

That is, functions can be represented as

 

f1 : 010010...

f2: 1011101...

f3: 0001011...

.

. and so on

Note that the 0 1 sequence here is how the natural numbers are being mapped to 0 or 1 for each function. Now if someone claims that this countably infinite, I can pick the 1st digit from 1st function, 2nd digit from 2nd function, 3rd digit from 3rd function and so on and flip those digits and I will have a function which is not in this supposedly countably infinite list. Thus, I can say that the claim that all set of functions from N -> {0,1} is countably infinite is false. Therefore, this is uncountably infinite. Its easier to understand this proof if you already understand cantor's proof of how real numbers are uncountable.

Answer 2

there are counatbly infinte natrual numbers.

there will be countably infinite number of elemnents in mapping N->{0,1}

e.g.

ASSUME N has 5 elements then N*{0,1} has 10 ordered pair(cartesian product}

now there can be muliplte funcitions,

function is a subset of cross product (some restircions but lets forget this

now we have 10 elements and all the subset of that 2^10.

similarly here 2^ (countable infite) =uncounatble ifiinite

remeber this rule of exponential(i dont have any proof)

http://cs.stackexchange.com/questions/51319/number-of-finite-strings-over-a-countably-infinite-alphabet

Answer 3

N : Natural numbers which is countable infinite

Lets find the number of functions possible,

1 -- 2 choices

2 -- 2 choices

3 -- 2 choices

4 -- 2 choices

. 

.

.    2 choices

Total Functions = 2^N

Using cantor's theorem, refer https://en.wikipedia.org/wiki/Cantor%27s_theorem

We can say that power set of a countable infinite set is UNCOUNTABLE. Hence Proved