Show that the set is Uncountable

[rshalloo]

I've been looking at this for the past hour and I have a possible solution but as with all of abstract Algebra I can never tell if I'm right or if I am just making stuff up :P Could someone please help?

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

 

[HallsofIvy]

Isn't it also true that the set of all natural numbers has "twice as many numbers" as the set of all even numbers? But that surely does not show that the set of all natural numbers is not countable!

You cannot use terms like "twice as many" when talking about infinite sets. Have you ever seen a proof that a set is not countable? Have you ever seen a proof that the set of all real numbers is not countable? Mimic that. What you need to do is assume there already is some specific such mapping. Suppose we had some list of functions from N to {0, 1}. The function, $f_1$ maps 1 onto either 0 or 1. Define $\overline{f}(0)$ to be the other value (if $f_1(0)= 0$ then $\overline{f}(0)= 1$, if $f_1(0)= 1$, then $\overline{f}(0)= 0$). Define $\overline{f}(1)$ to be whichever of 0 and 1 $f_2(1)$ (the next function on list) is NOT. Use that to define $\overline{f}$ for all of N.

 

[rshalloo]

But If i have n natural numbers I have n/2 even number thus you could prove by induction that there would always be twice as many natural numbers as even numbers. When i say that there are twice as many elements of the set of functions as the set of natural numbers i mean that if i had 300 natural numbers i have 600 functions whereas if i have 300 natural numbers i only have 150 even numbers.

I've seen it once but i didnt really understand it. I tend to think of things geometrically and so this stuff tends to be quite difficult to understand

 

[gb7nash]

But If i have n natural numbers I have n/2 even number thus you could prove by induction that there would always be twice as many natural numbers as even numbers. When i say that there are twice as many elements of the set of functions as the set of natural numbers i mean that if i had 300 natural numbers i have 600 functions whereas if i have 300 natural numbers i only have 150 even numbers.

No no no. When dealing with infinite sets, you cannot apply these rules. "Twice as many" and dividing by 2 make no sense when dealing with infinity.

And to give you an idea of why you can't do this, there exists a bijection from [0,1] (all real numbers from 0 to 1) to [0,2] (all real numbers from 0 to 2). This means, infinitely speaking, there are the "same" number of real numbers from 0 to 1 and from 0 to 2. So unfortunately, you cannot have this kind of mentality when dealing with infinite sets.

 

[upsidedowntop]

You seem to be associating the cardinality of set to a sort of growth rate of the set, which isn't the right concept.

I'll give you a couple examples using the definition: two sets have the same cardinality if there exists a bijection between them.

The set of even natural numbers has the same cardinality as the set of odd natural numbers. The function f(n) = 2n is a bijection between the two sets. Every odd number has a double that is even, and every even number has a half which is odd.

The set of finite sequences of 0s and 1s has the same cardinality as the natural numbers or integers or rationals. You can use binary to unambiguously encode any of these forms of numbers as a finite sequence of 0s and 1s. That encryption is a bijection, so the sets have the same cardinality.

Even if sets A and B are subsets of the natural numbers, nothing in the definition of cardinality references that external set. So it can't matter if one of A or B takes up more of the containing set than the other.

Good luck!

 

[Agent M27]

These sort of proofs are sometimes easier to complete via contradiction. So in your case:

Assume that the set of all functions f:N -> (0,1) is countable...Also as with any proof, an accurate knowledge of the definitions is imperative. I'm not saying you don't, but just incase here are a few that are necessary.Let S be a set. S is countable iff S is finite or S is denumerable
S is uncountable iff S is not countable
Let S be a set. S is denumerable iff S ~ NHope this helps.

Joe

 

[LPerrott]

Look up Cantor diagonalization argument. That should help you. Proceed by contradiction. First, realize that the functions we are speaking about really yield a sequence of 1's and zero's. If the set of all these functions were countable, then we could put them into an matrix of infinite size e.g.

1010101010010...
1000100010010...
0010100001000...
...

and so on. Now, if the set were countable then every such f should correspond to a row in the matrix, however if we look at the diagonal of the matrix and set all the 0's to 1's and vice versa, then that sequence does NOT correspond to a row in the matrix. Why? Since we have found an existing sequence not in the matrix, then the set must be uncountable.

 

[rshalloo]

show that the Set of all Functions from N-> {0,1} is not a countable set where N = set of natural numbers
Thanks for all the replies after much head-desk and trying to understand cantors argument i think I've got it.
Ok so if i say that each function applied to the natural numbers will generate the following set of answers:
Natural number 1 2 3 4 5 6 7 8 9 ...
Function 1 applied to natural numbers 1 1 1 1 1 1 1 1 1...
Function 2 applied to natural numbers 0 1 0 1 0 1 0 1 0...
Function 3 applied to natural numbers 1 0 0 1 0 0 1 0 0...
...

Then I end up with a infinite table of 1's and zero's. This is a set of all possible functions between that take the natural numbers from 0-1. If i assume the set of all functions is countable then this is a table of all possible combinations of zeros and ones. But by using cantors diagonal argument I take the first element of the first sequence in this case a 1. and i change it to its opposite in this case zero. Then i repeat that process for the second element of the second sequence and the third element of the third sequemce and the nth element of the nth sequence. By doing this I can create a new combination of ones and zeros that isn't in my list. and thus isn't in my set of all functions which is a contradiction

Thus the set of all functions from N-> {0,1} is uncountable

Is that right?

 

[LPerrott]

that is correct

 

[rshalloo]

Cheers for the help everyone

 

[wisvuze]

I hope you still don't think that the natural numbers have twice as many elements as the even numbers :)

 

[LPerrott]

The proper way to think about it would be that the natural numbers are "finer" than the even numbers or the even numbers are "coarser" than the natural numbers ... I'm I correct in my thinking?

 

[rshalloo]

I hope you still don't think that the natural numbers have twice as many elements as the even numbers :)

No I've seen the error of my ways :P