# The most difficult way of proving that a countable union of countable sets is countable

In ZFC I want to prove the following result:

Proposition 1: Let $$A$$ be a set and let $${(G_k)}_{k \in \mathbb N}$$ be a (countable) family of countable nonempty subsets of $$A$$. Then there exist a mapping $$f: \mathbb N \to A$$ satisfying:

$$\tag 1 \text{There exist a partition of } \mathbb N \text{ into a family of subsets } N_k , \, k \ge 0$$

$$\tag 2 f \text{ restricted to } N_k \text{ is an injective mapping onto } \,G_k, \, k \ge 0$$

We can see immediately that $$f$$ maps onto $$\bigcup G_k$$ and that $$f$$ is injective when the $$G_k$$ are mutually disjoint.

My hand-waving idea of a proof:

Using the axiom of choice, we can endow all the $$G_k$$ with a well-ordering relation. The idea is is to define, using recursion, a way of visiting each index $$k$$ for the $$G_k$$ family as many times as necessary to 'scratch off and exhaust' the elements in $$G_k$$ as they are enumerated. For instance, if $$G_k$$ is finite with $$\alpha_k$$ elements, we would 'visit' $$k$$ exactly $$\alpha_k$$ times.

Another idea:

Proposition 1 is sure looks like it is equivalent to showing that a countable union of countable sets in countable; the arguments found in this math.stackexchange question make this very plausible.

Question 1:

If proposition 1 is valid in ZFC, any ideas on how to go about proving it.

Question 2:

Assuming again that proposition 1 is true, is it equivalent in ZF (axiom of choice dropped) to the Axiom of Choice from a 'Countable Family of Countable Sets':

Axiom AOC.CFCS: If $${\displaystyle (S_{i })_{\,i \in \mathbb N}}$$ is a family of non-empty countable sets indexed by the natural numbers, then $$\;{\displaystyle \prod _{i \in \mathbb N}S_{i }\neq \emptyset }$$.

A 'yes' or 'no' would be helpful here with perhaps some idea sketch/links to help me see this.

• A famous result is that if there is a measurable cardinal then there is a model of ZF that satisfies "$\omega_1$ is a countable union of countable sets". So if you can't first prove that measurable cardinals don't exist, then well-ordering $\cup_{k\in \Bbb N}G_k$ will not suffice. What you need, I think, is to use Countable Choice to get some $(f_k)_{k\in \Bbb N}\in \prod_{k\in \Bbb N}F_k,$ where $F_k$ is the set of bijections from $G_k$ to $\Bbb N$ or to an initial segment of $\Bbb N.$.... Note that if $G_k$ is infinite then $F_k$ is uncountable. – DanielWainfleet Oct 5 '18 at 4:37
• @DanielWainfleet: What??? Measure cardinals??? There are no large cardinals involved with "$\omega_1$ is a countable union of countable sets". The statement is equiconsistent with ZF itself. – Asaf Karagila Oct 5 '18 at 5:01

You suggest that Proposition 1 might be equivalent over ZF to the axiom of choice for countable families of countable sets. Asaf has given a reference showing that it's not. I think I understand where you got confused.

The family $$(G_k)_{i\in \mathbb{N}}$$ is a countable family of countable sets, but you don't use the axiom of choice to get a choice function for this family. Instead, you use it to pick a well-ordering of each $$G_k$$. That is, letting $$W(G_k)$$ be the set of well-orderings of $$G_k$$, you need a choice function for the family $$(W(G_k))_{k\in \mathbb{N}}$$. And given a countably infinite set $$G_k$$, the set $$W(G_k)$$ is not countable.

Regarding the details of making your proof of Proposition 1 precise, here's one way to formalize it. For each $$k$$, pick an injective map $$f_k\colon G_k\to \mathbb{N}$$. Let $$\bigsqcup_{k\in \mathbb{N}} G_k = \{(k,x)\mid k\in \mathbb{N}, x\in G_k\}$$ be the disjoint union of the $$G_k$$. Then we have an injective map $$f\colon \bigsqcup_{k\in \mathbb{N}} G_k\to \mathbb{N}\times\mathbb{N}$$, by $$f(k,x) = (k,f_k(x))$$.

Now by induction you can define a map $$g\colon \mathbb{N}\to \text{ran}(f)$$ via the standard diagonal enumeration of $$\mathbb{N}\times \mathbb{N}$$, skipping any elements of $$\mathbb{N}\times\mathbb{N}$$ which aren't in $$\text{ran}(f)$$.

For any $$n\in \mathbb{N}$$, if $$g(n) = (k,x)$$, then set $$n\in N_k$$ and $$h(n) = f_k^{-1}(x)$$. The function $$h$$ and partition $$(N_k)_{k\in \mathbb{N}}$$ do what you wanted.

• Your formal solution is just what I was looking for. Your answer has the added benefit that it stops me from writing a Python program to answer my question - such a demonstration of the concept might upset pure mathematicians interested in set theory. – CopyPasteIt Oct 6 '18 at 0:59
• So proposition 1 over ZF is a 'downshift' of full AOC over ZF, but is powerful enough to care care of (i,e, prove) both AOC.CFCS and the assertion that the countable union of countable sets is countable. – CopyPasteIt Oct 6 '18 at 1:09
• @CopyPasteIt That's right, although I would say that your Proposition 1 is pretty obviously equivalent to the assertion that a countable union of countable sets is countable... – Alex Kruckman Oct 6 '18 at 1:22

To answer the second question, no. You cannot prove from countable choice for countable sets that the countable union of countable sets is countable. Felgner constructed a model where every family of well-orderable sets admits a choice function, and $$\omega_1$$ is a countable union of countable sets. In the Howard–Rubin book Consequences of The Axiom of Choice this model is referred to as $$\mathcal M20$$.

To answer the first question, yes, that is a valid idea. More to the point, partition $$\Bbb N$$ into $$N_k$$ such that $$|N_k|=|G_k|$$ for all $$k$$, choose a bijection $$f_k$$ between $$N_k$$ and $$G_k$$, and let $$f=\bigcup f_k$$.

• Is it easy to write out the details of the 'more to the point' proof? – CopyPasteIt Oct 5 '18 at 12:49
• Well. Yes. The only details missing are explaining how to partition $\Bbb N$ (which is a bit of a hassle if you want to do it directly, otherwise you can rely on some other theorems), and that the union of bijections whose domains are disjoint is a well-defined function which is surjective on the union of the ranges (not necessarily injective, of course, unless the ranges are also disjoint). – Asaf Karagila Oct 5 '18 at 13:03