|
In the entry first-order language, 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 if and only if it is not within the “scope” of a quantifier. For instance, occurs free in if and only if it occurs in it as a symbol, and no subformula of is of the form
. Here the after the is to be taken literally : it is and no other symbol.
The set
of free variables of is defined by well-founded induction on the construction of formulas. First we define , where is a term, to be the set or all variables occurring in , and then :
When for some , the set
is not empty, then it is customary to write as
, in order to stress the fact that there are some free variables left in , and that those free variables are among
. When
appear free in , 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 . If
, then is called a sentence.
If a variable never occurs free in (and occurs as a symbol), then we say the variable is bound. Bound variables can be inductively defined as well: let be a formula, then we define the set
of bound variables as follows:
Thus, a variable is bound if and only if
or
is a subformula of for some
Note that it is possible for a variable to be both free and bound. For example, consider the following formula of the lenguage
of ring theory :
Then
and
: the variable 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
, or
, and is a variable not occurring in , then
, where is the formula obtained from by replacing every free occurrence of by .
|