# Cardinality of sets of subsets of $\mathbb{N}$

If we dont assume CH, is there a procedure to construct or define a set of subsets of $\mathbb{N}$ such that we cannot prove it to be of cardinality $\aleph_0$ or $\aleph_1$?

Or if we assume not CH, how to find a set of subsets of $\mathbb{N}$ with cardinality $\aleph_1$?

-
It may depend on what you mean by "construct". If we assume $V=L$ (Axiom of constructibility), then GCH holds; that suggests to me that the things you can explicitly construct are likely to be probably countable, or of cardinality $\mathfrak{c}$. – Arturo Magidin Jul 1 '11 at 4:07
if $2^{\mathbb N}$ qualifies as a construction, then without CH you cannot prove it to be of cardinality $\aleph_0$ or $\aleph_1$. – Levon Haykazyan Jul 1 '11 at 9:31
@Levon: You can never prove that $2^\mathbb N=\aleph_0$ within the set theory of $ZF$. – Asaf Karagila Jul 1 '11 at 10:01
@Asaf, that doesn't contradict my statement. – Levon Haykazyan Jul 1 '11 at 10:16
@Levon: No it does not, but your statement is somewhat deceiving that perhaps somehow $2^\mathbb N$ might be countable. You cannot prove whether or not it is of cardinality $\aleph_1$, but you can prove it is bigger than $\aleph_0$. – Asaf Karagila Jul 1 '11 at 10:19

## 2 Answers

(Edit: I edited the answer to improve readability; Edit II: Added an $\aleph_1$ collection of reals)

We need to approach the question first by addressing what does that mean to "find a set of subsets". If the answer is "define explicitly" then this requires us to limit ourselves to $L$, that is Godel's universe of constructible sets. In $L$ we have that $CH$ holds and therefore there is a definable bijection between $2^{\aleph_0}$ and $\aleph_1$.

However, this may not always be the case, in particular it might be that $\aleph_1$ in $L$ is not even close to the "real" $\aleph_1$ (i.e. different models see the same ordinals as different cardinals. Yes it is very confusing at start). In this case it might be that the axiom of choice does not hold, or even worse $\aleph_1$ and $2^{\aleph_0}$ are incomparable (that is there is no set of reals of size $\aleph_1$).

The "correct" answer is that we define, or construct, objects using tools which are not really constructible, that is we give an outline of a mathematical object and prove its existence using machinery such as transfinite induction or the axiom of choice (often both). This means that we don't actually describe the set, but just use the fact it is there.

