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

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

Homework Help Overview

The problem involves proving that the set {0,1}^N is uncountable, where N represents the positive integers. The discussion references Cantor's diagonal argument and its application to this context.

Discussion Character

  • Exploratory, Conceptual clarification, Assumption checking

Approaches and Questions Raised

  • Participants discuss Cantor's diagonal argument and its relevance to proving the uncountability of {0,1}^N. There are attempts to clarify the argument and explore the possibility of using proof by contradiction.

Discussion Status

The discussion is ongoing, with participants seeking clarification on Cantor's argument and considering different approaches to the proof. Some guidance has been offered regarding the connection between the set and real numbers.

Contextual Notes

Participants express confusion about Cantor's argument and its application, indicating a need for further exploration of the concepts involved.

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
2K
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
2K
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