Non-constructive rules of inference

For some theoretical purposes, generalized deductive systems (or, ‘semi-formal’ systems) are considered, having rules with an infinite number of premises. The best-known of these rules is the ‘ω-rule’, or rule of infinite induction. This rule allows the inference of ∀nΦ(n) from the infinitely many premises Φ(0), Φ(1),… that result from replacing the numerical variable n in Φ(n) with the numeral for each natural number. About 1930, in part as a response to Gödel’s demonstration that no formal deductive system had as theorems all and only the true formulas of arithmetic, several writers (most notably, Carnap) suggested considering the semi-formal systems obtained, from some formulation of arithmetic, by adding this rule. Since no finite notation can provide terms for all sets of natural numbers, no comparable rule can be formulated for higher-order arithmetic. In effect, the ω-rule is valid just in case the relevant quantifier can be interpreted substitutionally; looked at from the other side, the validity of some analogue of the ω-rule is the essential mathematical characteristic of substitutional quantification.