# 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
.