Who is right here? Are the amount of numbers between both 0 to 1 and 0 to 2 the same?

1MileCrash

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.

Number Nine

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

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

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.

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.

No this is false, they all have strictly larger cardinality as [itex]\mathbb{N}[/itex] as long as n>0.

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.

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.

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.

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)

You need to study set theory for this. A very good book is "Introduction to Set theory" by Hrbacek and Jech.

1MileCrash

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

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

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

No you are right. I was only thinking about power sets and forgetting the supremum operation.

dextercioby

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

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

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

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

1MileCrash

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

I thank you all for your kind replies.