Free variables

1. Introduction

This web page gives the official definition of what it means for a variable $v$ to be free in a formula $ϕ$ of a first-order language $L$ .

2. The definition

The definition of what it means for $v$ to be free in $ϕ$ or term $t$ of a first-order language $L$ is y induction on terms and formulas. We shall specify what it means for $v$ to be free in each of the constructions of terms and formulas, and assume that it is already understood what $v$ is free in $ϕ$ [or term $t$ ] is already understood for all subformulas and subterms.

Most syntactical definitions in first order logic are of this kind: such definitions implicitly require the Theorem on Unique Readability, which says that for any term or formula there is a unique way of reading it as built from subformulas and subterms, and therefore exactly one of our inductive clauses applies.

Fix a first order language $L$ and variable $v$ of $L$ . Here are the clauses defining what it means for $v$ to be free in $ϕ$ .

$v$ is free in $v$
$v$ is not free in $c$ for a constant symbol $c$
$v$ is free in $F (t_{1}, \dots, t_{k})$ (where $F$ is a $k$ -ary function symbol) if and only if $v$ is free in at least one of $t_{1}, \dots, t_{k}$
$v$ is not free in $⊤$ nor in $⊥$
$v$ is free in $(t_{1} = t_{2})$ if and only if $v$ is free in at least one of $t_{1}, t_{2}$
$v$ is free in $R (t_{1}, \dots, t_{k})$ (where $R$ is a $k$ -ary relation symbol) if and only if $v$ is free in at least one of $t_{1}, \dots, t_{k}$
$v$ is free in $\neg ϕ$ if and only if $v$ is free in $ϕ$
$v$ is free in $(ϕ_{1} \lor ϕ_{2})$ if and only if $v$ is free in at least one of $ϕ_{1}, ϕ_{2}$
$v$ is free in $(ϕ_{1} \land ϕ_{2})$ if and only if $v$ is free in at least one of $ϕ_{1}, ϕ_{2}$
$v$ is free in $(ϕ_{1} \to ϕ_{2})$ if and only if $v$ is free in at least one of $ϕ_{1}, ϕ_{2}$
$v$ is free in $\forall w ϕ$ if and only if $v$ is not the same variable as $w$ and $v$ is free in $ϕ$
$v$ is free in $w ϕ$ if and only if $v$ is not the same variable as $w$ and $v$ is free in $ϕ$

That's it. You should be able to check that this defines $v$ is free in $ϕ$ for all $ϕ$ . Readers with some programming experience will recognise the definition just given as a recursive definition, and will easily be able to write a subroutine or function in their favourite language that computes whether $v$ is free in $ϕ$ . In other words, this notion is (rather easily) computable.

Exercise.

Show that $v$ is not free in $ϕ$ is equivalent to the statement that Each occurence of $v$ in $ϕ$ is in the scope of a quantifier $\forall v$ or $v$ .

It is common to write a formula $ϕ$ or term $t$ with arguments displayed as $ϕ (v_{1}, \dots, v_{k})$ or $t (v_{1}, \dots, v_{k})$ . When so-doing it is important to list all of the variables that occur free in $ϕ$ or $t$ . It is always OK to include additional variables, however, and this sometimes saves a lot of writing. The reason for this is that there is little difference between $ϕ (v_{1}, v_{2})$ and $ϕ (v_{1}, v_{2}) \land (v_{3} = v_{3})$ so it is OK to write the former as $ϕ (v_{1}, v_{2}, v_{3})$ . But it would be a mistake to write $ϕ (v_{1}, v_{2}) \land (v_{3} = v_{3})$ as $ϕ (v_{1}, v_{2})$ as the $v_{3}$ does play a role and must not be forgotten.

Definition.

A closed term is a term which has no free variables (and hence has no variables at all). A sentence is a formula which has no free variables. Sentences are sometimes called closed formulas.