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

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.

• @LSpice No. This works with boots, but not with socks. See also the boots-and-socks metaphor of Russell about the Axiom of Choice. Feb 8, 2022 at 20:48
• I guess you are right …. Feb 8, 2022 at 20:52
• @LSpice The existence of left/right socks seems to be a bit of a personal opinion, and perhaps in a few cases a very specific design decision of certain brands. For, say, generic tube socks I think it's pretty clear that there is no left/right distinction, but I've known people who have thought otherwise, at least for a period of time. It's interesting to wonder where this comes from. Perhaps just that left vs. right shoe being a thing makes their minds automatically presume there must be a left vs. right sock, and just sticks with it. But that's rather off topic. Feb 9, 2022 at 9:19
• @zibadawatimmy Perhaps LSpice wears toe socks. Feb 9, 2022 at 15:11
• I appreciate the extended effort in the comments to save me the embarrassment of having forgotten how socks work. Feb 9, 2022 at 18:18

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.

• Thank you very much!!! I will try to read and understand the paper. Feb 8, 2022 at 21:12
• Russel, actually writes of indistinguishable boots not socks, according to Herrlich. Feb 9, 2022 at 13:53
• @Logic Quote from Introduction to Mathematical Philosophy: "Among boots we can distinguish right and left, and therefore we can make a selection of one out of each pair, namely, we can choose all the right boots or all the left boots; but with socks no such principle of selection suggests itself." Maybe you meant to write "distinguishable boots not shoes"? Feb 9, 2022 at 15:16
• @TimothyChow I meant, what I wrote. Apparently the book you mention was written in 1920, what I wrote was apparently said by Russel in 1907, see the background section of the paper Wojowu mentions. Herrlich also mentions this in their book on the axiom of choice. Feb 9, 2022 at 15:34
• @Logic Ah, very interesting! So Russell didn't come up with the socks until later. It seems that Herrlich and Tachtsis were unaware of the 1920 book, since they attribute the socks to "mathematical folklore." Feb 9, 2022 at 15:39

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.

• If we are digging into the history, I remember reading/hearing somewhere that Mostowski was trying to understand Fraenkel's proofs, and kept sending him queries and pointed mistakes, and eventually just came up with the whole "finite support" idea to get around the many issues. Although, I can't quite remember where I read/heard that. Feb 11, 2022 at 20:31
• @AsafKaragila That's interesting to hear, especially because Fraenkel is your academic great-grandfather. Feb 11, 2022 at 21:09
• Indeed he is. But if I learned anything from my academic father and grandfather, it is to hold the mathematics dearer than the people who developed it. (Although also to be respectful of the people, of course.) :-) Feb 11, 2022 at 21:12
• Note that the disjointness condition is unnecessary. Feb 12, 2022 at 12:41
• @Logic Yes indeed, I added a postcript to that effect. Feb 13, 2022 at 16:29