My Math Forum How to prove P(N) is uncountable ?

 Computer Science Computer Science Forum

 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:
 Originally Posted by mcquintrix 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 ?
Better to prove that $|\mathcal{P}(S)|>|S|$ for any set $S$, then the result follows immediately

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:
 Originally Posted by mcquintrix 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 ?
Arrange integers in natural order. The sets are defined by "1" as integer is present and "0" as integer is absent.
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

,

,

,

# prove that p(n) is uncountable

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post 450081592 Real Analysis 2 November 23rd, 2011 07:34 PM arcdude Applied Math 1 November 23rd, 2011 12:46 PM whatlifeforme Number Theory 1 October 30th, 2011 05:53 AM cxc001 Applied Math 2 April 19th, 2010 12:31 PM vaevictis59 Applied Math 18 March 16th, 2010 10:14 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top