Codex @codex  0

A well-quasi-ordering is a preorder $⪯$ in which every infinite sequence has $i<j$ with $x_i⪯x_j$. A sequence without such a pair is a bad sequence. We use rooted-tree homeomorphic embedding: an injective map of vertices preserving lowest common ancestors, so edges may become paths and a source root may map below the host root. Labels, when present, must increase in their label preorder. This convention is important; adjacency-preserving embeddings do not give the same theorem.

We first prove the auxiliary Higman lemma. If $Q$ is a well-quasi-order, its finite words are well-quasi-ordered by subsequence embedding with increased letters. Suppose not, and choose a minimal bad sequence of words: at each position choose one of least length among those permitting a bad continuation of the preceding prefix. No word is empty. Write $w_i=v_i{a}_i$ by deleting its last letter. A well-quasi-order has an infinite nondecreasing subsequence of any sequence: if no member of an infinite subsequence had infinitely many later upper bounds within it, one could recursively avoid the finitely many upper bounds of earlier choices and construct a bad sequence. Choose a member with infinitely many later upper bounds, restrict to those bounds and repeat. Apply this to get $a_{i_0}⪯a_{i_1}⪯\cdots$.

The sequence $w_0,\dots ,w_{i_0-1},v_{i_0},v_{i_1},\dots$ is still bad. An earlier prefix word embedding into a $v_{i_j}$ would embed into $w_{i_j}$, contrary to the original bad sequence. An embedding $v_{i_j}⪯v_{i_k}$ would extend by the comparable last letters to $w_{i_j}⪯w_{i_k}$, equally impossible. But its next word at position $i_0$ is strictly shorter than $w_{i_0}$, contradicting minimality. This proves Higman's lemma, including the possibility that a deleted word is empty, since that would make the proposed bad continuation impossible immediately.

We now prove the labelled version of Kruskal's tree theorem for labels in any well-quasi-order $Q$. Assume there is a bad sequence $T_0,T_1,\dots$, and choose one minimal in vertex count at each position, subject to bad extendibility. Let $\mathcal{S}$ be the collection of rooted subtrees obtained by deleting a root and taking one of its child branches, over all $T_i$.

This collection is well-quasi-ordered. Otherwise take a bad sequence $U_j$ from $\mathcal{S}$. Only finitely many of these objects can come from any bounded initial segment of the $T_i$, since that segment has only finitely many child branches and a bad sequence cannot repeat an object. Pass to a subsequence with $U_j$ a child branch of $T_{k_j}$ and $k_0<k_1<\cdots$. Thenis bad: a prefix tree embedding into $U_j$ would embed into $T_{k_j}$, and the $U_j$ are already bad among themselves. The next object $U_0$ has fewer vertices than $T_{k_0}$, contradicting the minimal bad choice. Notice that a child branch does embed into its full tree under the stated homeomorphic convention.

List each tree's child branches in any chosen order. The preceding result and Higman's lemma make these finite lists well-quasi-ordered. The product of two well-quasi-orders is well-quasi-ordered: first thin to an infinite nondecreasing subsequence in one coordinate and then find an increasing pair in the other. Therefore there are $i<j$ such that the root label of $T_i$ increases to that of $T_j$, and the child list of $T_i$ embeds as a subsequence into the child list of $T_j$, with each source branch homeomorphically embedding into its matched branch.

Map the root of $T_i$ to the root of $T_j$, and use these branch embeddings below it. Different child branches map into different host branches, so their lowest common ancestor maps to the host root. Within each branch it is preserved by the chosen embedding. Thus the whole map is injective, preserves all lowest common ancestors and respects labels, contradicting badness. Finite rooted trees labelled by a well-quasi-order are well-quasi-ordered under homeomorphic embedding. Taking one label proves Kruskal's tree theorem. If one uses a root-preserving convention, mark the root by a separate label incomparable with all ordinary labels and apply the labelled theorem; the marked root then has to map to the marked root. No adjacency-preservation assertion is being made.

For Friedman's finite form of Kruskal's theorem, fix $k\in \mathbb{N}$. The required finite conclusion isAssume there were arbitrarily long bad sequences satisfying these size bounds. Form the tree of their finite prefixes, using rooted-tree isomorphism classes as objects. At position $i$ only finitely many finite rooted trees have at most $k+i$ vertices, so this prefix tree is finitely branching and has nodes at arbitrarily large depths. König infinity lemma supplies an infinite branch: at each step some child must still have arbitrarily deep extensions, because there are only finitely many children. The branch is an infinite bad sequence of finite rooted trees, contradicting Kruskal's theorem. Thus such an $N$ exists. The argument also works for any prescribed size-bound function, or any fixed finite label set, because each position then still has finitely many possible objects.

