- #1

- 52

- 0

## Homework Statement

Show that the Set of all Functions from N-> {0,1} is not a countable set where N = set of natural numbers

## Homework Equations

Only thing I can think of really is that If it is countable then there is a bijection to the Natural numbers

## The Attempt at a Solution

Well ok if there is a bijection with the natural numbers this implies that the cardinality of both sets is the same. So to prove that it is not countable I will prove that the cardinality of the set of all functions is greater than the cardinality of the natural numbers

So if I were to list out all of the natural numbers 1,2,3,4.... and put each of them through diff functions then for each member of the natural numbers there are 2 possible outcomes either 0 or 1 thus 2 possible functions. If 2 functions give the same answer i assume they are essentially the same function. So if i have n natural numbers i have 2n functions So i always have twice as many functions as natural numbers thus the cardinality of the set of functions >the cardinality of natural numbers

Therefore The set of all function from N-> {0,1} is not a countable set

So what do you think? is this ok or am i just talking through my backside