Stronger Systems
Much as we have defined Σn and Πn (or, more accurately, Σ0n and Π0n) formulae, we can define Σ1n and Π1n formulae in the following way: a Δ10 (or Σ10 or Π10) formula is just an arithmetical formula, and a Σ1n, respectively Π1n, formula is obtained by adding existential, respectively universal, class quantifiers in front of a Π1n−1, respectively Σ1n−1.
It is not too hard to see that over a not too weak system, any formula of second-order arithmetic is equivalent to a Σ1n or Π1n formula for all large enough n. The system Π11-comprehension is the system consisting of the basic axioms, plus the ordinary second-order induction axiom and the comprehension axiom for every Π11 formula φ. It is an easy exercise to show that this is actually equivalent to Σ11-comprehension (on the other hand, Δ11-comprehension, defined by the same trick as introduced earlier for Δ01 comprehension, is actually weaker).
Read more about this topic: Second-order Arithmetic
Famous quotes containing the words stronger and/or systems:
“It is the nature of an hypothesis, when once a man has conceived it, that it assimulates every thing to itself as proper nourishment; and, from the first moment of your begetting it, it generally grows the stronger by every thing you see, hear, read, or understand. This is of great use.”
—Laurence Sterne (1713–1768)
“People stress the violence. That’s the smallest part of it. Football is brutal only from a distance. In the middle of it there’s a calm, a tranquility. The players accept pain. There’s a sense of order even at the end of a running play with bodies stewn everywhere. When the systems interlock, there’s a satisfaction to the game that can’t be duplicated. There’s a harmony.”
—Don Delillo (b. 1926)