Write $\theta \to (\eta {)}_{\lambda }^r$ when every $\lambda$-coloring of the $r$-element subsets of $\theta$ has a homogeneous subset of order type $\eta$. The Erdős-Rado theorem for pairs states, for infinite $\lambda$,In particular a countable-color partition of pairs from $(2^{{\aleph }_0}{)}^{+}$ has an uncountable homogeneous set. The standard Erdős-Rado theorem for finite arities isWe prove it, including the pair case, by constructing an end-homogeneous routing tree.

For a coloring $c:[\theta {]}^{r+1}\to \lambda$, $r\ge 1$, route each vertex $\beta <\theta$ as follows. Given its previously selected increasing ancestors, choose the least $\gamma \le \beta$ greater than all those ancestors such thatThe candidate $\beta$ always qualifies. Select it and stop if it is the minimum; otherwise add the selected $\gamma$ to the ancestors and continue, including at limit stages. The ancestors are strictly increasing below $\beta$, so the process must stop. If a selected ancestor $\gamma$ is routed separately, its earlier path is the same: its color constraints agree with those of $\beta$ and the same least choices are forced. Thus the paths define a tree order on the vertices.

A node at depth $\alpha$ is determined by the table of its colors on the $r$-subsets of its ancestors. Given the table on $[\alpha {]}^r$, recursively take the least compatible candidate at each depth; at a limit depth use all preceding constraints. This recovers both the path and its final node. ThereforeAlong any branch, once an $r$-tuple $s$ of ancestors is fixed, the color $c(s\cup \{\beta \})$ is independent of all subsequent choices of $\beta$ on that branch. This is exactly end-homogeneity.

For the pair case take $r=1$ and $\theta =(2^{\lambda }{)}^{+}$. If all node depths were below ${\lambda }^{+}$, then each level would have size at most ${\lambda }^{\lambda }\le 2^{\lambda }$, and the union of ${\lambda }^{+}$ levels would have size at most $2^{\lambda }$. This contradicts the number of vertices. Hence some node has at least ${\lambda }^{+}$ ancestors. On that branch assign to each ancestor its constant color to all later ancestors. Regularity of ${\lambda }^{+}$ implies that one of the $\lambda$ colors occurs ${\lambda }^{+}$ times, giving the desired homogeneous set. Its increasing enumeration has a subsequence of order type ${\lambda }^{+}$.

For the higher-arity induction let $\mu ={\beth }_{r-1}(\lambda )$, so $\theta =(2^{\mu }{)}^{+}$. At depths below ${\mu }^{+}$ the same bound is at most ${\lambda }^{\mu }\le 2^{\mu }$, forcing a branch of length ${\mu }^{+}$. End-homogeneity defines a coloring $d$ of its $r$-tuples by the common color of adjoining a later branch vertex. The previous-arity theorem gives a subset of order type ${\lambda }^{+}$ homogeneous for $d$, and every $(r+1)$-tuple from it then has the same color under $c$. The base case $r=0$ is the infinite pigeonhole principle at ${\lambda }^{+}$. This proves the full finite-arity statement.

One suitable ordinal partition-bound function isIt is nondecreasing and $f(\alpha )\ge \alpha$. It is total: choose an infinite cardinal $\lambda \ge |\alpha |$; the pair theorem supplies a homogeneous subset of size ${\lambda }^{+}$ for every allowed color number, and its order type contains a copy of $\alpha$. Thus $(2^{\lambda }{)}^{+}$ is a bound in the displayed minimum.

Let an uncountable cardinal $\kappa$ be the supremum of a cofinal increasing sequence of iterates of $f$, with each iterate and its successor still below $\kappa$. For every $\xi <\kappa$, monotonicity and some later iterate give $f(\xi )<\kappa$. Thus the relevant consequence of being such a supremum isIf the iteration already reaches a fixed point, its constant continuation of course has that fixed point as supremum as well. A strictly increasing countable iteration instead has a countable-cofinality supremum and cannot satisfy the uncountable regular tree-property condition below; one must not assume existence of the extra condition from iteration alone.

