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 be an expression consisting of variables, constant symbols, and function symbols. Show that is a term iff and for every terminal segment of we have . Suggestion: Prove the stronger result that if for every terminal segment of , then is a concatenation of terms. (This algorithm is due to Jáskowski.)
If is a term, then and every terminal segment of is a concatenation of one or more terms (Lemma 23B), therefore, (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 into terms. We prove it by induction on the length of .
For consisting of symbol, cannot be a function symbol, as otherwise . Hence, is either a variable or constant symbol. In both cases is a term, and .
Now, suppose that for all lengths less than the statement is true, and we consider of length . Its terminal segment of length satisfies the condition that every terminal segment of is a terminal segment of , hence, . Therefore, is a (unique) concatenation of terms. If the first symbol of is a variable or constant symbol, then . The first variable or constant symbol of is a term itself. And no term of length greater than 1 can start with a variable or constant (by definition). Moreover, is uniquely decomposed into terms, therefore, is uniquely decomposed into terms. If the first symbol of is an -place function symbol , then, since , . Then, together with the first terms of the unique decomposition of into terms forms one new term, and the resulting number of terms is , as instead of terms we now have just term. So, again, the number of terms in the decomposition is . The composition is also unique, as, by definition, a term starting with must be , where are terms, and due to the unique decomposition of into terms, are uniquely determined, and so is the decomposition of the remaining expression into terms.