Section 2.4: Problem 9 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
(Re-replacement lemma) (a) Show by example that is not in general equal to . And that it is possible both for to occur in at a place where it does not occur in , and for to occur in at a place where it does not occur in .
(b) Show that if does not occur at all in , then is substitutable for in and . Suggestion: Use induction on .
(a) Let us temporarily call an instance of variable (or ) bounded by iff the instance is within some subformula of . Then, every instance of or in will become or depending on whether it is bounded by and/or (for cases). In two of these cases, if a variable is not bounded by (regardless of whether it is bounded by or not), it will eventually become in . If the variable is bounded by , then depending on whether it is bounded by or not, it will, correspondingly, remain the same as in or become in . Therefore, we have several potential cases when may become and may become . Based on this, consider equal to . Then , where a free turned out to be and a free turned out to be .
Based on this observation, it is clear that if there is no in then a) no can become (no extra ’s), and b) no is bounded by , hence, no can become (no missing ’s). A more formal prove is given in (b).
(b) As suggested we show the statement by induction. For a variable or constant symbol , if , then , otherwise and . For a term that does not contain , by induction, . Similarly, for an atomic formula that does not contain , by induction, (and is substitutable for in because the latter is an atomic formula as well).
Further, by definition and induction, if and not containing are such that is substitutable for in and , and , then a) , is substitutable for in it, and , and b) , is substitutable for in it, and . Moreover, not containing at all, and , , does not occur free, hence, is substitutable for in it, and .