Proposition 18: Let x be a variable, and \phi a statement.
(a) If x is among the variables a, b, ..., z , then x occurs in the generalized existence statement \exists a, b, ..., z \phi .
(b) If x occurs in \phi then it occurs in \exists ab, b, ..., z \phi .

Proof: (a): We will argue by structural induction over the recursive definition of generalized existence statements.

Base cases: If x is among the variables a and b , then x is identical to at least one of these variables. If x is identical to a , then x occurs in \exists a \exists b \phi by (c) in the definition of occurrence. If x is identical to b then x occurs in \exists b \phi by (c) again, and hence in \exists a \exists b \phi by either (c) or (f) in the definition of occurrence. But \exists a, b \phi is precisely an abbreviation for \exists a \exists b \phi .

Inductive step: We take as the induction hypothesis that the desired result is evident for variables b, c, ..., z , and want to show from this that it is evident for a, b, c, ..., z . If x is among a, b, ..., y, z , then either x is identical to a or it is among b, c, ..., z . In the former case, x occurs in \exists a \exists b, c, ..., z \phi by (c) in the definition of occurrence. In the latter case, x occurs in \exists b, c, ..., z \phi by the induction hypothesis, and hence in \exists a \exists b, c, ..., z \phi by (f) in the definition of occurrence. But \exists a, b, c, ..., z \phi is short for \exists a \exists b, c, ..., z \phi . \square