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!

Log in or Sign up

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

arcdude

LCKurtz

arcdude

HallsofIvy

LCKurtz

arcdude

LCKurtz

arcdude

Prove lim na^n = 0 when 0 < a < 1 (Replies: 4)

Prove/Disapprove n2 + 3n + 1 is prime for n > 0 (Replies: 13)

Prove the integral of f over [0,1] is 1. f=(n+1)x^n when 0<=x<1; f=1, when x=1 (Replies: 5)

Use the definition of convergence to prove that the lim (1/2)^n=0 (Replies: 1)

Prove 2^0+ +2^n=2^{n+1}-1 (Replies: 4)