Prove that {0,1}^N is uncountable.

[arcdude]

Homework Statement

Prove that {0,1}^N is uncountable.

(N = positive integers)

Homework Equations

f: N -> {0,1}

The Attempt at a Solution

f(n) = 0 or 1 for every n is an element of N.
I should treat n as the nth term of an infinitely long sequence of 0's and 1's.

 

[LCKurtz]

Are you familiar with Cantor's diagonal argument which shows the reals are uncountable?

 

[arcdude]

Yes, we discussed that today in class, but I'm a bit confused on Cantor's argument. We also discussed possibly proving the statement through contradiction, assuming that it is countable.

 

[HallsofIvy]

Every real number, between 0 and 1, can be written in binary notation as a list of "0"s and "1"s so your set is equivalent to the set of all real numbers between 0 and 1.

 

[LCKurtz]

Yes, we discussed that today in class, but I'm a bit confused on Cantor's argument. We also discussed possibly proving the statement through contradiction, assuming that it is countable.

Sounds like a good plan. Kind'a like Cantor's argument...

 

[arcdude]

Can you explain to me what Cantor's argument is though?

 

[LCKurtz]

Can you explain to me what Cantor's argument is though?

You can read about it here:
http://planetmath.org/encyclopedia/CantorsDiagonalArgument.html

 

[arcdude]

alright, thank you for your help!