What is an example of model of ZF with a countable family of pairs whose union is uncountable?

Question

I was reading the book "Howard and Rubin, “Consequences of the Axiom of Choice”.

For example, why do not exists sets that are neither countable nor uncountable?

It is interesting to point out that there are some statements on countable and uncountable sets that depend on the presence of weak choice principles (which are weaker versions of the Axiom of Choice).

For instance, there are models of ZF on which the statements “A countable union of countable sets is countable”, or even “A countable union of finite sets is countable”, do not hold. In fact, there is a model of ZF with a countable family of pairs whose union is uncountable.

One could intuitively think that this union of a countable family of pairs, which lives in a model where the Axiom of Choice is not available and because of that enjoys its existence as an awkward uncountable set, would become a countable set as soon as the Axiom of Choice would enter the room, but this is just a tale we tell to our students and has no formal meaning.

Answer 1

I'm quite fond of using permutation models (https://en.wikipedia.org/wiki/Permutation_model) for these sorts of constructions, since they're a relatively simple way of constructing models of ZF with Ur-elements (not quite the model of ZF you're looking for, but you can enhance these arguments using forcing to produce models of ZF)

In this case, construct a model of ZF with Ur-elements $a_{i,j}$ where $i \in {0,1}$ and $j \in \mathbb{N}$. Let $G$ be the group of permutations of the $a_{i,j}$ such that for each $j$ either $a_{0,j}$ and $a_{1,j}$ stay fixed or are switched.

Define a set $x$ as nearly-fixed by $G$ if there's some finite set of indices $J$ such that any element of $G$ that fixes the $j$th pair for every $j \in J$, also fixes $x$.

The sets that are hereditarily nearly-fixed by $G$ (i.e. they are nearly-fixed by $G$ and their elements are hereditarily nearly-fixed by $G$) form a model of ZF with ur-elements. In this model, $\bigg\{\{a_{0,j},a_{1,j}\}\bigg\}_{j \in \omega}$

• Exists
• Is a countable union of pairs
• Any bijection between the union of this set with $\omega$ is going to necessarily not be nearly-fixed by $G$, so won't exist in the model.

It's been a while since I've worked with permutation models, so please correct me if I've made a mistake somewhere!

Answer 2

Let me answer the easy part first. A set is countable if there is an injection into $\omega$, or it is uncountable if there is none. So a set must be one of the two, since one of the two must be true (in any fixed universe of $\sf ZF$).

Some define "uncountable" as "strictly larger than $\omega$" and it can be beneficial in some contexts, but that is the exception to the rule. But, if you do insist to define it this way, then an infinite Dedekind-finite set is neither countable nor uncountable. Nevertheless, if you have an infinite Dedekind-finite set $A$, then $A\cup\omega$ is an uncountable set, under this revised definition, and if $A$ was a countable union of pairs, then $A\cup\omega$ is also a countable union of pairs by simply considering $\omega$ as the union of the pairs $P_n=\{2n,2n+1\}$.

---

The canonical example is Cohen's second model, which comes from his seminal work on forcing. The idea is quite similar to Fraenkel's second model, which is presented in the other answer as a permutation model of ZF+Urelements.

Cohen's construction is to add $\omega\times2\times\omega$ Cohen reals, call them $x_{n,i,m}$ for $(n,i,m)\in\omega\times2\times\omega$; then consider the blocks $a_{n,i}=\{x_{n,i,m}\mid m<\omega\}$ as your urelements, and set $P_n=\{a_{n,0},a_{n,1}\}$ and $P=\{a_{n,i}\mid (n,i)\in\omega\times2\}$.

Using automorphisms of the forcing we can define an intermediate model where each $a_{n,i}$ is a Dedekind-finite set, and there is no uniform way to enumerate the $P_n$s. That is, we cannot know, internally to the model, which element of $P_n$ is $a_{n,0}$ and which on is $a_{n,1}$. We can do that without changing the order of the $P_n$s, so that the sequence $f(n)=P_n$ remains in this intermediate model.

That implies, in particular, that the set $P$, which is the union of the pairs, is a countable union of pairs which is itself uncountable. If it were countable, we could have enumerated it, and we could have chosen the least member of each $P_n$ to be $a_{n,0}$.

You can find the full details in Jech's "The Axiom of Choice" book on Chapter 5. The idea is to consider permutations of $\omega\times2\times\omega$ which respect the partitions above, i.e. for $\pi(n,i,m)=(n',i',m')$ implies that $n=n'$ and that for all $m$ the $i'$ is the same. Applying these to the forcing in the standard way will permute the names of the reals in a way that preserves the canonical names for $a_{n,i}$, $P_n$, and the sequence $f(n)=P_n$.

Now consider taking into your model only those sets which have a name that is stable under almost all of these automorphisms, namely, if we fix a finite set of indices, we will have guaranteed that the name is stable; and moreover, require that this property holds hereditarily (we do not require that the same finite set fixes a name and the names appearing inside it).

It is not hard to check now that each $x_{n,i,m}$ will satisfy the above property (with $\{(n,i,m)\}$ being the wanted finite set), and that each $a_{n,i}$ will satisfy that as well (with $\{(n,i,m)\}$, for any $m$, witnessing that, since once $\pi(n,i,m)=(n,i,m)$ it must be that any other $k<\omega$ satisfies that $\pi(n,i,k)=(n,i,k')$ for some $k'$), and therefore also each $P_n$ and the sequence of pairs must be preserved by all automorphisms.

On the other hand, if we could uniformly enumerate $P$, the union, there would be a finite witness to that, say $E\subseteq\omega\times2\times\omega$, so there is some $(n,i,m)$ such that $n$ is not mentioned in any tuple in $E$, and then we can find a permutation that "flips" the members of that $P_n$, but is supposed to preserve the enumeration. But that would be impossible, since then $f(k)=a_{n,0}$ and also $f(k)=a_{n,1}$.

(Again, the idea is very much the same as in the case with Urelements, since Cohen took his first two models to mimic Fraenkel's original two models with Urelements.)

---

Let me finish by addressing what Noah Schweber mentions in the comments. Using forcing we can move from one model of set theory to another, and indeed, any set could be made countable in some forcing extension of the universe.

(Note that if we make the real numbers countable, then we simply add more real numbers in the process, so in the forcing extension "the original reals" are now countable, but the entire set of reals is not.)

To that end the notion of "uncountable" could be seen as "a tale", since everything and anything can be made countable by adding a certain function to the universe. But working within a fixed universe of set theory some sets are countable and others are not. Some axioms are true, and others are not. Some families of sets may admit a choice function, and others might not.

The point is that we evaluate definitions within a given model. (We sometimes do quantify over generic extensions, but that is within the depth of set theoretic technical axioms, so let's not go there right now.)

What you could argue about is whether or not we can add a choice function, or a well-ordering of a certain type with or without collapsing cardinals. In this sense, a countable union of pairs is "almost countable", since we cannot well-order the union of these pairs in an uncountable order type $\alpha$, adding such a bijection will simply make $\alpha$ countable as well.

Nevertheless, we can have a Dedekind-finite set which is the union of $\aleph_1$ pairs, and no infinitely many of them admit a choice function. So there is a bit more to that than just what meets the eye, especially when we move to more generalised settings of "counterexamples to the axiom of choice".