# Does ZF prove the existence of a "minimum size" uncountable set of reals?

Clarification prepended below. Essentially the original post follows it.

Whether or not CH is true in V, the well ordering theorem lets us prove there exists a set of reals equinumerous with the countable ordinals, i.e. of cardinality $$\aleph_1$$; well-order the reals, and then take the reals with only countably-many predecessors in that order. I am saying "reals" because it is more concise than "subsets of $$P(\mathbb{N})$$", but it is the latter that I care about. As far as I know, this doesn't affect anything significant below.

I have heard the above construction of a set of $$\aleph_1$$ reals is about as "explicit" as we know how to do, by any means. But of course "explicit" doesn't have a unique precise interpretation. So, I have tried to ask here a precise question that sheds light on that. The question should be a faithful formalization of: Without AC, can you prove there exists a set of reals that is equinumerous with the countable ordinals? Unfortunately, AC is needed to prove some things about the coincidence of equinumerosity and cardinal numbers (see the linked-to stack exchange questions), so we have to be careful about how we formalize the question. I wasn't careful enough in my first go. Here is attempt 2.

Out of an abundance of caution, I will switch to asking about $$P(\mathbb{N})$$. Let $$X be the relation: "There is an injection from X to Y and no injection from Y to X." Let A be a sentence in the language of set theory that expresses: There exists $$X \subseteq P(\mathbb{N})$$ such that $$\mathbb{N} < X$$ and there is no $$Y \subseteq P(\mathbb{N})$$ such that $$\mathbb{N} < Y < X$$.

Then we have a 2-part question:

• Q1: Does ZF prove A?
• Q2: If ZF does not prove A, adding what axiom (as weak as possible) suffices? Ideally, this would be a well-known sentence B such that ZF $$\vdash A \iff B$$, but any $$B$$ weaker than $$AC$$ is helpful.

Original post

I'm attempting to ask roughly if ZF proves the existence of a subset of $$\mathbb{R}$$ of size $$\aleph_1$$, while avoiding the language of cardinality in light of complications discussed here: There's non-Aleph transfinite cardinals without the axiom of choice? and Well-orderings of $\mathbb R$ without Choice and Defining cardinality in the absence of choice.

My understanding is that ZF does prove such an X exists if X is not required to be a subset of $$\mathbb{R}$$ (there exists an uncountable set X all of whose uncountable subsets have bijections with X). I'm assuming that follows in ZF from https://proofwiki.org/wiki/Existence_of_Minimal_Uncountable_Well-Ordered_Set#Proof_Without_Using_Choice, but correct me if I'm wrong.

I've made a couple easy observations. Let A be a sentence in the language of set theory that's clearly equivalent to the question in the title, minus the informal part: there exists an uncountable set of reals X all of whose uncountable subsets have bijections with X.

1. ZF $$\vdash$$ A follows from ZF + $$\neg$$AC + $$\neg$$CH $$\vdash$$ A, since AC and CH both separately suffice to prove A. ZF + AC $$\vdash$$ A using the well-ordering theorem; the reals having only countably-many predecessors in a well-ordering of $$\mathbb{R}$$ works for X. ZF + CH $$\vdash$$ A since CH implies $$\mathbb{R}$$ works for X.

2. A seems to be equivalent in ZF to "$$P(\mathbb{R})$$ with the partial order ($$X < Y$$ iff $$X \subset Y$$ and there's no injection from Y to X) has no infinite descending chain." I'm not entirely confident in this since ZF not proving the Partition Principle gives me doubts about my ability to sketch a proof from ZF without accidentally using an independent axiom.

If the answer to ZF $$\vdash$$ A is no, is there a well-known axiom, weaker than AC, that together with ZF suffices to prove A? I had a look at https://en.wikipedia.org/wiki/Axiom_of_choice#Weaker_forms but didn't find one that obviously suffices.

• Please, use MathJax to type the math in your questions. Some symbols of your question are not rendering properly. Commented Aug 12, 2023 at 17:36

There are a lot of small misconceptions here, so let me address them one by one, while explaining why the answer is very much "no, it does not prove that".

1. $$\sf ZF$$ is consistent with "There exists a Dedekind-finite set of reals", e.g. in Cohen's first model, in which case we have a subset of the reals which is not countable, not comparable with $$\aleph_1$$, and when we remove a point from it, it shrinks in cardinality.

2. $$\sf ZF$$ is also consistent with "There exists an $$\aleph_1$$-amorphous set of reals", where $$\aleph_1$$-amorphous means that every subset is countable or co-countable, and we also implicitly mean that every infinite subset of our set is Dedekind-infinite, to avoid trivial constructions as above. The interesting thing about $$\aleph_1$$-amorphous sets is that they are uncountable, but every subset is just a countable set away from the whole thing, and since adding a countable set to a Dedekind-infinite set will not change its cardinality, an $$\aleph_1$$-amorphous set is in fact minimal, nevertheless, it is incomparable with $$\omega_1$$, so we get that it is consistent to have multiple minimal uncountable cardinals below the continuum (in fact, we can easily arrange to have a large number of these simultaneously).

3. $$\sf ZF$$ is also consistent with "There is no set of reals of size $$\aleph_1$$", which we usually prove through the Perfect Set Property, which means "every uncountable set of reals contains a perfect set", which also implies that every uncountable set of reals has size continuum, which is what you're asking about. So in fact you can get a sense in which the Continuum Hypothesis holds, and indeed the continuum itself is the minimum uncountable cardinals below the continuum, but there is no set of reals of size $$\aleph_1$$ to begin with, therefore equating "minimum" or even "minimal" size with "size $$\aleph_1$$" is not provable in $$\sf ZF$$.

4. $$\sf ZF$$ is also consistent with "There is a descending sequence of cardinals below the continuum, and every uncountable set contains a subset of size $$\aleph_1$$". This means that equating "there is a minimum uncountable cardinal" with the cardinals below the continuum being well-founded is not provable in $$\sf ZF$$ either.

• +1. Do you know whether ZF proves "there is a minimal uncountable cardinal $\leq\mathfrak{c}$"? Commented Aug 13, 2023 at 19:58
• Isn't that answered by (1)? Commented Aug 14, 2023 at 1:02
• No, I wonder whether there is a model of ZF in which every uncountable caridnal $\leq\mathfrak{c}$ has another uncountable cardinal strictly below it. So for example there is no set of reals of size $\aleph_1$, not every set of reals has the PSP, ... Commented Aug 14, 2023 at 7:05
• Ohhh, I see what you mean. If you take a Cohen model extension of the Solovay model, I believe you'll get exactly that. Commented Aug 14, 2023 at 7:36
• No. I don't think this was ever discussed or done, or perhaps even thought about before this morning. If you want to get into the details, drop me an email. Commented Aug 14, 2023 at 14:30