Recall that $|A|\le|B|$ if there is an injective function from $A$ into $B$. This translates as: $|A|\le|B|$ if and only if there exists some $B'\subseteq B$ such that $|A|=|B'|$ (i.e. there is a bijection between $A$ and $B'$).

Now suppose that $2^{\aleph_0}=\aleph_{12,401}$. Since $\aleph_1<\aleph_{12,401}=2^{\aleph_0}$ take a bijection between $\aleph_{12,401}$ and $2^{\aleph_0}$ and limit yourself to the first $\aleph_1$ elements in the domain. The result is a set of subsets whose cardinality is $\aleph_1$.

Furthermore, the indices don't matter in the above example, nor even the fact we assumed $2^{\aleph_0}$ is an $\aleph$-number at all. All that mattered is that $\aleph_1<2^{\aleph_0}$ in the above example, we could have used any other cardinality - as long as it is less (or equal) to this of the continuum.

If the axiom of choice does not hold there might be a set of real numbers (i.e. subsets of $\mathbb N$) which is not of any $\aleph$ cardinality at all, that is - they cannot be well ordered. From this follows that $2^{\aleph_0}$ is definitely not $\aleph_1$ or any other $\aleph$ number. (for more information read my answer here)

Furthermore, if we assume some mildly stronger axioms we can construct a model in which there are absolutely no $\aleph_1$ sets of reals. That is, sets of real numbers can be well ordered if and only if they are countable.

A more specific $\aleph_1$ set can be found in descriptive set theory. It is consistent (as remarked by user92843 below his answer) to have a co-analytic set of reals that is of cardinality $\aleph_1$.

Firstly when saying consistent it means there is no new contradiction when asserting that such set exists. It might be consistent that the opposite is true (an example for such assertion is the Continuum Hypothesis).

That is we start with a model of $ZFC$ and describe a way to turn that into a model of $ZFC$ with the wanted set of real numbers. These proofs usually go through forcing and get somewhat technical.

Another reason for vagueness lies within the structure of sets in the projective hierarchy, which tend to be very complicated in comparison to Borel (or even Lebesgue) sets.

To finish I will return to the beginning of my answer. We usually cannot describe in a very nice way mathematical objects which are uncountable, and even countable objects can behave strangely. The fact is that the continuum can be described in a nice way as the cardinality of the real line is somewhat surprising and nontrivial at all.

This is why mathematics is a "science of deduction", where we infer from assumptions. We assume that $\aleph_1<2^{\aleph_0}$ and from this we infer the existence of a $A\subseteq\mathbb R$ such that $|A|=\aleph_1$.

Added: How to construct an $\aleph_1$ set of real numbers within ZFC.

Take $f$ to be your favourite bijection from $\mathbb R^\mathbb N$ onto $\mathbb R$. Now fix some $\langle g_\beta\colon\omega\to\beta\mid\beta<\omega_1\rangle$ a sequence of bijections of all countable ordinals with $\mathbb N$, and $\langle h_\beta\colon\beta\to\mathbb Q\mid\beta<\omega_1\rangle$ a sequence of order embeddings of countable ordinals into the the rationals (these sequences require a fragment of choice, as such sequence might not exist without it).

For every $\beta<\omega_1$ take $r_\beta$ to be $f(h_\beta\circ g_\beta)$.

Suppose $\alpha<\beta$ then the range of $h_\beta$ is different than the range of $h_\alpha$, as the ranges are well-ordered by $<$. Therefore $\{r_\alpha\mid\alpha<\omega_1\}$ is a set of real numbers of cardinality $\aleph_1$ as wanted.

-
So... I'm guessing that whether those sets of reals that are of cardinality $\aleph_1$ are of the same cardinality as $\mathbb{R}$ is undecidable in ZF(C), then? – Arturo Magidin Jul 1 '11 at 5:13
Arturo: I'm not sure I understand the question. – Asaf Karagila Jul 1 '11 at 5:15
@Asaf: Well, we know $\aleph_1\leq 2^{\aleph_0}$ (assuming the latter is an aleph, anyway). In ZFC, it's undecidable whether $\aleph_1\lt 2^{\aleph_0}$, or $\aleph_1=2^{\aleph_0}$. If, as you write, one find a subset of $\mathbb{R}$ which is provably of cardinality $\aleph_1$, then we should not be able to establish whether this subset is bijectable to $\mathbb{R}$; otherwise, that would settle CH one way or another, which we cannot do. (I think descriptive set theory does not involve any extra axioms, but I guess my error could be there as well). – Arturo Magidin Jul 1 '11 at 5:18
@Arturo: Ah. I see. I will add a bit on that in my answer. – Asaf Karagila Jul 1 '11 at 5:21
@Arturo: Whilst searching for reference in several books and online, I ran into some old forum posts about a similar question with answers given by some names that I recognized such as Herman Rubin, Arturo Magidin, and a couple others... :-) – Asaf Karagila Jul 1 '11 at 6:39

Any Borel (in fact analytic) subset of $2^\mathbb{N}$ is either countable or contains a perfect set. In particular, if such a set is uncountable then it has the cardinality of the continuum.

EDIT: If you're interested in seeing this perfect set property propagate through all projective sets (in some sense, any reasonably definable set, including coanalytic sets and beyond) you should look into the axiom of projective determinacy.

-
My account got lost somehow so I can't comment on Asaf's answer. I'll put my comment here where nobody will see it. It is not a theorem of ZFC that there's a coanalytic set with cardinality $\aleph_1$, since this in fact would contradict PD + not CH. – user92843 Jul 1 '11 at 7:50
This explains why I could not find any references to it in the main parts of Kechris and Moschovakis. It makes sense as well. However, regardless to "not a theorem of" it still consistent with. I will add this to my answer as well. – Asaf Karagila Jul 1 '11 at 8:33
And of course when I say "not a theorem" I am implicitly assuming the consistency of some unnamed large cardinal (supercompact surely suffices). – user92843 Jul 1 '11 at 8:49
I think that measurable should be enough to ensure the determinacy of projective sets. I recall a chat about the topic of measurable cardinals and CH in relation to the projective determinacy after a set theory seminar. – Asaf Karagila Jul 1 '11 at 8:54