Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 135 / 1

Work in ZF with the law of excluded middle, without the axiom of choice. The paper's terminology is an infinite Dedekind-finite set. The useful common principle is countable union of explicitly ordered finite lists without choice: given an actual sequence of finite lists, enumerate their entries by list number and position using a Cantor pairing function. If the union of entries is infinite, repeatedly take the entry with the least code not already selected. This produces an injection from $\mathbb{N}$ without choosing any enumerations of unordered sets.

Consequently, if a family of objects has an explicitly ordered finite list of labels for each object, and only finitely many objects can be made from any given finite pool of labels, then a countably infinite list of distinct objects forces a countably infinite subset of the label set. For a Dedekind-finite label set this is impossible. If the label set embeds into the object family as well, infinitude is preserved. ThusThe distinction between ordered lists supplied by the data and arbitrary finite subsets is essential: a blanket countable-union theorem for unordered finite sets would introduce a choice principle.

Let $\mathrm{Inj}(<\omega ,X)$ denote the finite repetition-free sequences, including the empty sequence. The map $x\mapsto (x)$ is injective, so this set is infinite when $X$ is infinite. Suppose, for a contradiction, that it contains a countably infinite subset. Fix its given injective enumeration $s_0,s_1,\dots$; this is part of the supposition, not a choice from a family of sets.

Enumerate all pairs $(n,j)$ with $j<\mathrm{length}(s_n)$ by their natural-number pairing codes, recording the corresponding entries $s_n(j)$. If the union of entries were infinite, recursively selecting the first new entry would give an injection $\mathbb{N}\to X$, contradicting Dedekind-finiteness. Therefore the union is a finite set $F$, say of size $m$. A repetition-free sequence over $F$ has length at most $m$, and there are exactlysuch sequences, with the empty product equal to one. All $s_n$ would belong to this finite set, contradicting their distinctness. Finite counting and the least-code construction use no axiom of choice. This proves finite repetition-free sequences preserve Dedekind-finiteness and the required infinitude:

Write $\mathcal{T}(D)$ for the recursively repetition-free labelled trees. Each rooted tree is finite because the inductive definition forms it from an already constructed finite list of finite child rooted trees. Its label list is obtained by visiting the root first, then each child subtree in its prescribed order, using a depth-first traversal of a tree. This list can have repetitions. In particular, different branches may use the same label; the children are required to be distinct rooted trees, not to have distinct root labels.

For any finite label pool $F$, prove by mathematical induction on $|F|$ that $\mathcal{T}(F)$ is finite. For $F=\varnothing$ it is empty. For each root $d\in F$, the children form a finite repetition-free sequence from $\mathcal{T}(F\setminus \{d\})$, which is finite by mathematical induction. There are therefore finitely many child lists for that root, and the finite union over $d\in F$ is finite. More explicitly, if $t_m$ is the number of rooted trees on a pool of $m$ labels, thenThere is no countable choice in this finite mathematical induction.

Now suppose $T_0,T_1,\dots$ were an injective enumeration of a countably infinite subset of $\mathcal{T}(D)$. Their canonical traversal lists give an explicit enumeration of all labels used. If infinitely many different labels occur, the least-first-occurrence procedure gives a countably infinite subset of $D$, a contradiction. Otherwise all labels belong to one finite set $F$. Every $T_n$ then belongs to $\mathcal{T}(F)$: recursively its root lies in $F$ and its child rooted trees use only $F$ with that root removed. But $\mathcal{T}(F)$ is finite by the preceding mathematical induction, again a contradiction. Finally $d\mapsto$ the single-vertex rooted tree labelled $d$ is injective, so $\mathcal{T}(D)$ is infinite. Hence recursively repetition-free labelled trees preserve Dedekind-finiteness: