« Section 2.3: Problem 1 Solution

# Section 2.3: Problem 2 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
Let $\epsilon$ be an expression consisting of variables, constant symbols, and function symbols. Show that $\epsilon$ is a term iff $K(\epsilon)=1$ and for every terminal segment $\epsilon'$ of $\epsilon$ we have $K(\epsilon')>0$ . Suggestion: Prove the stronger result that if $K(\epsilon')>0$ for every terminal segment $\epsilon'$ of $\epsilon$ , then $\epsilon$ is a concatenation of $K(\epsilon)$ terms. (This algorithm is due to Jáskowski.)
If $\epsilon$ is a term, then $K(\epsilon)=1$ and every terminal segment $\epsilon'$ of $\epsilon$ is a concatenation of one or more terms (Lemma 23B), therefore, $K(\epsilon')>0$ (equals the number of terms in the concatenation).
We now prove the stronger result, as suggested. We also prove the uniqueness of the decomposition of such $\epsilon$ into $K(\epsilon)$ terms. We prove it by induction on the length of $\epsilon$ .
For $\epsilon$ consisting of $1$ symbol, $\epsilon$ cannot be a function symbol, as otherwise $K(\epsilon)\le0$ . Hence, $\epsilon$ is either a variable or constant symbol. In both cases $\epsilon$ is a term, and $K(\epsilon)=1$ .
Now, suppose that for all lengths less than $l$ the statement is true, and we consider $\epsilon$ of length $l$ . Its terminal segment $\epsilon'$ of length $l-1$ satisfies the condition that every terminal segment $\epsilon''$ of $\epsilon'$ is a terminal segment of $\epsilon$ , hence, $K(\epsilon'')>0$ . Therefore, $\epsilon'$ is a (unique) concatenation of $m=K(\epsilon')>0$ terms. If the first symbol of $\epsilon$ is a variable or constant symbol, then $K(\epsilon)=m+1$ . The first variable or constant symbol of $\epsilon$ is a term itself. And no term of length greater than 1 can start with a variable or constant (by definition). Moreover, $\epsilon'$ is uniquely decomposed into $m$ terms, therefore, $\epsilon$ is uniquely decomposed into $m+1=K(\epsilon)$ terms. If the first symbol of $\epsilon$ is an $n$ -place function symbol $f$ , then, since $K(\epsilon)=m+1-n>0$ , $n\le m$ . Then, $f$ together with the first $n$ terms of the unique decomposition of $\epsilon'$ into $m\ge n$ terms forms one new term, and the resulting number of terms is $m-n+1$ , as instead of $n$ terms we now have just $1$ term. So, again, the number of terms in the decomposition is $m-n+1=K(\epsilon)$ . The composition is also unique, as, by definition, a term starting with $f$ must be $ft_{1}\ldots t_{n}$ , where $t_{1},\ldots,t_{n}$ are terms, and due to the unique decomposition of $\epsilon'$ into terms, $t_{1},\ldots,t_{n}$ are uniquely determined, and so is the decomposition of the remaining expression into $m-n$ terms.