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

Question

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.

Answer 1

Just to add to Asaf's nice answer:

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.

Answer 2

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$.