Section 2.1: 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

Give a precise definition of what it means for the variable $x$ to occur free as the $i$ th symbol in the wff $\alpha$ . (If $x$ is the $i$ th symbol of $\alpha$ but does not occur free there, then it is said to occur bound there.)

I assume we count all symbols regardless of whether they are variables, constants or any other symbols.

For an atomic formula $\alpha$ , $x$ occurs free as the $i$ th symbol in $\alpha$ iff it occurs as the $i$ th symbol in $\alpha$ .
$x$ occurs free as the $i$ th symbol in $(\neg\alpha)$ iff it occurs free as the $(i-2)$ th symbol in $\alpha$ .
$x$ occurs free as the $i$ th symbol in $(\alpha\rightarrow\beta)$ iff it occurs free as the $(i-1)$ th symbol in or it occurs free as the $(i-\#\alpha-2)$ th symbol in $\beta$ , where $\#\alpha$ is the length of $\alpha$ .
$x$ occurs free as the $i$ th symbol in $\forall v_{i}\alpha$ iff $x\neq v_{i}$ and it occurs free as the $(i-2)$ th symbol in $\alpha$ .

Alternatively, we could use the recursion theorem of Section 1.4 (and unique readability of wffs proved in Section 2.3, which is needed to argue that wffs are freely generated) as follows.

For an atomic formula $\alpha$ , let $h(\alpha)$ be the set of all pairs $<i,x>$ such that the variable $x$ is the $i$ th symbol in $\alpha$ .
We extend $h$ to $\overline{h}$ defined for all wffs as follows.
1. $\overline{h}(\mathcal{E}_{\neg}(\alpha))=\{<i,x>|<i-2,x>\in\overline{h}(\alpha)\}$ .
2. $\overline{h}(\mathcal{E}_{\rightarrow}(\alpha,\beta))=\{<i,x>|<i-1,x>\in\overline{h}(\alpha)\}$ $\cup\{<i,x>|<i-\#\alpha-2,x>\in\overline{h}(\beta)\}$ .
3. $\overline{h}(\mathcal{Q}_{i}(\alpha))=\{<i,x>|x\neq v_{i}\mbox{ and }<i-2,x>\in\overline{h}(\alpha)\}$ .

Then, $x$ occurs free as the $i$ th symbol in $\alpha$ iff $<i,x>\in\overline{h}(\alpha)$ .

Subpages

Section 2.1: Problem 9 Solution

Section 2.1: Problem 9 Solution