substitutability

In any logical system, the way to obtain (well-formed) formulas from existing ones is by attaching logical connectives to existing ones. For example, in classical propositional logic, if $\phi$ and $\psi$ are formulas, the following

$$\phi \vee \psi ,\mathrm{\neg }\phi ,\psi \wedge \phi$$

are formed by attaching logical connectives $\vee ,\mathrm{\neg }$, and $\wedge$ appropriately to $\phi$ and $\psi$.

Another convenient device is substitution:

replace all occurrences of some symbol $x$ in a formula $\phi$ by an expression $\psi$.

We denote the resulting expression by

$$\phi [\psi /x].$$

For example, in classical propositional logic, if $\phi$ is $p\wedge (\mathrm{\neg }r\vee p)$, then $\phi [(p\vee q)/p]$ is

$$(p\vee q)\wedge (\mathrm{\neg }r\vee (p\vee q))$$

On the other hand, the expressions

• $\phi [\mathrm{\neg }/p]$, which is $\mathrm{\neg }\wedge (\mathrm{\neg }r\vee \mathrm{\neg })$, and

• $\phi [q/\wedge ]$, which is $pq(\mathrm{\neg }r\vee q)$,

are not formulas. Thus, one must be careful when performing substitutions on formulas lest the resulting expressions are ill-formed. In other words, conditions must be placed on $x$ and $\psi$ in $\phi [\psi /x]$ in order that $\phi [\psi /x]$ is a (well-formed) formula. These conditions are called the substitutability conditions. In this entry, we will concentrate on substitutability conditions on predicate logic. Details on substitions in propositional logic can be found in here (http://planetmath.org/SubstitutionsInLogic).

Substitution in First-Order Logic

Substitution works pretty much the same way for first-order logic as in propositional logic. However, the substitutability conditions are more subtle. Take a look at the following example:

$$\exists x(x=1)$$

If we replace $x$ by $0$, we end up with

$$\exists 0(0=1),$$

which is non-sensical (not a wff). This is because $x$ occurs in the formula as a bound variable. (one reason why we distinguish the variables occurring in first order formulas into two types: free and bound).

We now formalize the notion of substitution in first-order logic. There are two parts: substitution for terms, and substitution for formulas.

Definition. For any term $t$, any symbol $x$, and any expression $s$, define $t[s/x]$ inductively, as follows:

1. if $t$ is an individual variable or a constant symbol, then $t[s/x]$ is $s$ if $t$ is $x$, and $t[s/x]$ is $t$ otherwise;

2. if $t$ is $f(t_1,\mathrm{\dots },t_n)$, where $f$ is an $n$-ary function symbol, and each $t_i$ is a term, then $t[s/x]$ is $f(t_1[s/x],\mathrm{\dots },t_n[s/x])$.

For example, if $t$ is $x+y$, then $t[(x-y)/x]$ is $(x-y)+y$.

It is easy to see that $s$ is a term and $x$ an individual variable, then $t[s/x]$ is a term. In addition, by induction, one can easily show that if the formula $s_1=s_2$ is true, so is the formula $t[s_1/x]=t[s_2/x]$.

Next, we define substitution for formulas. In light of the last example at the beginning of this section, we need to be a little careful.

Definition. Let $\phi$ be a formula, $x$ a symbol, and $s$ an expression. The expression $\phi [s/x]$ is again define inductively:

1. if $\phi$ is $t_1=t_2$, then $\phi [s/x]$ is $t_1[s/x]=t_2[s/x]$;

2. if $\phi$ is $R(t_1,\mathrm{\dots },t_n)$, then $\phi [s/x]$ is $R(t_1[s/x],\mathrm{\dots },t_n[s/x])$;

3. if $\phi$ is $\mathrm{\neg }\psi$, then $\phi [s/x]$ is $\mathrm{\neg }(\psi [s/x])$;

4. if $\phi$ is $\psi \vee \sigma$, then $\phi [s/x]$ is $\psi [s/x]\vee \sigma [s/x]$;

5. if $\phi$ is $\exists y\psi$, then $\phi [s/x]$ is $\exists y(\psi [s/x])$ if $x\ne y$, and $\phi [s/x]$ is $\phi$ otherwise.

Again, substitutions involving logical connectives $\to$, $\wedge$, and the universal quantifier $\forall$ can be derived from the rules given above.

For example, if $\phi$ is $\exists x(x=y\vee y=z)$, then $\phi [t/y]$ is $\exists x(x=t\vee t=z)$, whereas $\phi [t/x]$ is just $\phi$.

Given that $\phi$ is a formula, it is easy to see that if $x$ is an individual variable, and $s$ is a term, then $\phi [s/x]$ is a formula.

In addition, it is easy to see that sentences are not affected by substitutions: if $\phi$ is a sentence, then $\phi [s/x]$ is just $\phi$. In other words, sentences can not be changed into formulas with free variables.

Conversely, can a formula with free variables be changed into a sentence by substitution? Certainly. For example, if $\phi$ is

then $\phi [x/y]$ is

Although syntactically correct, this is undesirable in many situations, particularly when we are interested in the interpretations of these formulas. In the example above, we have changed , which many very well be true in many interpretations, into , something with a fixed meaning (and always false if is interpreted as the usual less than relation).

The problem with the situation described in the last paragraph arises because a free variable in $t$ becomes bound in $\phi [t/x]$. To eliminate this undesirable situation, we define the notion of “free for”:

Definition. Let $x$ be an individual variable, $t$ a term, and $\phi$ a formula. We define the relation$t$ is free for, or substitutable for $x$ in $\phi$, inductively, as follows:

1. $\phi$ is an atomic formula;

2. $\phi$ is $\mathrm{\neg }\psi$, and $t$ is free for $x$ in $\psi$;

3. $\phi$ is $\psi \vee \sigma$, and $t$ is free for $x$ in $\psi$ and in $\sigma$;

4. $\phi$ is $\exists y\psi$, and either

   • $x\notin \mathrm{FV}(\phi )$ ($x$ does not occur free in $\phi$), or

   • $y$ does not occur in $t$, and $t$ is free for $x$ in $\psi$.

In words, $t$ is free for $x$ in $\phi$ iff whenever $z$ is a variable in $t$, no literal subformula of $\phi$ of the form $\exists z\psi$ contains an occurrence of $x$ which is free in $\phi$.

For example, $f(x,y)$ is free for $x$ in the following formulas:

$$P(x,y),P(x)\vee \mathrm{\neg }Q(z),\mathrm{\neg }\exists x\mathrm{\neg }R(x,y),\text{and}\mathit{\hspace{1em}\hspace{1em}}\mathrm{\neg }S(y)\vee \exists yT(y,z),$$

but not in the following formulas:

$$\exists yP(x,y),Q(x)\vee \exists z\exists yR(x,y),\text{and}\mathit{\hspace{1em}\hspace{1em}}S(y)\to \forall y(T(y,y)\wedge \mathrm{\neg }Q(x)).$$

Given any formula $\phi$, we again write $\phi (x)$ to mean that variable $x$ occurs in $\phi$. A substitution instance of $\phi (x)$ is just $\phi [t/x]$, or $\phi (t)$ for short. Furthermore, if $t$ is free for $x$ in $\phi$, then $\phi (t)$ is called a free substitution instance of $\phi (x)$.

It is easy, by induction, to show that if terms $t_1$ and $t_2$ are free for $x$ in $\phi$, and that the formula $t_1=t_2$ is true, the substitution instances $\phi (t_1)$ and $\phi (t_2)$ are logically equivalent, as intended.