Database: Simple multiple variable substitution

Definition 28: We define the simple multiple variable substitution [ϕaA,bB,...,zZ]simple [\phi | a \to A, b \to B, ..., z \to Z]_\textup{simple} recursively as follows, where ϕ \phi is a statement and a,b,...,z a, b, ..., z and A,B,...,Z A, B, ..., Z are lists of variables, each having the same length.
(a) Base cases: [ϕaA,bB]simple [\phi | a \to A, b \to B]_\textup{simple} is the variable substitution [[ϕaA]bB]. \big[ [\phi | a \to A ] \big| b \to B \big]. (b) Recursion: Given variables a,b,...,y,z,A,B,...,y,Z a, b, ..., y, z, A, B, ..., y, Z such that [ϕaA,bB,...,yY]simple [\phi | a \to A, b \to B, ..., y \to Y]_\textup{simple} is known, we define [ϕaA,bB,...,yY,zZ] [\phi | a \to A, b \to B, ..., y \to Y, z \to Z] to be given by [[ϕaA,bB,...,yY]simplezZ]. \big[ [\phi | a \to A, b \to B, ..., y \to Y]_\textup{simple} \big| z \to Z \big].

This database entry builds on the following:

  1. Terminology: Recursion, structural induction
  2. Proposition/definition: Variable substitution