My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Thanks Tree2Thanks
  • 1 Post By CaptainBlack
  • 1 Post By mathman
Reply
 
LinkBack Thread Tools Display Modes
January 14th, 2015, 01: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 ?
mcquintrix is offline  
 
January 14th, 2015, 08:45 PM   #2
Senior Member
 
Joined: Jan 2012
From: Erewhon

Posts: 245
Thanks: 112

Quote:
Originally Posted by mcquintrix View Post
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
Thanks from mcquintrix
CaptainBlack is offline  
January 15th, 2015, 05:42 PM   #3
Global Moderator
 
Joined: May 2007

Posts: 6,528
Thanks: 589

Quote:
Originally Posted by mcquintrix View Post
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.
Thanks from mcquintrix
mathman is offline  
January 19th, 2015, 10:02 PM   #4
Newbie
 
Joined: Jan 2015
From: California

Posts: 2
Thanks: 0

Smile

Thank you
mcquintrix is offline  
Reply

  My Math Forum > Science Forums > Computer Science

Tags
prove, uncountable



Search tags for this page
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 06:34 PM
Prove that f: N -> {0,1} is uncountable arcdude Applied Math 1 November 23rd, 2011 11:46 AM
Uncountable whatlifeforme Number Theory 1 October 30th, 2011 04:53 AM
Set Theory: Prove the set of complex numbers is uncountable cxc001 Applied Math 2 April 19th, 2010 11:31 AM
Surjection, Uncountable Set vaevictis59 Applied Math 18 March 16th, 2010 09:14 AM





Copyright © 2018 My Math Forum. All rights reserved.