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:
“It is a monstrous thing that I will say, but I will say it all the same: I find in many things more restraint and order in my morals than in my opinions, and my lust less depraved than my reason.”
—Michel de Montaigne (1533–1592)
“‘Tis no extravagant arithmetic to say, that for every ten jokes,—thou hast got an hundred enemies; and till thou hast gone on, and raised a swarm of wasps about thine ears, and art half stung to death by them, thou wilt never be convinced it is so.”
—Laurence Sterne (1713–1768)