One of the most confusing, but also most important, parts of first order logic is the distinction between free and bound variables, or, more properly, between free and bound occurences of a variable in an expression. This is easier to understand in a formal system like the one we will use for elementary arithmetic than in first order logic so we’ll consider it there first.
Consider the expression \[ l = m + n . \] This could be true or false, depending on the values of \({ l }\), \({ m }\) and \({ n }\). Now consider the expression \[ [ ∃ n . ( l = m + n ) ] \] which is normally read “there exists an \({ n }\) such that \({ l }\) equals \({ m }\) plus \({ n }\)”. This could be true or false depending on the values of \({ l }\) and \({ m }\). You could substitute actual natural numbers in for \({ l }\) and \({ m }\) and sensibly ask whether this is a true statement for those values. In the version of elementary arithmetic we’ll consider the variables represent natural numbers, i.e. non-negative integers so this statement will in fact be true if \({ l ≥ m }\) and false if \({ l < m }\). What the value of the expression doesn’t depend on is \({ n }\). You are not allowed to substitute in a value for \({ n }\). The result of doing so isn’t true or false but just grammatically incorrect. \({ n }\) is what’s called a bound variable in this expression, while \({ l }\) and \({ m }\) are free variables. In the original expression all three variables were free.
We can add another quantifier. \[ \{ ∀ l . [ ∃ n . ( l = m + n ) ] \} \] is normally read “for all \({ l }\) there exists an \({ n }\) such that \({ l }\) equals \({ m }\) plus \({ n }\)”. The value of the expression now depends only on \({ l }\). In fact it’s true if \({ m }\) is zero and is false if \({ m }\) is positive. In this expression \({ l }\) and \({ n }\) are bound while \({ m }\) is free.
We can add one final quantifier. \[ ( ∃ m . \{ ∀ l . [ ∃ n . ( l = m + n ) ] \} ) \] Now all the variables are bound. It would not make sense to substitute for any of them. This statement is either true or false, not depending on anything. In fact it is true, since zero is an example of such an \({ m }\). In fact its the only example.
It’s important to note that we can only talk about whether a variable is free or bound within a particular expression. Each of the first three expressions above forms part of the expression which follows it and there is a variable which is free in the subexpression but bound in the whole expression. More subtly the same variable could be free and bound in different places in the same expression. This doesn’t happen in any of the expressions above and you should never write down such an expression because they are very confusing. I promise not to either. But it’s hard to write down grammar rules which forbid this so the standard practice is to allow it but then not do it. Because of this though we have to talk about free and bounded occurrences of a variable in an expression rather than free and bound variables, since a variable could potentially occur freely in one place and bound in another within the same expression.
The example above was taken from elementary arithmetic. The corresponding example in first order logic would be the four expressions \[ ( f x y z ) , \] \[ [ ∃ z . ( f x y z ) ] , \] \[ \{ ∀ x . [ ∃ z . ( f x y z ) ] \} , \] and \[ ( ∃ y . \{ ∀ x . [ ∃ z . ( f x y z ) ] \} ) . \] The particular predicate saying that the first argument is the sum of the last two has been replaced by the generic symbol \({ f }\). I’ve also renamed the variables to put them within the range specified by the grammar. Whether the last of these statements is true or false depends on the meaning of \({ f }\). If \({ f }\) is the sum predicate we considered earlier then the statement is true but for other choices of \({ f }\) it might be false. This is a question of interpretation, which we’ll discuss later.
The variable \({ x }\) has a free occurrence, but no bound occurrences, in the first and second expressions above and has a bound occurrence, but no free occurrences, in the third and fourth. \({ y }\) has free occurrences in the first three and a bound occurrence in the fourth. \({ z }\) occurs freely in the first and bound in the last three.
The precise rules are not difficult to state. In an atomic expression all variables are free. Whenever we build an expression from a quantifier, a variable, and an expression all occurrences of that variable in the combined expression are bound. Occurrences of other variables remain free or bound as they were in the original expression. Combining expressions using logical operators has no effect. Whatever occurrences were free in the old expressions remain free in the new one and whatever occurrences were bound remain bound.
An expression is called “open” if there is a free occurrence of some variable in it and is called “closed” if all occurrences are bound. If we have a particular interpretation where the variables are assumed to belong to a particular set and assigned particular relations to the predicates then it makes sense to ask whether a closed expression is true. For an open expression we can only ask that question after we’ve assigned particular values to the variables which occur freely in the expression.