# free and bound variables

In the entry first-order language (http://planetmath.org/TermsAndFormulas), I have mentioned the use of variables without mentioning what variables really are. A variable is a symbol that is supposed to range over the universe of discourse. Unlike a constant, it has no fixed value.

There are two ways in which a variable can occur in a formula: free or bound. Informally, a variable is said to occur free in a formula $\varphi$ if and only if it is not within the “scope” of a quantifier. For instance, $x$ occurs free in $\varphi$ if and only if it occurs in it as a symbol, and no subformula of $\varphi$ is of the form $\exists x.\psi$. Here the $x$ after the $\exists$ is to be taken literally : it is $x$ and no other symbol.

## Variables in Terms

To formally define free (resp. bound) variables in a formula, we start by defining variables occurring in terms, which can be easily done inductively: let ${t}$ be a term (in a first-order language), then $\operatorname{Var}(t)$ is

• if $t$ is a variable $v$, then $\operatorname{Var}(t)$ is $\{v\}$

• if $t$ is $f(t_{1},\ldots,t_{n})$, where $f$ is a function symbol of arity $n$, and each $t_{i}$ is a term, then $\operatorname{Var}(t)$ is the union of all the $\operatorname{Var}(t_{i})$.

## Free Variables

Now, let $\varphi$ be a formula. Then the set $\operatorname{FV}(\varphi)$ of free variables of $\varphi$ is now defined inductively as follows:

• if $\varphi$ is $t_{1}=t_{2}$, then $\operatorname{FV}(\varphi)$ is $\operatorname{Var}(t_{1})\cup\operatorname{Var}(t_{2})$,

• if $\varphi$ is $R(t_{1},\ldots,t_{n})$, then $\operatorname{FV}(\varphi)$ is $\operatorname{Var}(t_{1})\cup\cdots\cup\operatorname{Var}(t_{n})$

• if $\varphi$ is $\neg\psi$, then $\operatorname{FV}(\varphi)$ is $\operatorname{FV}(\psi)$

• if $\varphi$ is $\psi\vee\sigma$, then $\operatorname{FV}(\varphi)$ is $\operatorname{FV}(\psi)\cup\operatorname{FV}(\sigma)$, and

• if $\varphi$ is $\exists x\psi$, then $\operatorname{FV}(\varphi)$ is $\operatorname{FV}(\psi)-\{x\}$.

If $\operatorname{FV}(\varphi)\neq\varnothing$, it is customary to write $\varphi$ as $\varphi(x_{1},\ldots,x_{n}),$ in order to stress the fact that there are some free variables left in $\varphi$, and that those free variables are among $x_{1},\ldots,x_{n}$. When $x_{1},\ldots,x_{n}$ appear free in $\varphi$, then they are considered as place-holders, and it is understood that we will have to supply “values” for them, when we want to determine the truth of $\varphi$. If $\operatorname{FV}(\varphi)=\varnothing$, then $\varphi$ is called a . Another name for a sentence is a closed formula. A formula that is not closed is said to be open.

## Bound Variables

Bound variables in formulas are inductively defined as well: let $\varphi$ be a formula. Then the set $\operatorname{BV}(\varphi)$ of bound variables of $\varphi$

• if $\varphi$ is an atomic formula, then $\operatorname{BV}(\varphi)$ is $\varnothing$, the empty set,

• if $\varphi$ is $\neg\psi$, then $\operatorname{BV}(\varphi)$ is $\operatorname{BV}(\psi)$

• if $\varphi$ is $\psi\vee\sigma$, then $\operatorname{BV}(\varphi)$ is $\operatorname{BV}(\psi)\cup\operatorname{BV}(\sigma)$, and

• if $\varphi$ is $\exists x\psi$, then $\operatorname{BV}(\varphi)$ is $\operatorname{BV}(\psi)\cup\{x\}$.

Thus, a variable $x$ is bound in $\varphi$ if and only if $\exists x\psi$ is a subformula of $\varphi$ for some formula $\psi$.

The set of all variables occurring in a formula $\varphi$ is denoted $\operatorname{Var}(\varphi)$, and is $\operatorname{FV}(\varphi)\cup\operatorname{BV}(\varphi)$.

Note that it is possible for a variable to be both free and bound. In other words, $\operatorname{FV}(\varphi)$ and $\operatorname{BV}(\varphi)$ are not necessarily disjoint. For example, consider the following formula $\varphi$ of the lenguage $\{+,\cdot,0,1\}$ of ring theory :

 $x+1=0\wedge\exists x(x+y=1)$

Then $\operatorname{FV}(\varphi)=\{x,y\}$ and $\operatorname{BV}(\varphi)=\{x\}$: the variable $x$ occurs both free and bound. However, the following lemma tells us that we can always avoid this situation :

Lemma 1. It is possible to rename the bound variables without affecting the truth of a formula. In other words, if $\varphi=\exists x(\psi)$, or $\forall x(\psi)$, and $z$ is a variable not occurring in $\psi$, then $\vdash\varphi\Leftrightarrow\exists z(\psi[z/x])$, where $\psi[z/x]$ is the formula obtained from $\psi$ by replacing every free occurrence of $x$ by $z$.

As a result of the lemma above, we see that every formula is logically equivalent to a formula $\varphi$ such that $\operatorname{FV}(\varphi)\cap\operatorname{BV}(\varphi)=\varnothing$.

 Title free and bound variables Canonical name FreeAndBoundVariables Date of creation 2013-03-22 12:42:57 Last modified on 2013-03-22 12:42:57 Owner CWoo (3771) Last modified by CWoo (3771) Numerical id 24 Author CWoo (3771) Entry type Definition Classification msc 03C07 Classification msc 03B10 Synonym occur free Synonym occur bound Synonym closed Synonym open Related topic Substitutability Defines free variable Defines bound variable Defines free occurrence Defines bound occurrence Defines occurs free Defines occurs bound