Yet another infinity question

Factual Questions
1

OK so I know that Aleph_0 is the cardinality of the integers and that Aleph_1 > Aleph_0 is the cardinality of the set of all (possibly infinite) sets of integers, and is also the cardinality of the reals. Further the set of all subsets of reals has cardinality Aleph_2 > Aleph_1, and that we can continue this so that Aleph_n+1 > Aleph_n is the cardinality of the number of subsets of the elements of a set with cardinality Aleph_n.

But suppose we make a restriction on the size of the subsets. I can prove for example that the set of all finite subsets of integers has cardinality Aleph_0. But what about the set of all countable subsets of real numbers? I suspect that it is also of cardinality Aleph_1, but I can’t think of a bijection to prove it. Does anyone have an easy proof for this?
Also more generally if S is a set of cardinality Aleph_n and

V = {The set of all subsets of S with cardinality at most Aleph_(n-1) }

Is there an easy proof as to what the cardinality of V is?

2

This is only true if you accept the Continuum Hypothesis.

As to your main question: Do you also include the Axiom of Choice?

3

Whether Aleph_1 is the cardinality of the reals is subject to the continuum hypothesis, which is independent of ZFC set theory.
Your are right the cardianilty of the set of all finite subsets of R is |R|.

pI’m sure your aware that |R[sup]n[/sup]| and |(x,y)| = |R| (where (x,y) is a non-empty real interval). Then it is easy to see that there exists a bijection between R[sup]n[/sup] and (n-1,n) and thus a bijection between the set of all finite subsets of the reals and the positive reals (and hence the reals).

4

Is it dependent of the AC, I didn’t think it was, but I might be wrong.

5

It shouldn’t be. Your explanations look fine to me.

6

Looking back at it I guess I am misusing the notation Aleph notation in such a way that assumes the axiom of choice. I think I really meant to be using beth numbers.

So let me rephrase my question into asking for an easy proof that given a set of S is a set of cardinality Beth_n and

V = {The set of all subsets of S with cardinality at most Beth_(n-1) }

Based on what I am reading here, it sounds like if the axiom of choice holds then the answer is that V has cardinality Beth_n=Aleph_n, but that if the axiom of choice does not hold then it is possible that the result could be somewhere between Beth_n and Beth_(n+1).

Am I getting this right?

As far as my request for an easy proof goes, I am willing to accept that any proof that requires the axiom of choice is likely to be messy.

7

That seems largely right, except you’re conflating the Axiom of Choice with the Generalized Continuum Hypothesis at points.

The main effect of the Axiom of Choice for cardinality questions is that it tells us A) the notions “X has an injection into Y” and “Y has a partial surjection onto X” are the same, clearing up an ambiguity as to what “Y is at least as large as X” should mean, and B) it also ensures us that of any two different cardinalities, one is larger than the other, which makes these questions much simpler.

[This is distinct from the Generalized Continuum Hypothesis which is that the beth numbers (where beth_n is the powerset of beth_{n - 1}) match the aleph numbers (where aleph_n is the smallest (well-orderable) cardinal larger than aleph_{n - 1}), which makes things even simpler; the GCH implies the Axiom of Choice, but not vice versa]

Now, let’s consider V = {the set of all subsets of S with size at most K}, where S itself has size 2^K, and K is infinite.

Note that V is certainly at least as large as S (since the singleton operator injects S into V).

With the axiom of choice (but without requiring the GCH), we can get the converse as well: Note that W = {the set of all subsets of S with size at most K, along with a well-order on S} is at least as large as V [since every set can be given at least one well-order]. But W = S^0 + S^1 + S^2 + … + S^K <= S^K + S^K + S^K + … + S^K [with as many terms as there are ordinals <= K] <= 2^K * S^K [since the ordinals <= K can be identified with those particular subsets of K which are downwards closed, on some fixed well-ordering of K] = 2^K * (2^K)^K = 2^(K(K + 1)) = 2^K [since any infinite K satisfies K(K + 1) = K^2 = K] = S. Thus, S is at least as large as V as well, making the two equal in size.

Actually, we don’t need the full Axiom of Choice for this to go through; we simply need to assume that K is well-orderable.