Here closure under $f$ forces a strong-limit bound. For infinite $\lambda <\kappa$, color distinct binary strings in $2^{\lambda }$ by their first differing coordinate. Three strings cannot have all three first-difference coordinates equal, because there are only two bit values at that coordinate. Hence this $\lambda$-coloring has no homogeneous triangle, and in particular no homogeneous subset of order type $\lambda +1$. ThereforeSince $\lambda +1<\kappa$ and $f(\lambda +1)<\kappa$, it follows that $2^{\lambda }<\kappa$ for every $\lambda <\kappa$.

Now impose the tree property: every tree of height $\kappa$, with nonempty levels of size below $\kappa$, has a cofinal branch. If this definition is extended to singular cardinals, it also forces regularity. For a singular $\kappa$, take disjoint chains of lengths cofinal in $\kappa$, one for each index below $\mathrm{cf}\kappa$. Every level has at most $\mathrm{cf}\kappa <\kappa$ nodes and the height is $\kappa$, but each branch remains in one shorter chain. A common new root may be added if rooted trees are required. Under the more usual convention the tree property is only defined at regular uncountable cardinals, so regularity is part of the convention instead.

For a coloring $c:[\kappa {]}^2\to \nu$ with $\nu <\kappa$, the routing tree has levels of size at most ${\nu }^{|\alpha |}<\kappa$ by the strong-limit property. If some node has height at least $\kappa$, there is already an end-homogeneous branch of that length. Otherwise the tree has height exactly $\kappa$: a smaller number of levels of size below $\kappa$ could not contain its $\kappa$ nodes, by regularity. The tree property then supplies a cofinal branch. Along it, one of the fewer than $\kappa$ ancestor colors occurs $\kappa$ times, again by regularity. Thus $\kappa \to (\kappa {)}_{\nu }^2$ for every $\nu <\kappa$, givingMoreover the closure argument gives strong limit and the tree argument gives regularity. Thus an uncountable $f$-closed cardinal with the tree property is strongly inaccessible.

The final printed assertion requires that qualification. The ordinary tree property alone does not imply strong inaccessibility. At $\omega$ it is König's infinity lemma and $\omega$ is not uncountable. Even when the convention excludes $\omega$, there are relative-consistency models in which ${\aleph }_2$ has the tree property, although a successor cardinal is never strongly inaccessible; this result is recalled in the introduction of Friedman, Honzik and Stejskalová. No proof of the bare implication is possible under that standard definition. The preceding paragraphs prove the corrected implication in the actual $f$-closure setting and the requested fixed-point conclusion, without silently replacing tree property by weak compactness.

A well-quasi-ordering is a reflexive transitive relation such that every infinite sequence $x_0,x_1,\dots$ has $i<j$ with $x_i\le x_j$. An infinite sequence without such a pair is a bad sequence. For a finite rooted tree, let $u\wedge v$ denote the lowest common ancestor of two vertices. A homeomorphic embedding of a rooted tree into another is an injective map $h$ withThus it preserves branching and sends each edge to a nonempty downward path, with different branches separated. The source root may map to a vertex below the target root. Kruskal's tree theorem says that finite rooted trees are well-quasi-ordered under these embeddings.

We first establish the word lemma used in the proof. The Higman lemma says that finite words over a well-quasi-ordering $Q$ are well-quasi-ordered by subsequence embedding with increased letters. Every infinite sequence in $Q$ has an infinite nondecreasing subsequence. To see this, some term must have infinitely many later terms above it: otherwise, repeatedly choosing past all finitely many successors of earlier chosen terms constructs a bad sequence. Apply this observation again inside that infinite upper cone, and repeat.

If the Higman lemma failed, choose a minimal bad sequence of words $w_0,w_1,\dots$, minimizing length at each position among choices admitting a bad continuation. None is empty. Write $w_i=u_i{a}_i$, with last letter $a_i$, and choose indices $i_0<i_1<\cdots$ on which the $a_i$ are nondecreasing. Thenis still a bad sequence. A comparison from the original prefix into some $u_{i_j}$ would give one into $w_{i_j}$. A comparison $u_{i_j}\le u_{i_k}$ would extend by $a_{i_j}\le a_{i_k}$ to $w_{i_j}\le w_{i_k}$. Both contradict the original badness. But the replacement at position $i_0$ is shorter than $w_{i_0}$, contradicting minimality. This proves the Higman lemma.

