well-founded induction on formulas
Let be a first-order language. The formulas of are built by a finite application of the rules of construction. This says that the relation
defined on formulas by if and only if is a subformula of is a well-founded relation. Therefore, we can formulate a principle of induction
for formulas as follows : suppose is a property defined on formulas, then is true for every formula of if and only if
- 1.
is true for the atomic formulas;
- 2.
for every formula , if is true for every subformula of , then is true for .