Subsystems Second-order arithmetic

1 subsystems

1.1 arithmetical comprehension
1.2 arithmetical hierarchy formulas
1.3 recursive comprehension
1.4 weaker systems
1.5 stronger systems

subsystems

there many named subsystems of second-order arithmetic.

a subscript 0 in name of subsystem indicates includes restricted portion of full second-order induction scheme (friedman 1976). such restriction lowers proof-theoretic strength of system significantly. example, system aca0 described below equiconsistent peano arithmetic. corresponding theory aca, consisting of aca0 plus full second-order induction scheme, stronger peano arithmetic.

arithmetical comprehension

many of well-studied subsystems related closure properties of models. example, can shown every ω-model of full second-order arithmetic closed under turing jump, not every ω-model closed under turing jump model of full second-order arithmetic. subsystem aca0 includes enough axioms capture notion of closure under turing jump.

aca0 defined theory consisting of basic axioms, arithmetical comprehension axiom scheme (in other words comprehension axiom every arithmetical formula φ) , ordinary second-order induction axiom. equivalent include entire arithmetical induction axiom scheme, in other words include induction axiom every arithmetical formula φ.

it can shown collection s of subsets of ω determines ω-model of aca0 if , if s closed under turing jump, turing reducibility, , turing join (simpson 2009, pp. 311–313).

the subscript 0 in aca0 indicates not every instance of induction axiom scheme included subsystem. makes no difference ω-models, automatically satisfy every instance of induction axiom. of importance, however, in study of non-ω-models. system consisting of aca0 plus induction formulas called aca no subscript.

the system aca0 conservative extension of first-order arithmetic (or first-order peano axioms), defined basic axioms, plus first order induction axiom scheme (for formulas φ involving no class variables @ all, bound or otherwise), in language of first order arithmetic (which not permit class variables @ all). in particular has same proof-theoretic ordinal ε0 first-order arithmetic, owing limited induction schema.

the arithmetical hierarchy formulas

a formula called bounded arithmetical, or Δ0, when quantifiers of form ∀n<t or ∃n<t (where n individual variable being quantified , t individual term), where

∀
n
<
t
(
⋯
)


{\displaystyle \forall n<t(\cdots )}

stands for

∀
n
(
n
<
t
→
⋯
)


{\displaystyle \forall n(n<t\rightarrow \cdots )}

and

∃
n
<
t
(
⋯
)


{\displaystyle \exists n<t(\cdots )}

stands for

∃
n
(
n
<
t
∧
⋯
)


{\displaystyle \exists n(n<t\land \cdots )}

.

a formula called Σ1 (or Σ1), respectively Π1 (or Π1) when of form ∃m•(φ), respectively ∀m•(φ) φ bounded arithmetical formula , m individual variable (that free in φ). more generally, formula called Σn, respectively Πn when obtained adding existential, respectively universal, individual quantifiers Πn−1, respectively Σn−1 formula (and Σ0 , Π0 equivalent Δ0). construction, these formulas arithmetical (no class variables ever bound) and, in fact, putting formula in skolem prenex form 1 can see every arithmetical formula equivalent Σn or Πn formula large enough n.

recursive comprehension

the subsystem rca0 weaker system aca0 , used base system in reverse mathematics. consists of: basic axioms, Σ1 induction scheme, , Δ1 comprehension scheme. former term clear: Σ1 induction scheme induction axiom every Σ1 formula φ. term “Δ1 comprehension” more complex, because there no such thing Δ1 formula. Δ1 comprehension scheme instead asserts comprehension axiom every Σ1 formula equivalent Π1 formula. scheme includes, every Σ1 formula φ , every Π1 formula ψ, axiom:

∀
m
∀
x
(
(
∀
n
(
φ
(
n
)
↔
ψ
(
n
)
)
)
→
∃
z
∀
n
(
n
∈
z
↔
φ
(
n
)
)
)


{\displaystyle \forall m\forall x((\forall n(\varphi (n)\leftrightarrow \psi (n)))\rightarrow \exists z\forall n(n\in z\leftrightarrow \varphi (n)))}

the set of first-order consequences of rca0 same of subsystem iΣ1 of peano arithmetic in induction restricted Σ1 formulas. in turn, iΣ1 conservative on primitive recursive arithmetic (pra)




Π

2


0




{\displaystyle \pi _{2}^{0}}

sentences. moreover, proof-theoretic ordinal of





r
c
a


0




{\displaystyle \mathrm {rca} _{0}}

ω, same of pra.

it can seen collection s of subsets of ω determines ω-model of rca0 if , if s closed under turing reducibility , turing join. in particular, collection of computable subsets of ω gives ω-model of rca0. motivation behind name of system—if set can proved exist using rca0, set recursive (i.e. computable).

weaker systems

sometimes weaker system rca0 desired. 1 such system defined follows: 1 must first augment language of arithmetic exponential function (in stronger systems exponential can defined in terms of addition , multiplication usual trick, when system becomes weak no longer possible) , basic axioms obvious axioms defining exponentiation inductively multiplication; system consists of (enriched) basic axioms, plus Δ1 comprehension, plus Δ0 induction.

stronger systems

over aca0, each formula of second-order arithmetic equivalent Σn or Πn formula large enough n. system Π1-comprehension system consisting of basic axioms, plus ordinary second-order induction axiom , comprehension axiom every Π1 formula φ. equivalent Σ1-comprehension (on other hand, Δ1-comprehension.