List of First-order Theories - Second Order Arithmetic

Second Order Arithmetic

Second-order arithmetic can refer to a first order theory (in spite of the name) with two types of variables, thought of as varying over integers and subsets of the integers. (There is also a theory of arithmetic in second order logic that is called second order arithmetic. It has only one model, unlike the corresponding theory in first order logic, which is incomplete.) The signature will typically be the signature 0, S, +, × of arithmetic, together with a membership relation ∈ between integers and subsets (though there are numerous minor variations). The axioms are those of Robinson arithmetic, together with axiom schemes of induction and comprehension.

There are many different subtheories of second order arithmetic that differ in which formulas are allowed in the induction and comprehension schemes. In order of increasing strength, five of the most common systems are

• , Recursive Comprehension
• , Weak König's lemma
• , Arithmetical comprehension
• , Arithmetical Transfinite Recursion
• , comprehension

These are defined in detail in the articles on second order arithmetic and reverse mathematics.