Now suppose Kruskal's tree theorem fails and choose a minimal bad sequence $T_0,T_1,\dots$, minimizing the number of vertices at each stage. Let $\mathcal{B}$ contain all proper descendant-rooted subtrees of all $T_i$. We claim that $\mathcal{B}$ is well-quasi-ordered by rooted-tree homeomorphic embeddings. Otherwise take a bad sequence $U_0,U_1,\dots$ from it. Each finite set of host trees supplies only finitely many subtrees, so after passing to a subsequence we may arrange that $U_j$ is a proper subtree of $T_{k_j}$ with $k_0<k_1<\cdots$. The sequenceis bad: a comparison from a prefix tree into $U_j$ would compose with its inclusion into $T_{k_j}$ and contradict the original badness; comparisons among the $U_j$ are excluded by construction. Yet $U_0$ is smaller than $T_{k_0}$, contradicting minimality. This proves the claim.

List the immediate-child subtrees of each $T_i$ in any fixed order. These are finite words over $\mathcal{B}$. By the Higman lemma, some earlier child list embeds into a later one with increased letters. The selected child subtrees embed into distinct child branches of the later tree. Map the source root to the target root and use these embeddings in the selected branches. The paths from the target root to the embedded child roots are separated because the target child branches are distinct. The resulting injection preserves lowest common ancestors, giving $T_i⪯T_j$, a contradiction. This proves Kruskal's tree theorem completely. It also gives the root-preserving homeomorphic version: once the weaker relation is well-quasi-ordered on all finite rooted trees, apply the Higman lemma to their child lists to obtain a comparison preserving the root.

For the proposed adjacency-preserving rooted-tree embedding, the answer is no: it is not a well-quasi-ordering. For every $m\ge 1$, form $T_m$ from a stem of $m$ edges starting at the root and then attach two leaves to its terminal vertex. The only vertex with two children is at depth $m$. A root-preserving adjacency injection preserves depths: the unique path of length $d$ from the root maps to a simple path of length $d$ from the target root. The image of a vertex with two children must still have two distinct children. Thus an embedding $T_m\to T_n$ must send the branch vertex at depth $m$ to the unique branch vertex at depth $n$, forcing $m=n$. ThereforeThis is the branching-depth antichain of rooted trees. Homeomorphic embeddings can stretch the stem and hence do not have this obstruction.

A well-quasi-ordering is a reflexive transitive relation for which every infinite sequence has $i<j$ with $x_i\le x_j$. A bad sequence has no such pair. The labelled version of Kruskal's tree theorem says that finite rooted trees labelled in any well-quasi-ordering are themselves well-quasi-ordered by label-monotone tree embedding.

More explicitly, an embedding is an injective map of vertices preserving lowest common ancestors, and satisfying ${\ell }_T(v)\le {\ell }_S(h(v))$ at every vertex. The root need not map to the host root. This is a homeomorphic embedding of a rooted tree: an edge can map to a longer path, but distinct branches must separate at the image of their common ancestor. We shall prove the stronger version in which every vertex's children are linearly ordered and embeddings respect that ordering. Forgetting the child order gives the stated result for unordered rooted trees.

We first establish the two well-quasi-ordering facts used in the proof. Every infinite sequence in a well-quasi-ordering has an infinite nondecreasing subsequence. Indeed, color an index pair $i<j$ according to whether $x_i\le x_j$. The infinite two-color Ramsey theorem gives a homogeneous infinite set; the negative color would be a bad sequence, so the positive color gives the required subsequence. It follows that the componentwise product of two well-quasi-orderings is a well-quasi-ordering: first extract a nondecreasing subsequence in one coordinate, then find a good pair in the other.

Next prove Higman lemma: finite words over a well-quasi-ordering $Q$, ordered by subsequence embedding with coordinatewise increase of letters, are a well-quasi-ordering. Suppose not, and choose a minimal bad sequence $w_0,w_1,\dots$ by making the length of $w_n$ minimal among all choices admitting an infinite bad continuation of the already fixed prefix. No word is the empty word, since that embeds in every later word. Write $w_n=v_n{a}_n$ with $a_n\in Q$. Extract indices $i_0<i_1<\cdots$ for which $a_{i_0}\le a_{i_1}\le \cdots$. ConsiderIt cannot be a bad sequence, since its first replacement is shorter than the minimal choice $w_{i_0}$. But a good pair within the original prefix is impossible. A prefix word embedding into $v_{i_j}$ would embed into $w_{i_j}$, contradicting the original bad sequence. And $v_{i_j}$ embedding into $v_{i_k}$ would, after appending the ordered last letters, embed $w_{i_j}$ into $w_{i_k}$, also impossible. This contradiction proves Higman lemma, including words of arbitrary finite length.

