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:
Number Nine
#19
Jan2-13, 05:46 PM
P: 772
Quote Quote by 1MileCrash View Post
Forgive me if I'm not understanding but,

The number of elements of P(N) is the number of possible subsets of natural numbers that can be formed.

That is surely uncountable, as I can combine any number of any natural numbers I want to form some subset. If I call one subset, the non-proper subset, the entire set of natural numbers, one subset, what's another subset? The subset of 1 million of any natural numbers? 2 million any natural numbers? Considering all singleton sets of each natural number is already a countably infinite number of subsets, and there are uncountably many subsets besides those, it doesn't work in my brain to call P(N) a set of countable cardinality.

EDIT:

I found this

http://www.earlham.edu/~peters/writing/infapp.htm#thm3

Which I guess is a much better and more formal version of what I'm thinking.
You're right, P(N) is uncountable. An easy way to see this is to identify each element of P(A) with an infinite binary string (easy to show that this is a bijection) and note that the set of all such strings is uncountable.
1MileCrash
#20
Jan2-13, 08:38 PM
1MileCrash's Avatar
P: 1,292
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?
micromass
#21
Jan2-13, 09:02 PM
Mentor
micromass's Avatar
P: 18,229
Quote Quote by dextercioby View Post
Just as a curiosity, what's the connection between the discrete/countable infinite sets (sequences) [itex]\mathcal{P}^{n}(\mathbb{R})[/itex] and [itex] \aleph_{n} [/itex] ?
The only thing we can say for sure is that [itex]|\mathcal{P}^n(\mathbb{R})|\geq \aleph_{n+1}[/itex]. Equality is not true in general. If you assume the GCH (generalized continuum hypothesis) as an axiom, then equality is true.

Quote Quote by 1MileCrash View Post
Ah.. I failed to think of deriving a set from an uncountable set in such a way that the cardinality must be greater. It doesn't make much sense at all to say that a set and it's power set have the same cardinality. That is easy to see.

Thank you.

Is this limited to the idea of power sets? It feels like this could only occur when you "build" a "higher order" uncountable set from a previously uncountable set.

Also- the power set of the naturals would certainly be of higher cardinality than the naturals and thus not at a one-to-one correspondence with the naturals and therefore uncountable, right?

Does that make P(N) have the same cardinality as R, and P(P(N)) have the same cardinality as P(R)?

Or am I oversimplifying the idea?
It is certainly true that [itex]\mathcal{P}(\mathbb{N})[/itex] has the same cardinality as [itex]\mathbb{R}[/itex]. But this requires an explicit proof.
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.

Quote Quote by dextercioby View Post
P^n (N) (=P(P(P...P(N)))) for arbitrary n has the same cardinality with N.
No this is false, they all have strictly larger cardinality as [itex]\mathbb{N}[/itex] as long as n>0.

Quote Quote by 1MileCrash View Post
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."
The notion you want are actually aleph numbers and not beth numbers. Beth numbers might miss some orders of infinity. Only under the GCH, it is true that the beth numbers capture all orders 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?
Again: it is the aleph numbers that indicates the cardinality of uncountable sets. The beth numbers are intimately related to power sets.
Incidentally, it is true that [itex]|\mathbb{R}|=|\mathbb{P}(\mathbb{N})|[/itex]. But this does not follow from beth numbers.

Is the power set concept the only source of constructing a "higher order" infinity?
The ZFC axioms (axioms for set theory) give some ways to construct new sets. But it is indeed only the power set axiom that allows you to construct new orders of infinity. Note that this does not mean that the power sets are the only orders of infinity.

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.

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?
This question cannot be answered in ZFC framework and requires a new axiom. The GCH axiom says that all orders of infinity correspond to power sets. However, it is also consistent with ZFC that there are sets with a beth number greater than two that aren't derived from taking the power set (however, they will be "subsets" of some power set though)

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?
You need to study set theory for this. A very good book is "Introduction to Set theory" by Hrbacek and Jech.
1MileCrash
#22
Jan2-13, 09:12 PM
1MileCrash's Avatar
P: 1,292
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.
pwsnafu
#23
Jan2-13, 10:38 PM
Sci Advisor
P: 827
Quote Quote by micromass View Post
Only under the GCH, it is true that the beth numbers capture all orders of infinity.
Err, IIRC, GCH is only powerful enough to show weak limit cardinals are equivalent to strong limit cardinals. That doesn't imply ZF+GCH doesn't have inaccessible cardinals at all. Do you have a source?
micromass
#24
Jan2-13, 10:45 PM
Mentor
micromass's Avatar
P: 18,229
Quote Quote by pwsnafu View Post
Err, IIRC, GCH is only powerful enough to show weak limit cardinals are equivalent to strong limit cardinals. That doesn't imply ZF+GCH doesn't have inaccessible cardinals at all. Do you have a source?
Even innaccessible cardinals must have an aleph-number. So under GCH, all cardinals have a beth-number. Do you think these statements are wrong?
pwsnafu
#25
Jan2-13, 10:56 PM
Sci Advisor
P: 827
Quote Quote by micromass View Post
Even innaccessible cardinals must have an aleph-number. So under GCH, all cardinals have a beth-number. Do you think these statements are wrong?
No you are right. I was only thinking about power sets and forgetting the supremum operation.
dextercioby
#26
Jan3-13, 10:57 AM
Sci Advisor
HW Helper
P: 11,915
Quote Quote by micromass View Post
[...]
It is certainly true that [itex]\mathcal{P}(\mathbb{N})[/itex] has the same cardinality as [itex]\mathbb{R}[/itex]. But this requires an explicit proof.[...]
Do you have a reference for this proof ?

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.
Number Nine
#27
Jan3-13, 11:00 AM
P: 772
Quote Quote by dextercioby View Post
Do you have a reference for this proof ?

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.
Identify each subset of N with an infinite binary string, where the n'th digit is a 1 if n is in the subset, and 0 otherwise. This is easily shown to be a bijection between P(N) and the set of all infinite binary strings. Cantor's diagonalization argument shows that the set of all such strings is uncountable, therefore P(N) is uncountable.

The union of countably many countable sets is countable, but that's no guarantee that the set of all such sets is countable.
micromass
#28
Jan3-13, 11:15 AM
Mentor
micromass's Avatar
P: 18,229
Quote Quote by dextercioby View Post
Do you have a reference for this proof ?

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.
First of all, what do you mean with a "proper" subset in this case?? Do you mean subsets of [itex]\mathbb{N}[/itex] that are not singletons?? In that case, there are uncountably many proper subsets of [itex]\mathbb{N}[/itex].

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.
1MileCrash
#29
Jan3-13, 11:29 AM
1MileCrash's Avatar
P: 1,292
Quote Quote by micromass View Post
First of all, what do you mean with a "proper" subset in this case?? Do you mean subsets of [itex]\mathbb{N}[/itex] that are not singletons??

From both his context and the standard definition, he is talking about any subset of N that is not N itself.
1MileCrash
#30
Jan3-13, 11:32 AM
1MileCrash's Avatar
P: 1,292
Quote Quote by dextercioby View Post
Do you have a reference for this proof ?

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.
Your proof fails in that, you are right that any proper subset of N is countable, but that is a nonissue because we are not concerned with the number of elements of the subsets, we are concerned with the number of subsets.

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.
dextercioby
#31
Jan3-13, 03:05 PM
Sci Advisor
HW Helper
P: 11,915
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