3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Delta Psi
    May 22 at 6:14
  • $\begingroup$ 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. $\endgroup$ May 22 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.