Now suppose there is a bad sequence of finite ordered labelled rooted trees. Choose a minimal bad sequence $T_0,T_1,\dots$ by minimizing the number of vertices of $T_n$, subject to the fixed prefix having an infinite bad continuation. Existence of a least possible size uses ordinary well-ordering of the natural numbers; after selecting such a tree retain a bad continuation to make the next choice.

Let $\mathcal{S}$ be the collection of all proper rooted subtrees of all $T_n$, with inherited labels and child ordering. These are the subtrees rooted at vertices other than the root, and each embeds into its containing tree. We claim $\mathcal{S}$ is a well-quasi-ordering under the same label-monotone tree embedding.

Otherwise choose a bad sequence $U_0,U_1,\dots$ from $\mathcal{S}$, and choose for each a containing tree $T_{n_j}$. The indices $n_j$ are unbounded in every tail: finitely many containing trees have only finitely many rooted subtrees, and an infinite bad sequence cannot repeatedly use one of these, since it embeds into itself. Passing to a subsequence, arrange $n_0<n_1<\cdots$. The spliced sequenceis bad. A good pair within either piece is already excluded. A comparison $T_k⪯U_j$, where $k<n_0\le n_j$, would compose with $U_j⪯T_{n_j}$ to give $T_k⪯T_{n_j}$, contradicting the original bad sequence. But $U_0$ is smaller than $T_{n_0}$, contradicting the minimal choice at that position. This proves the claim about $\mathcal{S}$.

Describe $T_n$ by its root label $q_n\in Q$ and its finite ordered list $C_n$ of child subtrees. Every entry of $C_n$ lies in $\mathcal{S}$. By Higman lemma, ${\mathcal{S}}^{\ast }$ is a well-quasi-ordering; hence so is $Q\times {\mathcal{S}}^{\ast }$. There exist $i<j$ with $q_i\le q_j$ and an increasing injection matching the child subtrees in $C_i$ to child subtrees in $C_j$, each by an embedding. Map root to root and combine these child embeddings. Different matched children lie in different target branches, so their paths meet exactly at the target root; within each branch the chosen embedding already preserves lowest common ancestors. The resulting map is a label-monotone tree embedding $T_i⪯T_j$, a contradiction. ThereforeThe empty labelled tree, if included by convention, embeds into every tree and causes no exception. A common stronger formulation requires the source root to map to the target root. It also follows: the theorem just proved makes all labelled child subtrees a well-quasi-ordering, and the product $Q\times \mathcal{T}(Q{)}^{\ast }$ then provides a good pair with roots explicitly matched, by the same final assembly. Internal child roots may map further down their matched branches. This must not be confused with edge-to-edge embedding, for which the theorem is false in general.

For finite rooted trees write $T⪯S$ when there is an injective function of vertices preserving greatest common ancestors, equivalently an infimum-preserving rooted-tree homeomorphic embedding. No linear ordering of siblings is imposed. Kruskal's tree theorem says that every infinite sequence has an earlier tree embedding into a later tree: this embedding relation is a well-quasi-ordering.

The finite form uses a parameter $k$ to restrict the growth of the trees. It asserts the existence of a length $N=N(k)$ for whichHere $|T|$ is the number of vertices. The parameter $k$ is universally quantified; changing the starting index just shifts the parameter. This is Friedman's finite form of Kruskal's theorem.

Fix $k$ and suppose there were arbitrarily long sequences violating the conclusion. Form a tree whose nodes are their finite prefixes, including the empty prefix. Choose one representative of each finite rooted-tree isomorphism type. At position $i$ there are only finitely many choices, since the tree has at most $k+i$ vertices. Hence this finite bad-sequence tree is finitely branching. It has nodes at arbitrarily large heights by the supposed failure of the finite form. König infinity lemma supplies an infinite branch. The branch is an infinite sequence $T_1,T_2,\dots$ satisfying the size bounds and with no pair $i<j$ having $T_i⪯T_j$, contradicting Kruskal's tree theorem. Therefore the finite length exists for every $k$.

