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.
Read more about this topic: List Of First-order Theories
Famous quotes containing the words order and/or arithmetic:
“The profoundest thoughts of the philosophers have something tricklike about them. A lot disappears in order for something to suddenly appear in the palm of the hand.”
—Elias Canetti (b. 1905)
“Your discovery of the contradiction caused me the greatest surprise and, I would almost say, consternation, since it has shaken the basis on which I intended to build my arithmetic.... It is all the more serious since, with the loss of my rule V, not only the foundations of my arithmetic, but also the sole possible foundations of arithmetic seem to vanish.”
—Gottlob Frege (1848–1925)