What is the purpose of a certain problem?

Question

I am self-learning the material and I have encountered this question in the lecture notes by Stephen G. Simpson that I am reading:

Let $L=\{R,\ldots\}$ be a language which includes a binary predicate $R$. Let $S$ be a set of $L$-sentences. Assume that for each $n\ge 1$ there exists an $L$-structure $(U_{n},R_{n},\ldots)$ satisfying $S$ and containing elements $a_{n1},\ldots, a_{nn}$ such that $\langle a_{ni}, a_{nj}\rangle\in R_{n}$ for all $1\leq i<j\leq n$. Prove that there exists an $L$-structure $(U_{\infty},R_{\infty},\ldots)$ satisfying $S$ and containing elements $a_{\infty i}$, $i=1,2,\ldots$ such that $\langle a_{\infty i}, a_{\infty j}\rangle\in R_{\infty}$ for all $1\leq i < j$.

It provides a hint: Consider for each $i\ge 1$ new unary predicate $P^{i}$, a language $L^{*}=L\cup\{P^{1},P^{2},\ldots\}$, and a set $S^{*}$ consisting of $S$ plus $\exists x\: P^{i}x$, for all $i\ge 1$ plus $\forall x\forall y\: \big((P^{i}x\wedge P^{j}y)\Rightarrow Rxy\big)$, for all $1\leq i<j\leq n$.

It can be solved by an appropriate application of the Compactness Theorem. My question is: What is the point this problem is trying to illustrate? As far as I can tell it serves to illustrate that if there are $n$ distinct things for any arbitrary large $n\in\mathbb{N}$ then there are infinitely many distinct things. That is, if a set of sentences is satisfied in any structure of finite arbitrary cardinality, then it must also be satisfied in some infinite structure. However, I have seen simpler proofs of this fact.

What is the meaning of the unary predicates $P^{i}$. Where does the idea to add the new sentences come from? That is, what is the meaning of

1. $\exists x\: P^{i}x$, and
2. $\forall x\forall y\: \big((P^{i}x\wedge P^{j}y)\Rightarrow Rxy\big)$, for $1\leq i<j$?

We may intuitively assign meaning to $P^{i}x$ as -$x$ has cardinality $i$- and $Rxy$ to be $x\subset y$. That way 1. means -there is a set of cardinality $i$- and -any set of cardinality $i$ is contained in any set of cardinality $j$ whenever $1\leq i<j$-

Any other ideas as to the purpose of this problem?

Answer 1

Well, for one thing, the exercise is good practice in applying the compactness theorem!

But the statement is also interesting. I would parse it like this: Given a language with a binary relation symbol $R$, there is no theory $S$ with the property that models of $S$ contain arbitrarily long finite transitive $R$-chains, but no model contains an infinite transitive $R$-chain.

Here are some example applications:

• There is no theory whose models are exactly the graphs with no infinite cliques.
• If a theory $T$ extending the theory of linear orders has no models with an infinite increasing sequence, then there is a bound $N\in \omega$ such that no model has an increasing sequence of length longer than $N$. In particular, every model of $T$ is a finite linear order of length at most $N$.
• For any set theory $T$ (interpreting $Rxy$ as $y\in x$), if $T$ is non-trivial enough that it proves that all the von Neumann ordinals exist, then $T$ has models that are not well-founded.

As for what's going on in the proof: It's a bit weird that Simpson introduces these unary predicate symbols instead of constant symbols. The natural way to proceed would be to introduce new constant symbols $(c_n)_{n\in \omega}$ and new axioms $Rc_ic_j$ for all $i<j$. Then apply compactness, and in the model you get, the interpretations of the new constants form an infinite transitive $R$-chain.

Instead, Simpson introduces a unary predicate $P^n$ instead of $c_n$, asserts $\exists x P^nx$ (this ensures we can pick some element satisfying $P^n$, to play the role of my $c_n$) and $\forall x\forall y((P^ix\land P^jy)\rightarrow Rxy)$ (this ensures that whatever $c_i$ and $c_j$ we pick satisfying $P^i$ and $P^j$, we have $Rc_ic_j$). I'm guessing Simpson does this because he's only working with relational languages at this point in the notes?

Answer 2

My guess is that this problem is specifically trying to demonstrate a slightly advanced language-augmentation technique, which could inspire other compactness arguments. (What if the predicates $P$ were indexed by some other countable ordering?)

This argument might make more sense if you replace $\exists x : P^i(x)$ with $\exists! x: P^i(x)$ (there exists a unique $x$ satisfying $P^i$). In this case, the $P^i$ together would select out a "canonical length-$n$ chain under the $R$ relation" with $P^i$ being true of the $i$th element of the chain. Here an $R$-chain is a sequence of elements where each element is $R$ the next.