Proof that no term (of a language of predicate logic) is a (non-empty) initial segment of another

Question

I sense that the following simple argument is invalid, but cannot figure out why.

Base Case:No variable or constant is an initial segment of a term, since the only terms that begin with variables or constants have length 1, and so lack initial segments.

Inductive Case:Suppose s is an initial segment of a term, t, where s is $f t_1 t_2 \cdots t_n$ for terms $t_i$. Then t is su, i.e., the string, s, followed by the string, u, for some non-empty string u. But, then, t is not a term, since an n-ary function symbol followed by n terms, followed by a non-empty string is a not a term.

Hence, no term is an initial segment of any other.

I did not make use of the inductive hypothesis, that no ti in s is the initial segment of any term. This is what makes me think I cheated somehow. Assuming that I did, I wonder if someone could show me how to prove the conclusion by means of induction on the complexity of terms without assuming that the tis in t are not initial segments of any terms (i.e., by merely assuming that the tis in s are not).

Any feedback would be greatly appreciated! Thanks in advance.

Answer 1

I think that we can refine it a little bit.

You are saying :

Suppose $s$ is an initial segment of a term $t$. Then $t$ is $su$, i.e., the string $s$ followed by the string $u$, $u$ non-empty

and that :

$s = ft_1t_2\ldots t_n$, for terms $t_i$.

Thus, we conclude with :

Then, $t$ is not a term, since an $n$-ary function symbol followed by $n$ terms, followed by a non-empty string is a not a term.

But - in general - $s$ can be also a variable $x$ or constant $c$.

I think that we have to "reverse" the argument, assuming that we have proved it for $t=x$ or $t=c$ (the base case for induction).

See :

• Heinz-Dieter Ebbinghaus & Jörg Flum & Wolfgang Thomas, Mathematical logic (2nd ed 1984), page 20.

We will use as induction property $P$ :

the property which holds for a string $\sigma$ iff for all terms $t'$, $\sigma$ is not a proper initial segment of $t'$ and $t'$ is not a proper initial segment of $\sigma$.

Let $t=ft_1t_2\ldots t_n$ a term, and assume that the property holds for $t_1,\ldots, t_n$ and let $t'$ be an arbitrary term.

We will show that $t'$ cannot be a proper initial segment of $t$, otherwise there would be a non-empty $s$ such that :

$t = t's$ --- (*).

Since $t'$ begins with $f$ (for $t$ begins with $f$), $t'$ cannot be a variable or a constant, thus it has the form $ft'_1 \ldots t'n$, for suitable terms $t'_1, \ldots,t'_n$.

From (*) we have :

$ft_1t_2\ldots t_n=ft'_1t'_2\ldots t'_ns$.

Cancelling the symbol $f$, we obtain :

$t_1 \dots t_n = t'_1 \ldots t'_ns$.

Therefore $t_1$ is an initial segment of $t'_1$ or vice versa. Since $t_1$ satisfies the induction property (by induction hypothesis), neither of these can be a proper initial segment of the other.

Thus $t_1 = t'_1$.

Cancelling $t_1$ on both sides we obtain :

$t_2 \ldots t_n = t'_2 \ldots t_ns$.

And so on ..., until we obtain :

empty string $ = s$.

This contradicts our assumption that $s$ is non-empty.