Register to reply 
Who is right here? Are the amount of numbers between both 0 to 1 and 0 to 2 the same?by tahayassen
Tags: numbers 
Share this thread: 
#19
Jan213, 05:46 PM

P: 772




#20
Jan213, 08:38 PM

P: 1,268

Okay, I'm not sure how to construct these infinite binary strings but I do understand why P(N) is of uncountable cardinality. I have a few more questions.
I have been reading about "beth numbers" and this seems to be the name for the "order of infinity." So here are my questions: Is the beth number the sole indicator of cardinality of uncountable sets? If so, this would imply that P(N) and R have the exact same cardinality, right? Is the power set concept the only source of constructing a "higher order" infinity? Are there any sets that we naturally consider that aren't derived from taking the power set of some other set with a beth number greater than two? I do realize that this question is pretty much identical to my previous one, but I guess what I'm asking is if there is a set with a beth number greater than or equal to 2 that we could describe in some other way than a power set of some other set? I'm sorry for kind of derailing the topic but I find this really cool, as a grad, what focuses on this type of thing? Is it just set theory? 


#21
Jan213, 09:02 PM

Mentor
P: 18,011

Note, that it might happen that there exists a set A such that [itex]\mathbb{N}\leq A\leq \mathbb{R}[/itex]. So it is certainly not the case that [itex]\mathbb{R}[/itex] is the smallest uncountable set. This is only true under the continuum hypothesis. Incidentally, it is true that [itex]\mathbb{R}=\mathbb{P}(\mathbb{N})[/itex]. But this does not follow from beth numbers. For example, [itex]\mathcal{P}(\mathbb{N})[/itex] are a higher order of infinity than [itex]\mathbb{N}[/itex]. But there might be a subset A of [itex]\mathcal{P}(\mathbb{N}[/itex] such that [tex]\mathbb{N}<A<\mathcal{P}(\mathbb{N})[/tex] So the power set might immediately give us many new orders of infinity instead of just one. Only under the GCH, we get one new order of infinity. 


#22
Jan213, 09:12 PM

P: 1,268

Thank you
Unfortunately I just searched my university's course offerings and the only mention of set theory is for classes I've already taken, but were introductory and only "applied" basic set theory to proofs and such. Looks like this will be an independent study. 


#23
Jan213, 10:38 PM

Sci Advisor
P: 820




#24
Jan213, 10:45 PM

Mentor
P: 18,011




#25
Jan213, 10:56 PM

Sci Advisor
P: 820




#26
Jan313, 10:57 AM

Sci Advisor
HW Helper
P: 11,893

Where does my naïve proof fail ? P(N)  the power set of N = the set of all subsets of N. [itex] \mathbb{N} \subset \mathcal{P}(\mathbb{N}) [/itex] and any proper subset of N is countable and so is their number So P(N) is the disjoint reunion of N and the set of all proper subsets of N, hence countable, hence has the same cardinality with N. 


#27
Jan313, 11:00 AM

P: 772

The union of countably many countable sets is countable, but that's no guarantee that the set of all such sets is countable. 


#28
Jan313, 11:15 AM

Mentor
P: 18,011

Here is a cool proof that [itex]\mathcal{P}(\mathbb{N})[/itex] is uncountable: Assume we have a bijection [tex]f:\mathbb{N}\rightarrow \mathcal{P}(\mathbb{N})[/tex] Define the following subset of [itex]\mathbb{N}[/itex]: [tex]A=\{x\in \mathbb{N}~\vert~x\notin f(x)\}[/tex] Since f is surjective, there exists an [itex]a\in \mathbb{N}[/itex] such that [itex]f(a)=A[/itex]. There are two possibilities: either [itex]a\in A[/itex] or [itex]a\notin A[/itex]. But if [itex]a\in A=f(a)[/itex], then [itex]a\notin f(a)[/itex] by definition of [itex]A[/itex]. And if [itex]a\notin A=f(a)[/itex], then by definition of [itex]A[/itex], we would have [itex]a\in A[/itex]. So both possibilities lead to a contradiction. So the original statement that a bijection exists, must be a contradiction. The proof that [itex]\mathcal{P}(\mathbb{N})[/itex] has the same cardinality as [itex]\mathbb{R}[/itex] is a bit harder. But here is a way to construct a bijection between [itex]\mathcal{P}(\mathbb{N})[/itex] and [0,1)(I'll leave the details to the reader and I'll try to find a reference). Take a subset [itex]A\subseteq \mathbb{N}[/itex]. Define [itex]x_n[/itex] as 0 if [itex]n\notin A[/itex] and define it as 1 if [itex]n\in A[/itex]. Then let [tex]0.x_1x_2x_3x_4...[/tex] be a number in [0,1] written in binary notation. For example, the set [itex]\{1,4,6\}[/itex] corresponds to [itex]0.1001010000000...[/itex]. The even numbers correspond to [itex]0.010101010101...[/itex]. And the primes correspond to [itex]0.0110101000101...[/itex]. This is clearly a surjection. A technical detail is that this does not define an injection. The reason is that one number can have multiple binary representations. For example: [itex]0.01=0.00111111111111111...[/itex]. So the sets [itex]\{2\}[/itex] and [itex]\{3,4,5,6,7,...\}[/itex] are sent to the same number in [0,1]. This issue can be solved by remarking that such issue only arises with finite sets in [itex]\mathbb{N}[/itex] and that the collection of finite subsets of [itex]\mathbb{N}[/itex] is countable. 


#29
Jan313, 11:29 AM

P: 1,268

From both his context and the standard definition, he is talking about any subset of N that is not N itself. 


#30
Jan313, 11:32 AM

P: 1,268

You do say that "they are countable and so is their number" but the latter part seems to be an assumption. There are countably infinite different sizes a subset of N can be, and countably infinite choices for elements in that subset of a specified size. Therefore you could never "count" to the next "set size" choice because you are already at the "limit of countability" when considering how many choices of elements their are in that specific choice of set size. When attempting to count you would be "stuck" on a set size of 1 (or w/e you chose) due to the countably infinite choices of the elements. This is exactly the same idea as being "stuck" when trying to count the real numbers, you are "stuck" because there are countably infinite decimal places to consider. So as a whole, the possibilities cannot be counted in either case. But that's my weird way. 


#31
Jan313, 03:05 PM

Sci Advisor
HW Helper
P: 11,893

I thank you all for your kind replies.



Register to reply 
Related Discussions  
Fortran: Searching through a list of numbers and finding which numbers meet criteria  Programming & Computer Science  3  
Showing that a series of numbers has an infinite amount of composites  Calculus & Beyond Homework  9  
Write a Java program to convert binary numbers to decimal numbers.  Engineering, Comp Sci, & Technology Homework  2  
Sophie Germain Triangular Numbers: An Explicit (Simple/r) Formula via Pell Numbers  Linear & Abstract Algebra  0 