In their paper "Theories with recursive models" [1] Lerman and Schmerl used a version of Kruskal's tree theorem about finite n-augmented trees.


An n-augmented tree is a tree T together with $n$ unary relation symbols on its universe. The version of Kruskal's theorem is as follows


**Theorem 1.** Suppose $n<\omega$ and $A\_0,A\_1,\dots$ is a sequence of finite n-augmented trees. Then there are $i<j<\omega$ such that $A\_i$ embeds in $A\_j$.


They then used the following fact about $\Pi\_1$ sentences in the language of linear orderings with finitely many constants in their proof that any $\Sigma\_2$ theory of linear orderings has a recursive model. We denote with $L^F$ the language containing $\leq$ and a constant symbol $c\_i$ for every $i\in F$.


**Fact**. For every finite set of constants $F$ and every set $\Phi$ of $\Pi\_1$ sentences in $L^F$ consistent with the theory of linear orderings $LO$, there is finite $\Phi\_0\subseteq \Phi$ such that $LO\vdash \Phi\_0 \leftrightarrow \Phi$.


They do not give a proof of this fact and say that it follows easily from Theorem 1. I can see intuitively why the above fact should hold but how does this follow from Theorem 1?


[1] Lerman, Manuel, and James H. Schmerl. 1979. “Theories with Recursive Models.” The Journal of Symbolic Logic 44 (1): 59–76. <https://doi.org/10.2307/2273704>.



Kruskal's tree theorem and $\Pi_1$ sentences of linear orderings with finitely many constants
Towards a contradiction, suppose not. Then we can find a sequence $\phi\_0, \phi\_1, \dots$ from $\Phi$ such that for all $i$, $LO, \phi\_0, \dots, \phi\_i \not \vdash \phi\_{i+1}$. So for each $i$, there is an $L^F$-model $M\_i$ with $M\_i \vDash LO \wedge \phi\_0, \dots, \phi\_i \wedge \neg \phi\_{i+1}$. Since these are finitary $\Pi\_1$ sentences, it's not hard to argue that we can take $M\_i$ to be finite.


Each $M\_i$ is a $|F|$-augmented tree, using a unary relation symbol to pick out each constant, and interpreting a linear order as a non-branching tree. By Theorem 1, there is an $i < j$ with $M\_i$ embedding in $M\_j$. But $M\_j \vDash \phi\_{i+1}$, and since this is $\Pi\_1$, it must be that $M\_i \vDash \phi\_{i+1}$, contrary to choice of $M\_i$.


