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

arcdude

## Homework Statement

Prove that {0,1}N is uncountable.

(N = positive integers)

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.

Homework Helper
Gold Member
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.

Homework Helper
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.

Homework Helper
Gold Member
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?