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

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: