Substitution in first-order languages

1. Introduction

This web page discusses syntactical aspects of substitution in first-order logic. In particular, the tricky definition of substitution itself is given and we will see when that substitution is valid. All these details are technical. They behave exactly as one would naïvely hope (though the details are more awkward to write down than one might expect), and in particular all these notions are computable, i.e. computable on a computer, or representable in a formal system like a Post system. Readers who can take such details on trust need not read further. Only those who want to see the gory details need read on.

2. Substitution

We want to define and investigate the effect of substituting terms t 1 , , t k for variables v 1 , , v k in a term or formula. The work here will be entirely syntactical (i.e. manipulations of strings of symbols without meaning attached) but looking ahead to further work we will take care to ensure that our substitutions are potentially meaningful (i.e. can at a later stage be given meaning).

We fix a first order language L with variables from VAR L = { u , v , w , } and terms TERM L .

In its simplest form a substitution is a function s : V TERM L where V = dom ( s ) is a finite set of variables. The idea is that we should substitute each v V with the term s ( v ) . This is turn gives more complex substitition functions s ( t ) and s ( ϕ ) where t is a term and ϕ is a formula of L . Most of the inductive definition of this extension to terms and formulas is given recursively by the following.

This is an inductive definition on terms and formulas, and as such relies on the Unique Readability Theorem for terms and formulas.

The only clauses missing from the above are those for s ( v ) = v if v dom ( s ) and for the quantifiers and . But these cause difficulties: some substitutions are invalid i.e. they result in unacceptable introduction of new variables in the scope of an existing quantifier. To resolve this problem we must specify when substitutions are valid, and this involves a slightly more sophisticated idea of substitution.

From now on, we say that a substitution s is a function s : V TERM L with domain V = dom ( s ) and a finite set of forbidden variables, ( s ) . Variables in ( s ) are not allowed in the substituted output, though they can be present in unsubstituted output.

The remaining clauses of the definition of substitution will now be given, starting with the substitution of a variable for a term.

Finally, we can give the rules for substitution of formulas involving quantifiers. There are two cases. In the following, Q is either or .

The point is here that a quantified variable must never be substituted, since it already has an intended meaning (ranging over all or some elements of a L -structure). That is why in the first case the domain of the substitution is altered to remove the variable v . Furthermore, in the scope of the quantifier terms should not be introduced by substitution if they involve the variable being quantified over. That is why the forbidden variable set is made bigger.

In the sequel, when defining a substitution s we shall normally just give the domain of s and the value s ( v ) for each variable v dom ( s ) . If ( s ) is not specified it will be assumed to be empty.