« Section 2.4: A Deductive Calculus

Section 2.4: Problem 2 Solution »

Section 2.4: Problem 1 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
For a term , let be the expression obtained from by replacing the variable by the term . Restate this definition without using any form of the word “replace” or its synonyms. Suggestion: Use recursion on . (Observe that from the new definition it is clear that is itself a term.)
As suggested, we define using recursion. Let be the set of variables and constant symbols, be the set of terms, and be defined
Then, since is freely generated from by where is an -place function symbol and , there exists a unique extension such that a) if , and b) . We define to be .
Now, once is defined, we can refer to the forbidden word “replace” to verify that is indeed what we intended it to be. For , we have , which is with replaced by . For any other variable symbol , we have , and for any constant symbol , we have , that is, in both cases, the term is left unchanged as there is no in it at all. For any other term of the form , we have , i.e. is obtained by substituting for in each term , .
Finally, we observe that by definition, the extension , i.e. is a term.