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.

  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Oct 5 '18 at 4:37
  • 3
    $\begingroup$ @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. $\endgroup$ – Asaf Karagila Oct 5 '18 at 5:01

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.

  • $\begingroup$ 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. $\endgroup$ – CopyPasteIt Oct 6 '18 at 0:59
  • $\begingroup$ 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. $\endgroup$ – CopyPasteIt Oct 6 '18 at 1:09
  • 1
    $\begingroup$ @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... $\endgroup$ – 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$.

  • $\begingroup$ Is it easy to write out the details of the 'more to the point' proof? $\endgroup$ – CopyPasteIt Oct 5 '18 at 12:49
  • $\begingroup$ 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). $\endgroup$ – Asaf Karagila Oct 5 '18 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.