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:
“This event advertises me that there is such a fact as death,the possibility of a mans dying. It seems as if no man had ever died in America before; for in order to die you must first have lived.”
—Henry David Thoreau (18171862)
“I hope I may claim in the present work to have made it probable that the laws of arithmetic are analytic judgments and consequently a priori. Arithmetic thus becomes simply a development of logic, and every proposition of arithmetic a law of logic, albeit a derivative one. To apply arithmetic in the physical sciences is to bring logic to bear on observed facts; calculation becomes deduction.”
—Gottlob Frege (18481925)