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

  • Thread starter Thread starter arcdude
  • Start date Start date
Click For Summary
SUMMARY

The discussion centers on proving that the set {0,1}^N is uncountable, utilizing Cantor's diagonal argument. Participants emphasize that each sequence in {0,1}^N corresponds to a unique real number between 0 and 1, establishing a direct equivalence to the uncountable set of real numbers. The proof strategy discussed includes using contradiction by assuming countability and demonstrating the resulting inconsistencies. Familiarity with Cantor's argument is essential for understanding this proof.

PREREQUISITES
  • Understanding of Cantor's diagonal argument
  • Familiarity with binary notation
  • Basic knowledge of set theory
  • Concept of countable vs. uncountable sets
NEXT STEPS
  • Study Cantor's diagonal argument in detail
  • Explore proofs of uncountability for other sets
  • Learn about the implications of uncountability in set theory
  • Investigate the relationship between binary sequences and real numbers
USEFUL FOR

Mathematics students, educators, and anyone interested in set theory and proofs of uncountability will benefit from this discussion.

arcdude
Messages
8
Reaction score
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.
 
Physics news on Phys.org
Are you familiar with Cantor's diagonal argument which shows the reals are uncountable?
 
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.
 
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.
 
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...
 
Can you explain to me what Cantor's argument is though?
 
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
 
Last edited by a moderator:
alright, thank you for your help!
 

Similar threads

Prove every subset of countable set is either finite or else countable
  • · Replies 1 ·
Replies
1
Views
2K
Showing that a pathological function is only continuous at 0
  • · Replies 7 ·
Replies
7
Views
2K
Finding the nth roots of a complex number
  • · Replies 22 ·
Replies
22
Views
1K
Prove: f_n Convergence Implies f(x)=c
  • · Replies 7 ·
Replies
7
Views
2K
Finding the Maximum Value of f(x)=x(1-x)^n in [0,1]: A Calculus Problem
  • · Replies 3 ·
Replies
3
Views
2K
Prove that a function from [0,1] to [0,1] is a homeomorphism
  • · Replies 5 ·
Replies
5
Views
2K
Prove that ##\lim\limits_{x \to \infty} f(x) = 0##
  • · Replies 3 ·
Replies
3
Views
1K
Bounded non-decreasing sequence is convergent
  • · Replies 5 ·
Replies
5
Views
2K
Finding a closed form expression for an infinite union
  • · Replies 2 ·
Replies
2
Views
1K
How should I use the Jacobi equation to determine the nature of this?
  • · Replies 5 ·
Replies
5
Views
2K