
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
January 14th, 2015, 02:27 PM  #1 
Newbie Joined: Jan 2015 From: California Posts: 2 Thanks: 0  How to prove P(N) is uncountable ?
How do i prove that P(N) is uncountable, I can't use the diagonalization method for sure here. Can anyone explain how do I go about solving this ? One hint is that I have to equate P(N) to another uncountable set such as set of Real numbers. or a infinite number of sets which contain infinite sequence of binary. A = {0 ,1,1,0,0,0,1,....} B = {1,1,0,1,1,0,1......} C = {0,0,1,0,0,1,0,.....} ... ... How do I give relation between P(N) and the above given sets ? 
January 14th, 2015, 09:45 PM  #2  
Senior Member Joined: Jan 2012 From: Erewhon Posts: 245 Thanks: 112  Quote:
You will find such a proof here CB  
January 15th, 2015, 06:42 PM  #3  
Global Moderator Joined: May 2007 Posts: 6,641 Thanks: 625  Quote:
A is set containing 2,3,7,... B is set containing 1,2,4,5,7,... C is set containing 3,6,... Assuming you have a complete countable list, then you can construct a set not in the list by the usual method.  
January 19th, 2015, 11:02 PM  #4 
Newbie Joined: Jan 2015 From: California Posts: 2 Thanks: 0 
Thank you 

Tags 
prove, uncountable 
Search tags for this page 
show that p(n) is uncountable,p(n) is uncountable,prove that P(N) is not countable,prove that p(n) is uncountable
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
show that M is uncountable  450081592  Real Analysis  2  November 23rd, 2011 07:34 PM 
Prove that f: N > {0,1} is uncountable  arcdude  Applied Math  1  November 23rd, 2011 12:46 PM 
Uncountable  whatlifeforme  Number Theory  1  October 30th, 2011 05:53 AM 
Set Theory: Prove the set of complex numbers is uncountable  cxc001  Applied Math  2  April 19th, 2010 12:31 PM 
Surjection, Uncountable Set  vaevictis59  Applied Math  18  March 16th, 2010 10:14 AM 