# Mathematical Logic (Shoenfield) : Lemma 1

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...)

## 1 Answer

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).

• well, i thank you first for your clarification. But, the link you shared with me regarding the lemma makes me wonder in the book I am using is sufficient for a good basis in the field. In fact, I found myself needing a number of definitions (alphabet, polish notation, and other concepts used in the proofs in that website). – mehofc Jul 17 '19 at 8:34
• Otherwise, there is something bothering me in your proof. You said a variable juxtaposed to another variable is syntactically incorrect. But, that doesn't need to bother us, since we are dealing with compatibility, and compatibility is concerned with expressions, and expressions don't necessarily need to be correct (it is just a finite sequence of symbols), and they don't need to be terms in particular. – mehofc Jul 17 '19 at 8:45
• So, that makes me think the following. There may be a function symbol $\boldsymbol{f}$ defined like this : $\boldsymbol{f}(x, y, z)$ is $\boldsymbol{g}(x, y)\boldsymbol{h}(z)$ . So, the $\boldsymbol{f}$-term is compatible with the $\boldsymbol{g}$-term, but they are not the same. Can you point where I am wrong? or what do I need to understand that my example doesn't make sense? – mehofc Jul 17 '19 at 9:17
• @mehofc - but the Lemma (see above) is expressed for designators and "A designator is an expression which is either a term or a formula." – Mauro ALLEGRANZA Jul 17 '19 at 9:26
• Yeah, I know. If my point is valid for the version with terms, then it is for the whole lemma, since the conclusion of the lemma concerns the juxtaposition of terms, which means expressions (not necessarily terms). In other words, terms are special cases of designators. You are also using as an essential argument the correctness of the juxtaposition, which is not something necessary even in in the original version of the lemma. – mehofc Jul 17 '19 at 10:20