Even if K is not well-orderable, we still know that S <= V <= 2^S, trivially. However, there’s no reason I can see why V should be injectable into S. I’ll try to provide proof that this can fail (for non-well-ordered K) later.

8

Note that the more specific question in the OP (the number of countable subsets of the reals) is the case where K is countably infinite; this is trivially well-orderable, whether or not we have the Axiom of Choice in general, and so we find by the above argument that there are as many countable subsets of the reals as there are reals themselves.

9

Correction in bold

10

Thanks a lot!

I’m putting together a talk on infinity for some very bright middle schoolers, and just wanted to make sure I had an answer in my back pocket in case anyone asks. Too much discussion of the nitty-gritty of GCH vs AoC is well beyond the scope of what they are likely to understand but I after this I can safely tell them that it depends on how you formulate your axioms. I was already planning on telling them that there may or may not be cardinality between Beth_n and Beth_(n+1) depending on how you formulate you hypothesis, now I can use this as an example.

Also, of course, fighting my own ignorance is it’s own reward.

11

Further correction in bold…

12

Wait, the generalized continuum hypothesis implies choice? I would have thought that if there was a connection, that it would be the other way around, that the AoC could be used to construct a set intermediate in size between two Beths.

As an aside, are the Alephs even well-defined? Like, Aleph-1 is defined as the smallest cardinal strictly larger than Aleph-0, right? But (if the continuum hypothesis is false, of course) I could envision an infinite set of cardinals such than none of them is the smallest. Is this known to be impossible?

13

In the absence of the Axiom of Choice, one typically defines each aleph as the smallest well-orderable cardinal larger than the previous alephs. This is well-defined because well-orderable cardinals can be identified with ordinals (modulo equicardinality), which form a well-ordered sequence.

AC can’t be used to settle GCH (or even mere CH) one way or another; that ZFC + ~CH is consistent relative to ZFC follows from Cohen’s famous “forcing” argument, while the argument that ZFC + GCH is consistent relative to ZFC follows from the fact that ZF + GCH entails AC [as shown by Sierpinski] and the consistency of GCH relative to ZF [as demonstrated by Goedel using the “constructible universe”].

It may seem surprising that GCH implies AC, but think of it this way: AC is equivalent to the assertion that all sets can be well-ordered. GCH gives us immediately that a huge swath of otherwise not-necessarily-well-orderable sets can in fact be well-ordered (those in the beth series, since GCH tells us these are equal to the aleph series, which is well-orderable by definition). It’s not obvious that this will in fact allow us to well-order ALL sets, but it’s a huge start, from which the rest might not be so surprising.

14

I don’t understand… Isn’t well-ordering a property of a set, not of an individual element of a set? I couldn’t say something like “the smallest well-orderable real number larger than pi”, could I?

15

A cardinal is well-orderable if there is some way to assign a well-ordering to a set of that size.

16

I hope you mean “to some set of that size”. You’re not saying that for sets of a given size, either they are all well-orderable, or none of them are, are you?

17

One final question.

Assuming GCH holds, are there countably many Alephs or are there more?

18

Sure I am. If two sets have the same size, then there is some one-to-one correspondence (i.e., bijection) between them. Using any such correspondence, we can transfer any “structure”* on the one to corresponding structure on the other; for example, given a well-ordering on a set A and a correspondence between A and a set B, we can define a well-ordering on B by the rule “The result of comparing two elements of B is the same as that of comparing the corresponding elements of A”.

[*: For suitable notion of “structure”; specifically, “structure” which depends only on the categorical properties of the set (i.e., the various possible functions into and out of the set), and not on any information about what kinds of elements the set has (e.g., whether it’s elements are themselves sets or something else)]

19

There are as many alephs as there are transfinite ordinals, which is more than there are in any set. For given any set of alephs S, we can construct the new aleph corresponding to the number of ordinals of cardinality less than or equal to some aleph in S, which will be larger than any particular aleph in S.

[This is the ZF party line. Given some other sort of set theory, which is not based on a “limitation of size” principle like ZF, one might give some other sort of answer]

20

I actually felt kind of stupid asking, because I thought “well of course he meant the first meaning…”

Why wouldn’t showing that you could always make the one-to-one correspondence require the well-ordering theorem in the first place? It doesn’t seem obvious, otherwise.