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

arcdude · Nov 23, 2011

1. The problem statement, all variables and given/known data
Prove that {0,1}^N is uncountable.

(N = positive integers)

2. Relevant equations
f: N -> {0,1}

3. 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 · Nov 23, 2011

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

arcdude · Nov 23, 2011

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 · Nov 23, 2011

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 · Nov 23, 2011

arcdude said: ↑

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 · Nov 23, 2011

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

LCKurtz · Nov 23, 2011

arcdude said: ↑

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

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

arcdude · Nov 23, 2011

alright, thank you for your help!