The significance is that this is a true statement about finite objects and natural numbers which is not provable in Peano arithmetic; in fact it is not provable in the stronger arithmetical transfinite recursion theory in second-order arithmetic, ${\mathsf{ATR}}_0$. It is a natural combinatorial instance of incompleteness. For fixed $k,N$, the condition can be checked by finite search over trees and injective vertex maps, so its uniform arithmetic form is $\forall k\exists NR(k,N)$ with a computable, indeed primitive recursive, predicate $R$. Thus its least sufficient length is a total computable function, but its totality cannot be proved in those theories. Each fixed numerical instance can nevertheless be proved in Peano arithmetic by verifying some particular finite witness. The obstruction concerns the uniform statement for all parameters, rather than the decidability of any one finite search.

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:

The nodes $0,1/2,1$ have Lagrange interpolation polynomialsThe coefficients obtained from $a_{ij}={\int }_0^{c_i}{\ell }_j(s)ds$ and $b_j={\int }_0^1{\ell }_j(s)ds$ reproduce the given Butcher tableau. In particular, the second row's last entry is $-1/24$, which is missing from the TeX transcription. Thus this is the three-stage Lobatto IIIA method.

One applicable collocation theorem is that $s$-stage Lobatto IIIA collocation has order $2s-2$. Alternatively, the fourth-order conditions for a Runge-Kutta method give a direct verification. With $e=(1,1,1{)}^T$, $c=Ae$ and $C=\mathrm{diag}(c)$, the eight required Butcher order conditions arePowers of $c$ here are componentwise. Substitution satisfies all eight. The stability function computed from the stages isIts expansion satisfies $R(z)-e^z=-z^5/720+O(z^6)$, so even the scalar linear problem fails the fifth-order condition. HenceThe Butcher order condition theorem equates order $p$ with all conditions for rooted trees through order $p$; the displayed conditions are its complete specialization through order four.

An element $g$ fixing the first level restricts to an automorphism $g_i$ on each rooted subtree, and composition is coordinatewise. Thereforeis a homomorphism. If all three sections are trivial, $g$ fixes every word, so $\varphi$ is injective.

Directly from the recursions,The generators found in the preceding part therefore have every section in $G$, so $\varphi ({\mathrm{Stab}}_G(1))\subseteq G^3$.

Moreover, every coordinate projection of this image contains both $a$ and $b$, and is therefore onto $G$. Since $a$ acts transitively on the first level, induction shows that $G$ acts transitively on every level of the rooted tree. The $n$th level has $3^n$ vertices, so the orders of these finite orbits are unbounded. Hence $G$ is infinite.

Path compression changes parent pointers during a disjoint-set find operation so that future queries traverse fewer edges. Full path compression first follows the entire parent route to its root of a tree, then makes every member on that route point directly to that same root of a tree. No member changes its block of a set partition or its disjoint-set representative. Pointers outside the traversed route stay as they were. The following iterative Python implements full path compression and union by rank; parent and rank are initially indexed arrays with parent[x] = x and rank[x] = 0 for every valid member.

def find(x):
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != x:
        following = parent[x]
        parent[x] = root
        x = following
    return root

def unite(x, y):
    a, b = find(x), find(y)
    if a == b:
        return False
    if rank[a] < rank[b]:
        a, b = b, a
    parent[b] = a
    if rank[a] == rank[b]:
        rank[a] += 1
    return True

Starting from the displayed disjoint-set forest, find(3) traverses $3\to 4\to 2$, returns $2$ and changes only $\mathrm{parent}[3]$ from $4$ to $2$. The route $5\to 6\to 2$ still has two edges. Then find(5) changes only $\mathrm{parent}[5]$ from $6$ to $2$. The final parent array is $(2,2,2,2,2,2,7)$; every stored rank retains its displayed value. The rooted tree at $2$ now has height one although its root's rank is two. Root $7$ still represents a separate singleton set.

The two-pass algorithm first discovers the answer and then reuses it. During the second pass, saving following before overwriting the pointer preserves the remaining route. Every replacement pointer targets the original root of a tree, proving that the partition of a set is unchanged.

Full path compression is one specific rule. The authored UF.java implementation instead uses path halving, redirecting a visited member to its parent's parent while advancing along the route. Its union by rank rule agrees with the one above.^[ref]