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 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.
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 be a term (in a first-order language), then is
-
•
if is a variable , then is
-
•
if is , where is a function symbol of arity , and each is a term, then is the union of all the .
Free Variables
Now, let be a formula. Then the set of free variables of is now defined inductively as follows:
-
•
if is , then is ,
-
•
if is , then is
-
•
if is , then is
-
•
if is , then is , and
-
•
if is , then is .
If , 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. 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 be a formula. Then the set of bound variables of
-
•
if is an atomic formula, then is , the empty set,
-
•
if is , then is
-
•
if is , then is , and
-
•
if is , then is .
Thus, a variable is bound in if and only if is a subformula of for some formula .
The set of all variables occurring in a formula is denoted , and is .
Note that it is possible for a variable to be both free and bound. In other words, and are not necessarily disjoint. 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 .
As a result of the lemma above, we see that every formula is logically equivalent to a formula such that .
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 |