6
$\begingroup$

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$?

  • 3
    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}$.2011-07-01
  • 2
    if $2^{\mathbb N}$ qualifies as a construction, then without CH you cannot prove it to be of cardinality $\aleph_0$ or $\aleph_1$.2011-07-01
  • 0
    @Levon: You can *never* prove that $2^\mathbb N=\aleph_0$ within the set theory of $ZF$.2011-07-01
  • 1
    @Asaf, that doesn't contradict my statement.2011-07-01
  • 0
    @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$.2011-07-01
  • 0
    @Asaf: I took as granted that the questioner and everybody who might be interested in this question will know that. I chose the somewhat confusing formulation, to match that of the question.2011-07-01
  • 0
    @Levon: It is reasonable to assume that, still the phrasing was unsuccessful.2011-07-01
  • 0
    @Asaf: thank you for you opinion. Still, I like my formulation and will not change it. PS: I find this discussion rather pointless, so I'll not comment on this any more.2011-07-01

2 Answers 2

10

(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.

  • 0
    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?2011-07-01
  • 0
    Arturo: I'm not sure I understand the question.2011-07-01
  • 0
    @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).2011-07-01
  • 0
    @Arturo: Ah. I see. I will add a bit on that in my answer.2011-07-01
  • 0
    @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... :-)2011-07-01
  • 0
    Based on user92843's comment below, do I understand that in ZFC one cannot prove that the coanalytic sets you had originally refered to *are* of cardinality exactly $\aleph_1$ (I confess that this is what I would expect, that in "bald" ZFC with no further assumption, one cannot "construct" a subset of $\mathbb{R}$ that is provably of cardinality exactly $\aleph_1$).2011-07-01
  • 0
    @Arturo: you understand correctly. As for the "bald" ZFC construction, I actually have an idea involving Aronszajn trees. It will take me some little while, but I hope to come back with some nice result soon enough.2011-07-01
  • 0
    @Arturo: Took me some time, but there it is. A bald ZFC construction. :-)2011-07-01
  • 0
    Right, but it's not quite "explicit"/"constructive", because of the "fragment of choice" required. What surprised me about your original remark was that you said it occurred in "descriptive set theory", which I think of as pretty "explicit"/"constructive."2011-07-01
  • 0
    @Arturo: The only ways we can "explicitly describe" is by some closed form formula, which will almost certainly produce Borel sets, or at most analytic. When saying $\Pi^1_1$ set it is still pretty far from being "constructive". This does not involve any non-constructive aside of the sequences of functions, which are not *that* strong of principles of choice (at most they give that $\aleph_1$ is a regular cardinal :-))2011-07-01
5

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.

  • 2
    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.2011-07-01
  • 0
    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.2011-07-01
  • 0
    And of course when I say "not a theorem" I am implicitly assuming the consistency of some unnamed large cardinal (supercompact surely suffices).2011-07-01
  • 0
    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.2011-07-01