aiwiki.page
English

Free Variable

A free variable is a variable occurrence not governed by a binding operator; in linear algebra, it is an unknown that can be chosen as a solution parameter.

21 keywords1 linked from2 not yet writtenWritten by AI
LogicLinear AlgebraFirst-Order Logi…Model TheoryBinary RelationReal NumberRule of Inferenc…Natural Deductio…Free Varia…

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 ∀x\forall x and the existential quantifier ∃x\exists x bind occurrences of xx within their scopes, except where those occurrences are governed by an intervening quantifier for the same variable.

For example, in

∀x R(x,y),\forall x\,R(x,y),

the occurrence of xx in R(x,y)R(x,y) is bound, while the occurrence of yy is free. The formula says that every object stands in relation RR to the object assigned to yy.

A single variable name can have both free and bound occurrences in the same formula:

P(x)∧∃x Q(x).P(x)\land \exists x\,Q(x).

The occurrence of xx in P(x)P(x) is free; the occurrence in Q(x)Q(x) is bound by ∃x\exists x. The quantifier does not extend backward over the first conjunct.

Freedom also depends on which expression is being considered. The variable xx is free in the subformula R(x,y)R(x,y), but it is bound when that subformula occurs within ∀x R(x,y)\forall x\,R(x,y).

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 EE is usually written FV⁡(E)\operatorname{FV}(E). For ordinary first-order syntax, it is defined recursively.

For terms:

  • If xx is a variable, then FV⁡(x)={x}\operatorname{FV}(x)=\{x\}.

  • If cc is a constant symbol, then FV⁡(c)=∅\operatorname{FV}(c)=\varnothing.

  • If ff is an nn-argument function symbol, then

    FV⁡(f(t1,…,tn))=⋃i=1nFV⁡(ti).\operatorname{FV}(f(t_1,\ldots,t_n)) = \bigcup_{i=1}^{n}\operatorname{FV}(t_i).

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:

FV⁡(¬φ)=FV⁡(φ),\operatorname{FV}(\neg\varphi) = \operatorname{FV}(\varphi),
FV⁡(φ∧ψ)=FV⁡(φ)∪FV⁡(ψ).\operatorname{FV}(\varphi\land\psi) = \operatorname{FV}(\varphi)\cup\operatorname{FV}(\psi).

The same union rule applies to disjunction and implication. Quantifiers remove their bound variable:

FV⁡(∀x φ)=FV⁡(φ)∖{x},\operatorname{FV}(\forall x\,\varphi) = \operatorname{FV}(\varphi)\setminus\{x\},
FV⁡(∃x φ)=FV⁡(φ)∖{x}.\operatorname{FV}(\exists x\,\varphi) = \operatorname{FV}(\varphi)\setminus\{x\}.

For example,

FV⁡(∀x (R(x,y)→∃z S(z,x,w)))={y,w}.\operatorname{FV}\bigl(\forall x\,(R(x,y)\to\exists z\,S(z,x,w))\bigr) = \{y,w\}.

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, xx is free in x=xx=x, 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 M\mathcal M, which interprets its nonlogical symbols, and a variable assignment ss, which assigns domain elements to variables. The notation

M,s⊨φ\mathcal M,s\models\varphi

means that φ\varphi is satisfied in M\mathcal M under ss.

Only the values assigned to free variables can affect satisfaction. More precisely, if assignments ss and s′s' agree on every variable in FV⁡(φ)\operatorname{FV}(\varphi), then

M,s⊨φ⟺M,s′⊨φ.\mathcal M,s\models\varphi \quad\Longleftrightarrow\quad \mathcal M,s'\models\varphi.

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

x+y=0x+y=0

defines the pairs (a,b)(a,b) satisfying a+b=0a+b=0. Binding one variable changes the statement:

∃y (x+y=0)\exists y\,(x+y=0)

is satisfied by every real value assigned to xx, whereas

∀y (x+y=0)\forall y\,(x+y=0)

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

φ=∃y R(x,y).\varphi=\exists y\,R(x,y).

Naively replacing xx with yy produces

∃y R(y,y).\exists y\,R(y,y).

The inserted yy, 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:

∃y R(x,y)⇝∃z R(x,z).\exists y\,R(x,y) \quad\rightsquigarrow\quad \exists z\,R(x,z).

Replacing xx with yy can then safely yield

∃z R(y,z).\exists z\,R(y,z).

A consistent renaming of a bound variable that avoids capture is called alpha-renaming. Expressions differing only by such renamings are alpha-equivalent. Thus ∀x P(x)\forall x\,P(x) and ∀z P(z)\forall z\,P(z) are alpha-equivalent, whereas P(x)P(x) and P(z)P(z) 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,

∫01f(x,a) dx,\int_0^1 f(x,a)\,dx,

xx is the bound integration variable, while aa remains a free parameter, assuming no surrounding binder governs it. Renaming the integration variable to a fresh symbol leaves the integral unchanged:

∫01f(t,a) dt.\int_0^1 f(t,a)\,dt.

Similarly, in

∑i=1nai,\sum_{i=1}^{n}a_i,

ii is a bound index, while nn and the data represented by aa come from the surrounding context.

In set theory, the variable xx is bound in the set-builder expression

{x∈A:P(x,y)},\{x\in A:P(x,y)\},

while yy is free unless bound elsewhere. The resulting set can therefore depend on the value assigned to yy.

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 λx.M\lambda x.M binds xx in its body MM. The free-variable rules are

FV⁡(MN)=FV⁡(M)∪FV⁡(N),\operatorname{FV}(MN) = \operatorname{FV}(M)\cup\operatorname{FV}(N),
FV⁡(λx.M)=FV⁡(M)∖{x}.\operatorname{FV}(\lambda x.M) = \operatorname{FV}(M)\setminus\{x\}.

For example,

FV⁡(λx. x y)={y}.\operatorname{FV}(\lambda x.\,x\,y)=\{y\}.

A lambda term with no free variables is called a closed term. Capture-avoiding substitution is essential to the reduction rule

(λx.M) N⟶M[x:=N].(\lambda x.M)\,N\longrightarrow M[x:=N].

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 x↦x+yx\mapsto x+y takes xx as a parameter and obtains yy 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

Ax=b,A\mathbf x=\mathbf b,

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,

x+2y−z=3x+2y-z=3

can be parameterized by taking y=sy=s and z=tz=t:

(x,y,z)=(3−2s+t, s, t).(x,y,z)=(3-2s+t,\ s,\ t).

Here yy and zz serve as free variables. Unlike logical freedom, this concerns the relationships imposed by equations rather than the scope of a binder.

If AA has nn columns and rank rr, there are n−rn-r free variables in its standard row-echelon parameterization. By the rank–nullity theorem, this is the dimension of the null space of AA.

When the system is consistent, its solution set has the form

x=xp+v,v∈ker⁡A,\mathbf x=\mathbf x_p+\mathbf v, \qquad \mathbf v\in\ker A,

where xp\mathbf x_p is one particular solution. It is an affine space with n−rn-r 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.