A free variable is a variable that is not bound by an operator within the expression under consideration. In logic, a variable occurrence is free when it lies outside the scope of a quantifier or other operator that binds that variable. Its interpretation is supplied by an assignment or a surrounding context. In linear algebra, the term has a related but distinct meaning: a free variable is an unknown that can be chosen independently when parameterizing the solutions of a consistent linear system. Freedom is therefore relative to an expression, a binding context, or a system of constraints—not an intrinsic property of a variable name.
Free and bound occurrences
The distinction between free and bound variables is most precisely a distinction between occurrences of variables. In first-order logic, the universal quantifier and the existential quantifier bind occurrences of within their scopes, except where those occurrences are governed by an intervening quantifier for the same variable.
For example, in
the occurrence of in is bound, while the occurrence of is free. The formula says that every object stands in relation to the object assigned to .
A single variable name can have both free and bound occurrences in the same formula:
The occurrence of in is free; the occurrence in is bound by . The quantifier does not extend backward over the first conjunct.
Freedom also depends on which expression is being considered. The variable is free in the subformula , but it is bound when that subformula occurs within .
A formula with no free variables is called a sentence or closed formula. A formula with at least one free variable is commonly called an open formula. “Closed” does not mean “true”: a closed formula may be true or false in a given interpretation.
Formal definition
The set of free variables of an expression is usually written . For ordinary first-order syntax, it is defined recursively.
For terms:
If is a variable, then .
If is a constant symbol, then .
If is an -argument function symbol, then
For formulas, the free variables of an atomic formula are the variables occurring in its argument terms. Negation preserves the set of free variables, and binary logical connectives take unions:
The same union rule applies to disjunction and implication. Quantifiers remove their bound variable:
For example,
These rules describe syntactic freedom. A variable can occur freely even when changing its assigned value never changes the formula’s truth value. For example, is free in , although this formula is true under every assignment in ordinary first-order logic with equality.
Interpretation and truth
In model theory, evaluating a formula generally requires both a structure , which interprets its nonlogical symbols, and a variable assignment , which assigns domain elements to variables. The notation
means that is satisfied in under .
Only the values assigned to free variables can affect satisfaction. More precisely, if assignments and agree on every variable in , then
A sentence therefore has a truth value in a structure independently of the variable assignment.
An open formula can describe a relation or, more generally, a set of tuples. Over the real numbers, the formula
defines the pairs satisfying . Binding one variable changes the statement:
is satisfied by every real value assigned to , whereas
is satisfied by none.
Free variables are also relevant to restrictions on logical rules of inference. In natural deduction, universal introduction requires conditions ensuring that the generalized variable does not depend on an undischarged assumption. Without such conditions, a claim about a particular assigned object could incorrectly become a claim about every object.
Substitution and variable capture
Substitution replaces free occurrences of a variable with a term. It must preserve the distinction between free and bound occurrences.
Suppose
Naively replacing with produces
The inserted , intended to remain free, has instead become bound. This is variable capture, and it generally changes the intended meaning.
Capture-avoiding substitution first renames the bound variable to a fresh name:
Replacing with can then safely yield
A consistent renaming of a bound variable that avoids capture is called alpha-renaming. Expressions differing only by such renamings are alpha-equivalent. Thus and are alpha-equivalent, whereas and generally are not: their free variables refer to potentially different assigned objects.
Binding in mathematical notation
Binding occurs throughout mathematics, not only in quantified formulas. In a definite integral,
is the bound integration variable, while remains a free parameter, assuming no surrounding binder governs it. Renaming the integration variable to a fresh symbol leaves the integral unchanged:
Similarly, in
is a bound index, while and the data represented by come from the surrounding context.
In set theory, the variable is bound in the set-builder expression
while is free unless bound elsewhere. The resulting set can therefore depend on the value assigned to .
These examples show why a bound variable is often called a dummy variable: its name can be changed without changing the object denoted, provided the renaming respects scope and avoids capture.
Lambda calculus and programming languages
In lambda calculus, an abstraction binds in its body . The free-variable rules are
For example,
A lambda term with no free variables is called a closed term. Capture-avoiding substitution is essential to the reduction rule
In programming languages, a variable may be free relative to a function body while being bound in an enclosing scope. Under lexical scoping, a function such as an anonymous function representing takes as a parameter and obtains from its enclosing environment. A closure associates executable function code with the environment needed for such references.
Thus, “free variable” does not necessarily mean “undefined variable.” The variable may have a valid binding outside the expression currently being examined.
Free variables in linear systems
In a system of linear equations
free variables are coordinates not associated with pivot columns after Gaussian elimination has put the coefficient matrix into row-echelon form. For a consistent system, these variables can be chosen arbitrarily from the underlying field, and the pivot variables are then determined by them.
For example,
can be parameterized by taking and :
Here and serve as free variables. Unlike logical freedom, this concerns the relationships imposed by equations rather than the scope of a binder.
If has columns and rank , there are free variables in its standard row-echelon parameterization. By the rank–nullity theorem, this is the dimension of the null space of .
When the system is consistent, its solution set has the form
where is one particular solution. It is an affine space with independent parameters.
The choice of free coordinates can change if the unknowns are reordered or another parameterization is used; their number does not. Moreover, an inconsistent system has no solution, even if its coefficient matrix has nonpivot columns. In that case, nonpivot unknowns do not parameterize any solutions.