Formal Logic/Predicate Logic/Free and Bound Variables

Free and Bound Variables

Informal notions

The two English sentences,

If Socrates is a person, then Socrates is mortal,

if Aristotle is a person, then Aristotle is mortal,

are both true. However, outside any context supplying a reference for 'it',

(1)    If it is a person, then it is mortal,

is neither true nor false. 'It' is not a name, but rather an empty placeholder. 'It' can refer to an object by picking up its reference from the surrounding context. But without such context, there is no reference and no truth or falsity. The same applies to the variable 'x' in

(2)    If x is a person, then x is mortal.

This situation changes with the two sentences:

(3)    For any object, if it is a person, then it is mortal,

(4)    For any object x, if x is a person, then x is mortal.

Neither the occurences of 'it' nor the occurences of 'x' in these sentences refer to specific objects as with 'Socrates' or 'Aristotle'. But (3) and (4) are nonetheless true. (3) is true if and only if:

(5)    Replacing both occurences of 'it' in (1) with a reference to any object whatsoever (the same object both times) yields a true result.

But (5) is true and so is (3). Similarly, (4) is true if and only if:

(6)    Replacing both occurences of 'x' in (2) with a reference to any object whatsoever (the same object both times) yields a true result.

But (6) is true and so is (4). We can call the occurences of 'it' in (1) free and the occurences of 'it' (3) bound. Indeed, the occurrances of 'it' in are bound by the phrase 'for any'. Similarly, the occurences 'x' in (2) are free while those in (4) are bound. Indeed, the occurences of 'x' in (4) are bound by the phrase 'for any'.

Formal definitions

An occurence of a variable $\alpha$ is bound in $\phi$ if that occurence of $\alpha$ stands within a subformula of $\phi$ having one of the two forms:

$\mathrm{\forall }\alpha \psi ,$

$\mathrm{\exists }\alpha \psi .$

Consider the formula

$(7)(\mathrm{\exists }{x}_0{F}_{\mathrm{0}}^{\mathrm{1}}(x_0)\to \mathrm{\forall }{y}_0{F}_{\mathrm{0}}^{\mathrm{1}}(y_0)).$

Both instances of $x_0$ are bound in (7) because they stand within the subformula

$\mathrm{\exists }{x}_0{F}_{\mathrm{0}}^{\mathrm{1}}(x_0).$

Similarly, both instances of $y_0$ are bound in (7) because they stand withing the subformula

$\mathrm{\forall }{y}_0{F}_{\mathrm{0}}^{\mathrm{1}}(y_0).$

An occurence of a variable $\alpha$ is free in $\phi$ if and only if $\alpha$ is not bound in $\phi$. The occurences of both $x_0$ and $y_0$ in

$(8)(F_{\mathrm{0}}^{\mathrm{1}}(x_0)\to G_{\mathrm{0}}^{\mathrm{1}}(y_0))$

are free in (8) because neither is bound in (8).

We say that an occurence a variable $\alpha$ is bound in by a particular occurence of $\mathrm{\forall }$ if that occurence is also the first (and perhaps only) symbol in the shortest subformula of $\phi$ having the form

$\mathrm{\forall }\alpha \psi .$

Consider the formula

$(9)\mathrm{\forall }{x}_0(F_{\mathrm{0}}^{\mathrm{1}}(x_0)\to \mathrm{\forall }{x}_0{G}_{\mathrm{0}}^{\mathrm{1}}(x_0)).$

The third and fouth occurences of $x_0$ in (9) are bound by the second occurence of $\mathrm{\forall }$ in (9). However, they are not bound by the first occurence of $\mathrm{\forall }$ in (9). The occurence of

$(10)\mathrm{\forall }{x}_0{G}_{\mathrm{0}}^{\mathrm{1}}(x_0)$

in (9)—as well as the occurence of (9) itself in (9)—are subformulae of (9) beginning with a quantifier. That is, both are subformula of (9) having the form

$\mathrm{\forall }\alpha \psi .$

Both contain the second third and fourth occurences of $x_0$ in (9). However, the occurence of (10) in (9) is the shortest subformula of (9) that meets these conditions. That is, the occurence of (10) in (9) is the shortest subformula of (9) that both (i) has this form and (ii) contains the third and fourth occurences of $x_0$ in (9). Thus it is the second, not the first, occurence of $\mathrm{\forall }$ in (9) that binds the third and forth occurences of $x_0$ in (9). The first occurence of $\mathrm{\forall }$ in (9) does, however, bind the first two occurences of $x_0$ in (9).

We also say that an occurence a variable $\alpha$ is bound in by a particular occurence of $\mathrm{\exists }$ if that occurence is also the first (and perhaps only) symbol in the shortest subformula of $\phi$ having the form

$\mathrm{\exists }\alpha \psi .$

Finally, we say that a variable $\alpha$ (not a particular occurence of it) is bound (or free) in a formula if the formula contains a bound (or free) occurence of $\alpha$. Thus $x_0$ is both bound and free in

$(\mathrm{\forall }{x}_0{F}_{\mathrm{0}}^{\mathrm{1}}(x_0)\to F_{\mathrm{0}}^{\mathrm{1}}(x_0))$

since this formula contains both bound and free occurences of $x_0$. In particular, the first two occurences of $x_0$ are bound and the last is free.

Sentences and formulae

A sentence is a formula with no free variables. Sentential logic had no variables at all, so all formulae of ${ℒ}_{𝒮}$ are also sentences of ${ℒ}_{𝒮}$. In predicate logic and its language ${ℒ}_{𝒫}$, however, we have formulae that are not sentences. All of (7), (8), (9), and (10) above are formulae. Of these, only (7), (9), and (10) are sentences. (8) is not a sentence because it contains free variables.

Examples

All occurences of $x_0$ in

$(11)\mathrm{\forall }{x}_0(F_{\mathrm{0}}^{\mathrm{1}}(x_0)\to G_{\mathrm{0}}^{\mathrm{2}}(x_0,y_0))$

are bound in the formula. The lone occurence of $y_0$ is free in the formula. (11) is a formula but not a sentence.

Only the first two occurences of $x_0$ in

$(12)(\mathrm{\forall }{x}_0{F}_{\mathrm{0}}^{\mathrm{1}}(x_0)\to G_{\mathrm{0}}^{\mathrm{2}}(x_0,y_0))$

are bound in the formula. The last occurence of $x_0$ and the lone occurence of $y_0$ in the formula are free in the formula. (12) is a formula but not a sentence.

All four occurences of $x_0$ in

$(13)(\mathrm{\forall }{x}_0{F}_{\mathrm{0}}^{\mathrm{1}}(x_0)\to \mathrm{\exists }{x}_0{G}_{\mathrm{0}}^{\mathrm{2}}(x_0,y_0))$

are bound. The first two are bound by the universal quantifier, the last two are bound by the existential quantifier. The lone occurence of $y_0$ in the formula is free. (13) is a formula but not a sentence.

All three occurences of $x_0$ in

$(14)(\mathrm{\forall }{x}_0{F}_{\mathrm{0}}^{\mathrm{1}}(x_0)\to \mathrm{\exists }{y}_0{G}_{\mathrm{0}}^{\mathrm{2}}(x_0,y_0))$

are bound by the universal quantifier. Both occurences of $y_0$ in the formula are bound by the existential quantifier. (14) has no free variables and so is a sentence and as well as a formula.