Can a countable union of two-element sets be uncountable?

Question

I am thinking about the Axiom of Choice and I am trying to understand the Axiom with some but a little progress. Many questions are arising in my head. So, I know that there exists a model of ZF set theory in which the set of real numbers, which is provably uncountable, is a countable union of countable sets.

Question: does there exist a model of ZF set theory for which there exists a collection $A_n$, $n\in\mathbb{N}$, of pairwise disjoint two-element sets such that their union is not countable?

Some thoughts. Let $A_n$, $n\in\mathbb{N}$, be a collection of pairwise disjoint two-element sets. Then for every $n\in\mathbb{N}$ there exists a bijection $f:\{1,2\}\to A_n$. But when we want to prove that $\bigcup_{n\in\mathbb{N}}A_n$ is countable, we have to choose a countable number of bijections $f_n:\{1,2\}\to A_n$, $n\in\mathbb{N}$, at once (simultaneously). After this we plainly define the bijection $f:\mathbb{N}\to\bigcup_{n\in\mathbb{N}}A_n$ by $f(1):=f_1(1)$, $f(2):=f_1(2)$, $f(3):=f_2(1)$, $f(4):= f_2(2)$, and so on. Rigorously, we write $f(k)=f_l(1)$ if $k=2l-1$ and $f(k)=f_l(2)$ if $k=2l$. Clearly, $f$ is a bijection and we are done. But without the Axiom of Countable Choice we can not choose $f_n$, $n\in\mathbb{N}$, simultaneously and the argument does not work.

It is worth mentioning that if $A_n$ are subsets of $\mathbb{R}$, then we can choose $f_n$, $n\in\mathbb{N}$, simultaneously. Indeed, we can define $f_n(1):=\min A_n$ and $f_n(2):=\max A_n$, $n\in\mathbb{N}$, and the natural proof given above works. So if a counterexample exists, the sets $A_n$, $n\in\mathbb{N}$, have to be "abstract", say pairs of socks.

Answer 1

Yes, it is possible. This phenomenon is sometimes called Russell's socks, named after an analogy due to Russell about how one can pick out a shoe from an infinite set of pairs of shoes, but not for socks since socks in a pair are indistinguishable.

Horst Herrlich, Eleftherios Tachtsis, On the number of Russell’s socks or 2 + 2 + 2 + . . . = ? is a nice overview which proves some basic properties, including consistency of existence of Russell's socks.

Answer 2

The point of this answer is to draw attention to the easy proposition below and the historical remark that follows it. In this answer "countable" means countably infinite (the finite case is trivial since within $\mathrm{ZF}$-set theory, a simple induction on the cardinality of $F$, where $F$ is a finite set of finite sets, shows that the union of $F$ is finite).

Let $\mathrm{CUPC}$ denote the statement: "every countable disjoint union of pairs (two-element sets) is countable", and consider the weak form of the axiom of choice that is often denoted $\mathrm{C}^{\omega}_{2}$, which states: "every countable disjoint family of 2-element sets has a choice function". Note that it is precisely $\mathrm{C}^{\omega}_{2}$ that is alluded to in Russell's infinitely many pairs of socks set-up.

Proposition. Within $\mathrm{ZF}$-set theory, $\mathrm{C}^{\omega}_{2}$ is equivalent to $\mathrm{CUPC}$.

Proof. Suppose $P$ is a countable disjoint family of pairs (two-element sets), thus each $p\in P$ has two elements, and there is a bijection $f:\omega \to P$.

We will show that $P$ has a choice function iff the union $\cup_{n \in \omega} f(n)$ of members of $P$ form a countable set.

Suppose $\mathrm{C}^{\omega}_{2}$ holds. Then there is (choice) function $C:\omega \to \cup_{n \in \omega} f(n)$ such that $C(n) \in f(n)$ for each $n \in \omega$. To see that $\cup_{n \in \omega} f(n)$ is countable we simply note that the function $g:\omega \to \cup_{n \in \omega} f(n)$ is a bijection, where $g(2n) = C(n)$ and $g(2n+1) = b$, where $f(n)\setminus \{C(n)\} = \{b\}$ (i.e., $b$ is the element of $f(n)$ that is not chosen by the choice function $C$).

Now suppose $\mathrm{CUPC}$. Then there is a bijection $g:\omega \to \cup_{n \in \omega} f(n)$. This allows us to define the desired choice function $C:\omega \to \cup_{n \in \omega} f(n)$ via $C(n)=g(k)$, where $k$ is the least $m\in \omega$ such that $g(m)\in f(n)$.

Historical Remark. The independence of $\mathrm{C}^{\omega}_{2}$ from $\mathrm{ZFA}$, i.e., set theory with atoms/urelements was first established by Abraham Fraenkel in the 1920s, his technique was extended by Andrzej Mostwoski in the 1930s, in the form of what is nowadays known as Fraenkel-Mostowski permutation models (the modern expositions of this technique employ the further conceptual machinery of "filters" introduced by Ernst Specker in the 1950s). Several decades later, in the early 1960s, Paul Cohen invented the method of forcing, and was able to transplant the Fraenkel-Mostwoski independence to the $\mathrm{ZF}$-setting. In "Cohen's second model", there is a countable family $P$ of 2-element sets $p$ such that each member of $p$ is a subset $\mathbb{R}$ with the property that $P$ has no no choice function, i.e., each "Russell sock" is a collection of real numbers.

Postscript: It is well-known that the assumption of disjointness can be removed from the choice principle discussed here, and other similar situations, by the trick of replacing a family of sets $\mathcal{A}$ which might have intersecting members with the family of disjoint sets $\mathcal{A}^{*}$ that results from replacing each $A \in \mathcal{A}$ with $A \times \{A\}$, and noting that $\mathcal{A}^{*}$ has a choice function iff $\mathcal{A}$ does.