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 either (sic) an infinite chain or an infinite antichain.

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

By "tree," it is meant "single-rooted tree" in this sense. An $\omega$-tree is a tree of height $\omega$ with all of its levels finite. An antichain is a set of mutually incomparable elements of the tree.

I know that the first and (edited) last statements are equivalent, so that these statements should all be equivalent, according to the paper.

Proving that the first implies the second (with "either" removed) is not difficult. 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.

Showing that the second statement implied the third, though, was not so straightforward, even with edits.

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.

[Related question initially posed at Math.SE.]

Edit: Upon further research--in particular, upon inspecting the numerical list of forms from Howard and Rubin's "Consequences of the Axiom of Choice"--I noticed that Howard and Rubin's text actually references Good and Tree's paper. I also see that the first statement above readily implies Form 10A from H & R, the second statement above is Form 216 from H & R, the third statement above is Form 10 from H & R, and I give proof in the comments below that the third statement implies the first, so that the first statement is again equivalent to form 10. Furthermore, I noted that form 10F from H & R is the following:

Every $\omega$-tree has an infinite chain.

This clearly implies the second of G & T's statement above (with "either" removed), 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. Does anyone know whether this is true, false, or independent of $\mathsf{ZF}$?

P.S.: 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:

Every infinite tree has a countably infinite chain or a countably infinite antichain.

This readily implies the second of the statements from G & T (if the "either" is removed), but cannot follow from it unless $\mathsf{ZF}$ is inconsistent.

  • 1
    $\begingroup$ Probably a silly question, but: what is the proof that (3) implies (1)? $\endgroup$ – Noah Schweber Sep 29 '13 at 18:47
  • 3
    $\begingroup$ @Noah: Let $\mathcal A$ be a countable set of finite sets. For each $A\in\mathcal A,$ we have that $A$ is well-orderable, so is in bijection with a unique ordinal--namely $|A|$. There are only finitely-many functions $A\to|A|,$ so the set $B_A$ of bijections $A\to|A|$ is finite and non-empty for each $A\in\mathcal A$. Then we can choose $g_A\in B_A$ for each $A\in\mathcal A$ since $\mathcal A$ is countable. We can readily show that $|\bigcup\mathcal A|\leq\sum_{A\in\mathcal A}|A|$ using these bijections. (cont'd) $\endgroup$ – Cameron Buie Sep 29 '13 at 19:02
  • 3
    $\begingroup$ Finally, since $\mathcal A$ is well-orderable and each $|A|$ a finite cardinal, then $$\sum_{A\in\mathcal A}|A|=\max\left\{|\mathcal{A}|,\sup_{A\in\mathcal A}|A|\right\}\le\aleph_0.$$ $\endgroup$ – Cameron Buie Sep 29 '13 at 19:04
  • 3
    $\begingroup$ That's a nice proof. $\endgroup$ – Noah Schweber Sep 29 '13 at 20:49
  • $\begingroup$ Would there be any harm in making this question accessible to the masses by including definitions of $\omega$-tree and antichain? $\endgroup$ – bof Sep 27 '17 at 5:39

Your Answer

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

Browse other questions tagged or ask your own question.