Mathematical Logic (Shoenfield) : Lemma 1

Question

Well, I am new learning about mathematical logic and I am using Mathematical Logic, Shoenfield. Now, I have a question regarding this lemma (the first lemma in that book) :

Given two finite sequences of n designators, A and B the two expressions formed by juxtaposing each of the sequences, if A and B are compatible, then the k-th designator in the first sequence is the k-th designator in the second one.

Now, my question is the following : Can't we have 2 sequences of designators with a similar number of elements and with the first designators of different lengths? (that would mean that the designators are not the same, even if the juxtaposition is the same...)

Answer 1

The result, also known as Unique readibility lemma is a "nitpicking" result whose proof needs a simple induction. But the "meaning" of the proof is not so transparent...

An expression is a finite string of symbols of the alphabet [see page 14].

Definitions [see page 15] :

A designator is an expression which is either a term or a formula.

We say that two expressions are compatible if one of them can be obtained by adding some expression (possibly the empty expression) to the right end of the other.

In other words, two expressions $A$ and $B$ are compatible if one of them (say $A$) is an initial sub-string of the other [example : $A$ is $s_1 s_2 s_3$ and $B$ is $s_1 s_2 s_3 s_4 s_5$].

For simplicity, I'll restrict myself to terms.

The inductive proof must rely strictly on the formal definition of term :

i) a variable is a term;

ii) if $u_1, \ldots, u_n$ are terms and $f$ is an $n$-ary [function symbol], then $f u_1 \ldots u_n$ is a term.

Now for the Lemma :

If $u_1, \ldots, u_n$, $u'_1, \ldots, u'_n$ are designators and $u_1 \ldots u_n$ and $u'_1 \ldots u'_n$ are compatible, then $u_i$ is $u'_i$ for $i=1,\ldots, n$.

Please, note that $u_1, \ldots, u_n$ and $u'_1, \ldots, u'_n$ are lists of terms, while $u_1 \ldots u_n$ and $u'_1 \ldots u'_n$ are expressions (i.e. strings of juxtaposed terms).

The proof is by induction on the lenght of $u_1 \ldots u_n$ and thus we have the usual two steps :

(i) Base case : $n=1$. This again has two sub-cases.

First sub-case : $u_1$ is a variable $x$.

The result is immediate, because if $u_1$ and $u'_1$ are compatible, we must have $u_1=x=u'_1$ because there is no way to add symbols to the right of a variable $x$ in a way that the resulting expression is still a term [the expressions $xy$ or $xfuz$ are not syntactically correct].

Second sub-case : $u_1$ is $f v_1 \ldots v_k$, with $f$ $k$-ary. Again, $u'_1$ is obtained from it adding some expression (possibly none) to the right.

But, as in the previous case, if the number of terms $v_i$ in $f v_1 \ldots v_k$ matches the arity of $f$, we cannot add new symbols to the right to produce a syntactically correct term.

Thus, again, $u_1= f v_1 \ldots v_k = u'_1$.

The next step is :

(ii) Induction step : assume that the property holds for $n$ and prove it for $n+1$.

And this is basically what you find in the textbook.

Conclusion : if we now re-read the statement of the Lemma :

If $u_1, \ldots, u_n$, $u'_1, \ldots, u'_n$ are terms and $u_1 \ldots u_n$ and $u'_1 \ldots u'_n$ are compatible, then $u_i$ is $u'_i$ for $i=1,\ldots, n$,

that means :

if we have two sequences of terms of equal lenght that are compatible, then they must be equal.

This amounts to say that we cannot have two sequences of same lenght that start the same way but that "diverge" after a certain point.

---

The case regarding formulas is similar, taking into account [page 15] that formulas are "formally" written in prefix notation and thus $u \lor v$ is a (useful) abbreviation for $\lor u v$.

An atomic formula is $p a_1 \ldots a_k$ with $p$ a $k$-ary predicate symbol : thus, the reasoning will be exactly as that for terms with function symbols.

We have to manage the connectives and quantifier cases, and now there is a difference : in principle we may have a formula $A$ whose expression is $\lnot u$ that is part of a more complex formula $B$ whose expression is $\lnot u \lor v$.

But... we have to follow strictly the syntactical specifications, and thus we have to consider that formulas are written in prefix notation; this means that $B$ must be : $\lor \lnot u v$.

---

---

Compare with Heinz-Dieter Ebbinghaus & Jörg Flum & Wolfgang Thomas, Mathematical logic (Springer, 2nd ed. 1994), page 20-22 where the same result is obtained in a "less terse way" (one and an half page, with the two cases: terms and formulas, treated independently).