• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • Thread starter arcdude
  • Start date
  • #1
8
0

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.
 

Answers and Replies

  • #2
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,523
737
Are you familiar with Cantor's diagonal argument which shows the reals are uncountable?
 
  • #3
8
0
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.
 
  • #4
HallsofIvy
Science Advisor
Homework Helper
41,810
934
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.
 
  • #5
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,523
737
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...
 
  • #6
8
0
Can you explain to me what Cantor's argument is though?
 
  • #7
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,523
737
Can you explain to me what Cantor's argument is though?
You can read about it here:
http://planetmath.org/encyclopedia/CantorsDiagonalArgument.html [Broken]
 
Last edited by a moderator:
  • #8
8
0
alright, thank you for your help!
 

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

Replies
5
Views
1K
Replies
7
Views
2K
  • Last Post
3
Replies
55
Views
12K
Replies
4
Views
4K
Replies
1
Views
11K
Replies
5
Views
4K
Replies
18
Views
10K
Replies
2
Views
2K
  • Last Post
Replies
4
Views
329
Top