# Proving equivalence of a tree-based version of Countable Choice for families of finite sets.

In this paper by Good and Tree, the following result is mentioned without proof as part of Proposition 6.5:

Each of the following statements imply those beneath it.

• The countable union of finite sets is countable.

• Every $\omega$-tree has an infinite chain or an infinite antichain.

• Every countable collection of [non-empty] finite sets has a choice function.

I know that the first and last statements are equivalent, so that these statements are ostensibly all equivalent. I'm stymied on proving the second implication, though.

I began by taking $\{X_n:n<\omega\}$ to be a countably-infinite collection of finite non-empty sets, putting $X=\bigcup_{n<\omega}X_n,$ and letting $$T=\left\{f\in{}^{<\omega}X:\forall n\in\operatorname{dom}(f)\:f(n)\in X_n\right\},$$ where ${}^{<\omega}X$ is the set of all functions $k\to X$ with $k<\omega$. It is readily shown that $\langle T,\subsetneq\rangle$ is an $\omega$-tree. Now, if the tree has an infinite chain $C,$ then $$B=\bigcup_{f\in C}\{g\in T:g\subsetneq f\}$$ is a branch of length $\omega,$ and $f=\bigcup B$ is readily the desired choice function. On the other hand, if the tree has no infinite chain, then it has an infinite antichain, say $A.$ If $A$ happens to be Dedekind-infinite, then there is a countably-infinite antichain $A'\subseteq A,$ and without loss of generality, we may assume that $A'$ has at most one node on each level. Indexing the elements of $A'$ in order of increasing level by $f_n,$ we define $g(X_k)=f_0(k)$ for $k\in\operatorname{dom}(f_0)$ and $g(X_k)=f_{n+1}(k)$ where $k\in\operatorname{dom}(f_{n+1})\setminus\operatorname{dom}(f_n).$ Then $g$ is the desired choice function, and we're done.

If $A$ is infinite and Dedekind-finite, then...what in the world can be done? We need another (even stronger!) Choice principle to conclude that this is impossible, thereby finishing my proof.

Any hints as to how I can proceed?

Added: To see that the first statement implies the second, suppose we are given an $\omega$-tree $T.$ We know $T$ is countably-infinite since each of its countably-infinitely-many non-empty levels is finite. Let $f:\omega\to T$ a bijection. Supposing that $T$ has no infinite antichain, let $A$ be the set of all nodes of $T$ without successor. Since this is readily an antichain, then it is finite, so, put $$m=\max\bigl(\{0\}\cup\{k<\omega:A\cap T_k\ne\emptyset\}\bigr).$$ Let $c_0\in T_{m+1}.$ Given $c_n$ with height greater than $m$, we have by definition of $A$ and $m$ that $c_n$ has a successor, and letting $$c_{n+1}=f\bigl(\min\{k<\omega:c_n<f(k)\}\bigr),$$ the height of $c_{n+1}$ is greater than that of $c_n$, so also greater than $m$. In this way, we recursively define a strictly increasing sequence of points of $T$, so we have an infinite chain, as desired.

To see that the third statement implies the first, suppose that $\mathcal{A}$ is a countable set of finite sets. For each $A\in\mathcal A,$ we have that $A$ is well-orderable, and in particular can be put into bijection with a unique finite ordinal--namely $|A|.$ There are only finitely-many functions $A\to|A|,$ at least one of which is a bijection, and so the set $B_A$ of bijections $A\to|A|$ is a non-empty finite set for each $A\in\mathcal A.$ Since $\mathcal A$ is countable, then we can therefore use a choice function on $\{B_A:A\in\mathcal A\}$ to choose a bijection $g_A:A\to|A|$ for each $A\in\mathcal A.$ Using these bijections, we can readily show that $$\left|\bigcup\mathcal A\right|\le\sum_{A\in\mathcal A}|A|.$$ Then, since $\mathcal A$ is well-orderable and each $|A|$ is a finite cardinal, then $$\sum_{A\in\mathcal A}|A|\le\max\left\{|\mathcal A|,\sup_{A\in\mathcal A}|A|\right\}\le\aleph_0,$$ whence $\bigcup\mathcal A$ is countable, as desired.

If "Dedekind-finite = finite" holds, then showing the second statement implies the third is simple, but according to the paper, the implication is supposed to hold in $\mathsf{ZF}.$ It's possible that this was simply an error on the authors' part (like leaving off the "non-empty" from the third statement), and that it should specify Dedekind-infinite antichains.

If it is correct, though, then my approach quite simply won't work, since given an arbitrary infinite antichain, it need not have a countably-infinite subset. Certainly any such antichain will be a union of a countably-infinite collection of non-empty finite sets, but it's consistent with $\mathsf{ZF}$ that a countably-infinite union of pairs may be Dedekind-finite.

My question is this: Is it known whether the second statement (as originally written) is equivalent to or strictly weaker than the other two in $\mathsf{ZF}$? If it is equivalent, then can you direct me to a source in which it is proved, or outline an alternate proof technique that does the trick?

[Cross-posted to Math.Overflow.]

• In one Guinness and ten minutes I will post an answer. I hope. ;) – Asaf Karagila Sep 18 '13 at 21:16
• (I had to stop for a hot dog. The Viennese fast food stands are divine... So it took a few minutes longer!) – Asaf Karagila Sep 18 '13 at 22:22
• Ha! I was thinking: "My, that must be a big Guinness!" – Cameron Buie Sep 18 '13 at 22:24
• Well, it was the third Guinness, with the addition of two whisky in between. So it was longer than the first Guinness... – Asaf Karagila Sep 18 '13 at 22:25
• @dfeuer: No, I never did. Guess I should just bite the bullet and hit them up via snail mail, since I wasn't able to find any other means of contacting them. – Cameron Buie Jan 17 '14 at 19:39

Every $\omega$-tree has an infinite chain.
This clearly implies the second of G & T's statement above, and I suspect that it is what was intended by G & T, in the first place. Most notably, according to this site, H & R's text cites that Form 10 is stronger than Form 216, but that it was not known to be strictly stronger. This leads me to suspect (even more strongly) an error on G & T's part. Obviously, if it holds in $\mathsf{ZF}$ that every $\omega$-tree with an infinite antichain must have an infinite chain, then it isn't strictly stronger, but I'm unable to prove this or find any information confirming/denying this, so I suspect that it is an open question.
One thing I was able to find is that Keremidis published a proof (in Mathematica Japonica, Vol. 51, No. 2, pp. 175-178) that Form 9 from H & R (Every Dedekind-finite set is finite.), which is strictly stronger than Forms 10 and 216 in $\mathsf{ZF}$, is equivalent to the following statement:
This readily implies the second of the statements from G & T, but cannot follow from it unless $\mathsf{ZF}$ is inconsistent.