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

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.

## 1 Answer

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.

• Hello! Your answer is very nice. But there is one problem that I still don’t understand, the OP said if $s = f t_1 t_2 \cdots t_n$ and $f$ is an n-ary function, then anything of the form $$f t_1 t_2 \cdots t_n ~u$$ where $u$ is some non-empty string cannot be a term because that shall not be a valid syntax for a term. Can you please comment on that? May 22 at 6:14
• I think you can use your inductive hypothesis, if that was a term then the first term in the argument of $f$ would have to be $t_1$, since $t_1 s$ for any non-empty string $s$ is not a term by hypothesis, similarly, the next term would have to be $t_2$ and so on, but then we must have $t_n u$ is the $n$th term in the arguements of $f$, which means $t_n$ is a proper initial segment of a term which contradicts the inductive hypothesis. This is a contradiction, so this string cannot be a term. May 22 at 7:17