Definition Second-order arithmetic

1 definition

1.1 syntax
1.2 semantics
1.3 axioms

1.3.1 basic
1.3.2 induction , comprehension schema


1.4 full system

definition
syntax

the language of second-order arithmetic two-sorted. first sort of terms , in particular variables, denoted lower case letters, consists of individuals, intended interpretation natural numbers. other sort of variables, variously called “set variables,” “class variables,” or “predicates” denoted upper-case letters. refer classes/predicates/properties of individuals, , can thought of sets of natural numbers. both individuals , set variables can quantified universally or existentially. formula no bound set variables (that is, no quantifiers on set variables) called arithmetical. arithmetical formula may have free set variables , bound individual variables.

individual terms formed constant 0, unary function s (the successor function), , binary operations + , · (addition , multiplication). successor function adds 1 input. relations = (equality) , < (comparison of natural numbers) relate 2 individuals, whereas relation ∈ (membership) relates individual , set (or class). in notation language of second-order arithmetic given signature





l


=
{
0
,
s
,
+
,
⋅
,
=
,
<
,
∈
}


{\displaystyle {\mathcal {l}}=\{0,s,+,\cdot ,=,<,\in \}}

.

for example,



∀
n
(
n
∈
x
→
s
n
∈
x
)


{\displaystyle \forall n(n\in x\rightarrow sn\in x)}

, well-formed formula of second-order arithmetic arithmetical, has 1 free set variable x , 1 bound individual variable n (but no bound set variables, required of arithmetical formula)—whereas



∃
x
∀
n
(
n
∈
x
↔
n
<
s
s
s
s
s
s
0
⋅
s
s
s
s
s
s
s
0
)


{\displaystyle \exists x\forall n(n\in x\leftrightarrow n<ssssss0\cdot sssssss0)}

well-formed formula not arithmetical, having 1 bound set variable x , 1 bound individual variable n.

semantics

several different interpretations of quantifiers possible. if second-order arithmetic studied using full semantics of second-order logic set quantifiers range on subsets of range of number variables. if second-order arithmetic formalized using semantics of first-order logic model includes domain set variables range over, , domain may proper subset of full powerset of domain of number variables (shapiro 1991, pp. 74–75).

axioms
basic

the following axioms known basic axioms, or robinson axioms. resulting first-order theory, known robinson arithmetic, peano arithmetic without induction. domain of discourse quantified variables natural numbers, collectively denoted n, , including distinguished member



 
0


{\displaystyle \ 0}

, called zero.

the primitive functions unary successor function, denoted prefix



 
s
,


{\displaystyle \ s,}

, , 2 binary operations, addition , multiplication, denoted infix + ,



⋅


{\displaystyle \cdot }

, respectively. there primitive binary relation called order, denoted infix < .

axioms governing successor function , zero:

1.



∀
m
[
s
m
=
0
→
⊥
]
.


{\displaystyle \forall m[sm=0\rightarrow \bot ].}

(“the successor of natural number never zero”)
2.



∀
m
∀
n
[
s
m
=
s
n
→
m
=
n
]
.


{\displaystyle \forall m\forall n[sm=sn\rightarrow m=n].}

(“the successor function injective”)
3.



∀
n
[
0
=
n
∨
∃
m
[
s
m
=
n
]
]
.


{\displaystyle \forall n[0=n\lor \exists m[sm=n]].}

(“every natural number 0 or successor”)

addition defined recursively:

4.



∀
m
[
m
+
0
=
m
]
.


{\displaystyle \forall m[m+0=m].}


5.



∀
m
∀
n
[
m
+
s
n
=
s
(
m
+
n
)
]
.


{\displaystyle \forall m\forall n[m+sn=s(m+n)].}

multiplication defined recursively:

6.



∀
m
[
m
⋅
0
=
0
]
.


{\displaystyle \forall m[m\cdot 0=0].}


7.



∀
m
∀
n
[
m
⋅
s
n
=
(
m
⋅
n
)
+
m
]
.


{\displaystyle \forall m\forall n[m\cdot sn=(m\cdot n)+m].}

axioms governing order relation < :

8.



∀
m
[
m
<
0
→
⊥
]
.


{\displaystyle \forall m[m<0\rightarrow \bot ].}

(“no natural number smaller zero”)
9.



∀
n
∀
m
[
m
<
s
n
↔
(
m
<
n
∨
m
=
n
)
]
.


{\displaystyle \forall n\forall m[m<sn\leftrightarrow (m<n\lor m=n)].}


10.



∀
n
[
0
=
n
∨
0
<
n
]
.


{\displaystyle \forall n[0=n\lor 0<n].}

(“every natural number 0 or bigger zero”)
11.



∀
m
∀
n
[
(
s
m
<
n
∨
s
m
=
n
)
↔
m
<
n
]
.


{\displaystyle \forall m\forall n[(sm<n\lor sm=n)\leftrightarrow m<n].}

these axioms first order statements. is, variables range on natural numbers , not sets thereof, fact stronger being arithmetical. moreover, there 1 existential quantifier, in axiom 3. axioms 1 , 2, axiom schema of induction make usual peano-dedekind definition of n. adding these axioms sort of axiom schema of induction makes redundant axioms 3, 10, , 11.

induction , comprehension schema

if φ(n) formula of second-order arithmetic free number variable n , possible other free number or set variables (written m• , x•), induction axiom φ axiom:

∀
m
∀
x
(
(
φ
(
0
)
∧
∀
n
(
φ
(
n
)
→
φ
(
s
n
)
)
→
∀
n
φ
(
n
)
)


{\displaystyle \forall m\forall x((\varphi (0)\land \forall n(\varphi (n)\rightarrow \varphi (sn))\rightarrow \forall n\varphi (n))}

the (full) second-order induction scheme consists of instances of axiom, on second-order formulas.

one particularly important instance of induction scheme when φ formula “



n
∈
x


{\displaystyle n\in x}

” expressing fact n member of x (x being free set variable): in case, induction axiom φ is

∀
x
(
(
0
∈
x
∧
∀
n
(
n
∈
x
→
s
n
∈
x
)
)
→
∀
n
(
n
∈
x
)
)


{\displaystyle \forall x((0\in x\land \forall n(n\in x\rightarrow sn\in x))\rightarrow \forall n(n\in x))}

this sentence called second-order induction axiom.

if φ(n) formula free variable n , possibly other free variables, not variable z, comprehension axiom φ formula

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


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

this axiom makes possible form set



z
=
{
n

|

φ
(
n
)
}


{\displaystyle z=\{n|\varphi (n)\}}

of natural numbers satisfying φ(n). there technical restriction formula φ may not contain variable z, otherwise formula



n
∉
z


{\displaystyle n\not \in z}

lead comprehension axiom

∃
z
∀
n
(
n
∈
z
↔
n
∉
z
)


{\displaystyle \exists z\forall n(n\in z\leftrightarrow n\not \in z)}

,

which inconsistent. convention assumed in remainder of article.

the full system

the formal theory of second-order arithmetic (in language of second-order arithmetic) consists of basic axioms, comprehension axiom every formula φ (arithmetic or otherwise), , second-order induction axiom. theory called full second-order arithmetic distinguish subsystems, defined below. because full second-order semantics imply every possible set exists, comprehension axioms may taken part of deductive system when these semantics employed (shapiro 1991, p. 66).