MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 should all be equivalent, according to the paper.

Proving that the first implies the second 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. I instead proved the following statement:

If every $\omega$-tree has an infinite chain or a Dedekind-infinite antichain, then every countable collection of non-empty finite sets has a choice function.

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, given a Dedekind-infinite antichain $A,$ 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.

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?

[Question initially posed at Math.SE.]

share|cite|improve this question
Probably a silly question, but: what is the proof that (3) implies (1)? – Noah Schweber Sep 29 '13 at 18:47
@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) – Cameron Buie Sep 29 '13 at 19:02
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.$$ – Cameron Buie Sep 29 '13 at 19:04
That's a nice proof. – Noah Schweber Sep 29 '13 at 20:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.