Second-order arithmetic

Second-order arithmeticMain

Community hub

7 pages, 0 posts

0 subscribers

Recent from talks

Be the first to start a discussion here.

Recent from talks

Be the first to start a discussion here.

Contribute something

About hubMembersContent overviewUpdatesRules

Main reference articles

Second-order arithmetic

View on Wikipedia

from Wikipedia

Not found

Revisions and contributors Edit on Wikipedia Read on Wikipedia

View on Grokipedia

from Grokipedia

Second-order arithmetic is a formal system in mathematical logic that extends first-order Peano arithmetic by incorporating second-order quantification over subsets of the natural numbers, allowing the expression and proof of theorems involving sets and higher-level properties within the domain of arithmetic.^[1]^[2] Its language is two-sorted, featuring first-order variables for individual natural numbers (e.g.,

x, y

) and second-order variables for sets of natural numbers (e.g.,

X, Y

), along with function symbols for addition (

+

) and multiplication (

\times

), relations for equality (

=

) and order (

<

), and membership (

\in

).^[3]^[2] The axioms of full second-order arithmetic, often denoted

Z_2

, include the basic axioms of Robinson arithmetic

Q

(such as successor non-zero and no cycles in successors), a comprehension scheme asserting the existence of sets defined by any formula in the language (i.e., for any formula

\phi(n)

free of the set variable

X

, there exists

X

such that

\forall n (n \in X \leftrightarrow \phi(n))

), and an induction axiom schema that applies to arbitrary sets: if a set contains 0 and is closed under the successor function, it contains all natural numbers.^[2]^[3] This system is semantically interpreted over the standard model of the natural numbers

\mathbb{N}

with the full power set

\mathcal{P}(\mathbb{N})

, enabling it to categorically characterize the structure

(\mathbb{N}, +, \times)

up to isomorphism—a capability beyond first-order arithmetic due to limitations like the Löwenheim-Skolem theorem.^[1] Second-order arithmetic plays a central role in the foundations of mathematics, particularly through its subsystems (e.g.,

\mathrm{RCA}_0

with recursive comprehension and

\Sigma^0_1

-induction,

\mathrm{ACA}_0

with arithmetical comprehension, and stronger variants like

\Pi^1_1

\mathrm{CA}_0

), which are studied in reverse mathematics to determine the precise set-existence axioms required to prove core theorems in analysis, algebra, and topology.^[3] For instance, many classical results, such as the Bolzano-Weierstrass theorem, are equivalent to

\mathrm{ACA}_0

over

\mathrm{RCA}_0

, highlighting the system's utility in calibrating the strength of mathematical principles without full set theory.^[3] Philosophically, it bridges first-order and set-theoretic logics, raising questions about impredicativity and the reliance on a set-theoretic metatheory for its semantics, while formalizing significant portions of countable mathematics, including aspects of real analysis via arithmetical comprehension.^[1]

Overview and Historical Context

Core Concepts

Second-order arithmetic is a formal theory in mathematical logic that extends the foundations of arithmetic by incorporating quantification over sets of natural numbers, providing a framework for much of classical analysis and beyond. It is formulated as a two-sorted first-order theory, with one sort for individual natural numbers (typically denoted by variables like

n, m \in \mathbb{N}

) and another sort for sets of natural numbers (denoted by variables like

X, Y \subseteq \mathbb{N}

). This structure allows the theory to reason about both numerical computations and higher-level properties of collections of numbers, such as sequences, functions, and relations definable over

\mathbb{N}

.^[3] In contrast to first-order Peano arithmetic (PA), which is limited to quantification solely over individual natural numbers and thus cannot directly express concepts involving infinite subsets or full induction over all properties, second-order arithmetic introduces variables ranging over the power set

\mathcal{P}(\mathbb{N})

. This enables the full second-order induction axiom, which asserts that any property definable by a formula involving set quantifiers holds for all natural numbers if it holds for zero and is preserved under the successor function. Additionally, the comprehension scheme allows the existence of sets defined by arbitrary formulas, ensuring that the theory can construct subsets of

\mathbb{N}

corresponding to predicates in its language, thereby capturing the expressive power needed for mathematical analysis without invoking a full set-theoretic universe.^[3] A basic illustration of this capability is how second-order arithmetic models the power set of the naturals: set variables directly represent elements of

\mathcal{P}(\mathbb{N})

, and the comprehension axiom guarantees that for any formula

\phi(n)

, there exists a unique set

X

such that

n \in X

if and only if

\phi(n)

holds, all within the theory's arithmetic base. This avoids the need for a separate axiomatic set theory like ZFC, as the sets are inherently tied to arithmetic predicates, providing a lightweight yet potent system for encoding countable mathematics.^[3] Informally, second-order arithmetic motivates much of reverse mathematics, a program that classifies theorems of ordinary mathematics by determining the minimal subsystems of the theory required to prove them, revealing the logical strength underlying concepts from analysis, algebra, and geometry.^[3]

Development and Significance

The formalization of second-order arithmetic traces back to Richard Dedekind's 1888 work Was sind und was sollen die Zahlen?, where he employed second-order quantification to axiomatize the natural numbers and prove the uniqueness of their structure up to isomorphism, with significant developments in the early 20th century as part of efforts to formalize the foundations of analysis and arithmetic within a predicative framework. Hermann Weyl introduced a foundational system in his 1918 work Das Kontinuum, which restricted comprehension to arithmetical definitions, resembling the modern subsystem ACA₀ and emphasizing predicative methods to avoid impredicative set formations. This approach was motivated by Weyl's critique of classical analysis, aiming to construct the real numbers using only hereditarily finite sets and arithmetical predicates. Subsequently, David Hilbert and Paul Bernays developed a more comprehensive second-order arithmetic in their Grundlagen der Mathematik (Volumes I and II, 1934 and 1939), integrating it into Hilbert's program for finitistic proofs of consistency. Their system formalized substantial fragments of real analysis, using second-order variables to represent sets of naturals, and served as a bridge between finitary arithmetic and higher mathematics.^[3]^[4] Key advancements in the mid-20th century built on these foundations through model-theoretic and proof-theoretic analyses. In the 1950s, Georg Kreisel contributed significantly to the study of models of second-order arithmetic, particularly in his 1950 paper on arithmetic models for predicate calculus formulae, where he explored consistency and definability using hyperarithmetical sets. Kreisel's work in the 1950s and 1960s further examined predicative subsystems, showing limitations like the failure of the perfect set theorem in such systems and advancing ordinal analyses that informed later hierarchies. The field gained renewed momentum in the late 20th century with Stephen G. Simpson's development of reverse mathematics during the 1970s and 1980s, culminating in his 2009 book Subsystems of Second Order Arithmetic. Simpson systematized the "Big Five" subsystems (RCA₀, WKL₀, ACA₀, ATR₀, Π¹₁-CA₀), demonstrating how they calibrate the set existence axioms needed for core mathematical theorems.^[3] The significance of second-order arithmetic lies in its role as a foundational framework that bridges first-order arithmetic with analysis, allowing the formalization of much of classical mathematics—such as countable algebra, graph theory, and parts of analysis—without the full power of Zermelo-Fraenkel set theory with choice (ZFC). It provides the basis for reverse mathematics, where theorems are "reversed" to identify minimal axioms for their proofs, revealing the logical structure underlying ordinary mathematics and partial realizations of Hilbert's program. This bridge enables precise studies of computability and definability, as sets of naturals correspond to reals, facilitating encodings of continuous structures within discrete arithmetic. As of 2025, second-order arithmetic remains central to ongoing research in proof theory, where subsystems inform ordinal notations and consistency strengths; in computability theory, supporting analyses of hyperarithmetic sets and Turing degrees; and in descriptive set theory, underpinning determinacy results for projective sets. Recent works, such as those on constructive variants and their proof-theoretic ordinals, continue to extend its applications, highlighting its enduring relevance in foundational mathematics.^[5]

Formal Foundations

Syntax

Second-order arithmetic is formalized in a two-sorted first-order language

L_2

, consisting of a sort for natural numbers and a sort for subsets of natural numbers.^[3] The individual variables, often denoted by lowercase letters such as

n, m, k \in \mathbb{N}

, range over the natural numbers

\omega = \{0, 1, 2, \dots \}

. The set variables, denoted by uppercase letters such as

X, Y, Z \subseteq \mathbb{N}

, range over subsets of

\omega

.^[3] The language includes the constant symbols

0

and

1

for the numerical terms, as well as the binary function symbols

+

and

\cdot

(multiplication, often denoted

\times

) for addition and multiplication on natural numbers.^[3] Numerical terms are formed recursively: they include the number variables, the constants

0

and

1

, and expressions built from these using

+

and

\cdot

, such as

n + m

(n \cdot k) + 1

.^[3] The predicate symbols consist of equality

=

(between numerical terms), the strict order

<

(between numerical terms), and membership

\in

(relating a numerical term to a set variable, as in

n \in X

).^[3] Atomic formulas are the equality statements

t_1 = t_2

, the order statements

t_1 < t_2

, and the membership statements

t \in X

, where

t_1, t_2, t

are numerical terms and

X

is a set variable.^[3] Well-formed formulas are constructed inductively from atomic formulas using the propositional connectives

\neg

(negation),

\land

(conjunction),

\lor

(disjunction),

\to

(implication), and

\leftrightarrow

(biconditional), as well as the quantifiers: universal and existential quantifiers over numbers (

\forall n

\exists n

) and over sets (

\forall X

\exists X

).^[3] A formula with no free variables is called a sentence.^[3] Formulas in

L_2

are classified based on their quantifier structure, distinguishing the first-order and second-order aspects. Arithmetical formulas (or

\Delta_0^1

and higher levels in the arithmetical hierarchy) are those that use only number quantifiers and no set quantifiers, effectively forming the first-order part of the language equivalent to Peano arithmetic.^[3] Second-order formulas incorporate set quantifiers, enabling the expression of properties involving subsets of natural numbers, such as comprehension principles.^[3]

Semantics

The semantics of second-order arithmetic interprets its language in mathematical structures that capture both individual natural numbers and collections of such numbers, providing a precise meaning to formulas involving quantification over sets. A structure for second-order arithmetic consists of a pair

(\mathbb{N}, \mathcal{P}(\mathbb{N}))

, where

\mathbb{N}

is the domain of standard natural numbers equipped with the usual operations of addition (+), multiplication (·), and the order relation (<), along with constants 0 and 1, and

\mathcal{P}(\mathbb{N})

denotes the full power set of

\mathbb{N}

, serving as the domain for second-order variables that range over all possible subsets of natural numbers.^[3]^[1] The satisfaction relation for formulas in second-order arithmetic follows a Tarskian definition, recursively specifying when a structure satisfies a given formula under a variable assignment. For the first-order fragment, satisfaction is defined in the standard way over

\mathbb{N}

, evaluating atomic formulas using the interpretations of predicates and functions. Second-order quantifiers, such as

\forall X \phi

\exists X \phi

where

X

is a second-order variable, are satisfied if the formula

\phi

holds for all (or some) elements of

\mathcal{P}(\mathbb{N})

, respectively, with the assignment interpreting

X

as an arbitrary subset of

\mathbb{N}

.^[1]^[6] Two primary semantic frameworks distinguish interpretations of second-order arithmetic: full semantics and Henkin semantics. In full semantics, second-order quantifiers range over the complete power set

\mathcal{P}(\mathbb{N})

, including all subsets, which ensures a robust interpretation but leads to incompleteness with respect to provability since not all subsets are definable. Henkin semantics, in contrast, permits a partial interpretation where second-order quantifiers range over a restricted collection of subsets (e.g., those definable by formulas in the language), allowing for a completeness theorem but yielding non-categorical models that may not capture the full expressive power of the theory.^[1]^[3] In the standard model of second-order arithmetic, denoted

(\mathbb{N}, \mathcal{P}(\mathbb{N}), +, \cdot, 0, 1, <)

, truth is determined by evaluating formulas against all subsets of

\mathbb{N}

, encompassing both recursive (computable) sets and non-recursive sets that cannot be effectively described by any algorithm. This model uniquely characterizes the intended structure up to isomorphism under full semantics, as the second-order induction axiom and comprehension principles enforce the standard naturals and their full power set.^[3]^[1]

Axioms

Second-order arithmetic, often denoted as

\mathrm{Z_2}

or SOA, is formalized in a two-sorted first-order language with individual variables for natural numbers and set variables for subsets of the natural numbers, including symbols for zero (0), one (1), addition (+), multiplication (×), ordering (<), and membership (∈). The successor function is expressed by the term

n + 1

.^[3] The basic axioms consist of the first-order Peano axioms adapted to this language, governing the structure of the natural numbers and the arithmetic operations. These include:

∀n (n + 1 ≠ 0)
∀m ∀n (m + 1 = n + 1 → m = n)
∀m (m + 0 = m)
∀m ∀n (m + (n + 1) = (m + n) + 1)
∀m (m × 0 = 0)
∀m ∀n (m × (n + 1) = (m × n) + m)
¬∃m (m < 0)
∀m ∀n (m < n + 1 ↔ (m < n ∨ m = n))

These axioms ensure that the natural numbers form a discrete ordered semiring with no zero divisors.^[3]^[1] The induction schema extends the first-order version to second-order formulas, allowing induction over properties definable using quantification over sets. Formally, for every formula φ(n) in the language (possibly involving set quantifiers), the axiom states:

[\phi(0) \land \forall n \, (\phi(n) \to \phi(n + 1))] \to \forall n \, \phi(n)

This schema, together with the basic axioms, characterizes the standard model of the natural numbers up to isomorphism when interpreted in full semantics.^[3]^[1] The comprehension schema is the defining feature of the full second-order system, asserting the existence of sets defined by arbitrary properties. For every formula ψ(n) with free variable n (and no free set variables other than parameters), the schema yields:

\exists X \, \forall n \, (n \in X \leftrightarrow \psi(n))

This full comprehension enables the theory to capture the power set of the naturals, distinguishing Z₂ from its weaker subsystems.^[3]^[1] The deductive system of Z₂ employs the rules of classical first-order logic, extended to the two-sorted structure with separate quantifier rules for numbers and sets, including generalization over both sorts and standard inference rules like modus ponens.^[3]

Models

Standard Models

The standard model of second-order arithmetic is the structure

(\mathbb{N}, \mathcal{P}(\mathbb{N}), 0, S, +, \times, \in)

, where

\mathbb{N}

denotes the set of natural numbers starting from 0,

\mathcal{P}(\mathbb{N})

is the full power set of

\mathbb{N}

consisting of all subsets of natural numbers,

S

is the successor function, and

+

\times

, and

\in

are the standard addition, multiplication, and membership relation, respectively.^[1] This model satisfies all the axioms of the full theory Z

_2

of second-order arithmetic, including the basic axioms of arithmetic, the second-order induction axiom, and the full comprehension schema allowing quantification over all subsets.^[3] Due to the expressive power of full second-order semantics, this structure is unique up to isomorphism, categorically characterizing the natural numbers and their subsets in a way that first-order Peano arithmetic cannot achieve.^[1] This standard model captures the full scope of classical mathematical analysis, as the subsets in

\mathcal{P}(\mathbb{N})

enable the formalization of concepts from real analysis, topology, and beyond within the framework of second-order arithmetic.^[3] In particular, it decides all

\Pi^1_1

and

\Sigma^1_1

statements—universal and existential quantifications over sets of natural numbers with arithmetic matrix—by evaluating them against the complete collection of all possible subsets, providing definitive truth values grounded in classical set theory. The tight alignment between the theory's full semantics and the intended interpretation of arithmetic and analysis reflects the categorical nature of Z

_2

.^[1] A key feature of the standard model is its identification of the real numbers with subsets of

\mathbb{N}

, typically via binary expansions, where each subset

X \subseteq \mathbb{N}

corresponds to the real number whose binary representation has 1s in the positions indexed by elements of

X

(e.g.,

\sum_{n \in X} 2^{-(n+1)}

).^[1] This coding allows the model to represent the continuum

2^\omega

faithfully, supporting the development of analytic hierarchies and the proof of theorems in classical real analysis directly within the structure.^[3]

Non-Standard Models

In second-order arithmetic, non-standard models deviate from the unique standard model

\langle \mathbb{N}, \mathcal{P}(\mathbb{N}) \rangle

by employing generalized semantics, where second-order quantifiers range over proper subsets of the full power set rather than all subsets of the natural numbers. These models, often called general or Henkin models, arise when the collection of second-order objects is a countable family of subsets closed under the operations definable in the language, satisfying the comprehension axiom schema only for formulas whose witnessing sets lie within this restricted collection. Such structures validate the full axioms of second-order arithmetic but fail to capture all subsets of the naturals, leading to incompleteness relative to the standard interpretation.^[1] Henkin models were introduced to establish completeness for second-order logic, reducing the semantics to a many-sorted first-order framework where the Löwenheim-Skolem theorem applies, ensuring the existence of countable models. In the context of arithmetic, a Henkin model consists of a first-order structure for the natural numbers (potentially non-standard) paired with a collection

S

of subsets of its domain, where

S

is closed under definable comprehension and satisfies induction for sets in

S

. This allows for non-standard interpretations of the number sort, where the order type extends beyond

\omega

, while the second-order part remains incomplete. For instance, the model may include non-standard numbers but only a countable portion of the intended power set, enabling the proof of theorems like compactness that fail in full semantics. A special class of ω-models, known as

\beta

-models, provides a well-founded alternative to general models by ensuring correctness about well-orderings. A

\beta

-model is an

\omega

-model of second-order arithmetic—meaning its number sort is exactly

\mathbb{N}

—in which every relation coded by a set in the model induces the correct well-founded part, as determined by

\Sigma^1_1

-definability over the model itself, i.e., a set codes a well-ordering if and only if it is well-ordered externally. These models satisfy true first-order arithmetic and accurately reflect the ordinals representable in the hyperarithmetic hierarchy, making them minimal models for subsystems like ATR

_0

. The existence of countable

\beta

-models follows from forcing techniques or recursive construction, though uncountable ones align more closely with the standard model's scale. Non-standard number models, where the carrier for natural numbers

\mathbb{N}^*

has order type beyond

\omega

but the second-order interpretation includes the full power set

\mathcal{P}(\mathbb{N}^*)

, are exceedingly rare in second-order arithmetic due to the strength of the induction schema. In full semantics, the second-order induction axiom forces the number sort to be standard, as any non-standard extension would violate the categoricity of the theory; thus, such models exist only in generalized semantics but require careful closure under comprehension to avoid collapse. Their rarity underscores the theory's rigidity, with most constructions yielding partial power sets instead.^[7] The standard model of full second-order arithmetic is uncountable, as

\mathcal{P}(\mathbb{N})

has cardinality

2^{\aleph_0}

, but the Löwenheim-Skolem theorem for Henkin semantics guarantees countable models by reducing the theory to a countable first-order signature. This downward extension implies that any consistent second-order theory admitting a model has a countable Henkin model, highlighting the paradox that the uncountable continuum can be "simulated" in countable structures without capturing all subsets. Upward Löwenheim-Skolem variants further ensure models of any desired infinite cardinality, though these remain non-standard unless expanding to the full power set.^[1]

Definable Functions

In second-order arithmetic, sets

X \subseteq \mathbb{N}

are definable if there exists a first- or second-order formula

\phi(n, \vec{z})

ϕ(n,z

) (possibly with number or set parameters $\vec{z}$

) such that $X = \{ n \in \mathbb{N} \mid \mathbb{N} \models \phi(n, \vec{z}) \}$

)}.^[3] Functions from $\mathbb{N}$ to $\mathbb{N}$ are similarly represented as their graphs, which are definable sets of pairs in $\mathbb{N} \times \mathbb{N}$ satisfying functional conditions like totality and uniqueness.^[3] All primitive recursive functions are definable using arithmetical comprehension alone, as their graphs are arithmetical sets provably existent in subsystems like $ACA_0$ , where comprehension applies to arithmetical formulas.^[3] For example, basic operations such as addition and multiplication, along with closure under primitive recursion and projection, yield graphs that are $\Delta^0_1$ -definable, ensuring their totality is provable without second-order quantifiers beyond arithmetical means.^[3] In the standard model of full second-order arithmetic $Z_2$ , the comprehension axiom scheme guarantees the existence of all subsets of $\mathbb{N}$ , each definable via the instance of comprehension for its characteristic formula $\phi(n) \equiv n \in X$ .^[3] However, the sets whose existence and properties are provable within the theory using parameter-free second-order formulas are limited to the $\Delta^1_1$ sets, which are both $\Sigma^1_1$ - and $\Pi^1_1$ -definable and coincide with the lightface projective sets of low complexity.^[3] The hyperarithmetic sets extend this scope and are definable through iterated applications of comprehension, starting from recursive sets and building a transfinite hierarchy via Turing jumps along well-orderings up to the Church-Kleene ordinal $\omega_1^{CK}$ , the least upper bound of computable ordinals.^[3] This hierarchy captures all sets hyperarithmetic in the empty set, forming the minimal $\omega$ -model of $\Delta^1_1$ -comprehension ( $\Delta^1_1$ -CA $_0$ ), where each level adds sets computable relative to previous jumps, ultimately encompassing all $\Delta^1_1$ -definable sets without parameters.^[3] Functions whose graphs lie in this class, such as those provably total in subsystems like ATR $_0$ , align with hyperarithmetic computability, bridging definability and ordinal iteration in the theory.^[3]

Subsystems and Hierarchies

Weak Subsystems

Weak subsystems of second-order arithmetic restrict the comprehension axiom to Δ^0_1 formulas and limit induction to low-complexity formulas, forming the foundation for reverse mathematics, which calibrates the axiomatic strength required to prove theorems of ordinary mathematics.^[3] These systems capture aspects of computable and recursive mathematics while avoiding full analytical power.^[3] The system RCA₀, or Recursive Comprehension Axiom, consists of the basic axioms of second-order arithmetic (including those for the natural numbers and set formation), the Δ^0_1 comprehension scheme (allowing comprehension for formulas equivalent to both Σ^0_1 and Π^0_1), and the Σ^0_1 induction scheme (induction for Σ^0_1 formulas).^[3] It serves as the baseline for reverse mathematics, formalizing the notion of recursive functions and sets.^[8] RCA₀ interprets primitive recursive arithmetic (PRA), proving the totality of all primitive recursive functions, and is conservative over PRA for Π^0_2 sentences.^[9] WKL₀ builds on RCA₀ by adjoining Weak König's Lemma, which asserts that every infinite binary tree (a tree with nodes labeled by finite binary sequences, finitely branching) contains an infinite path, equivalent to the compactness principle for countable 2-valued languages.^[3] This addition enables proofs of theorems like the Heine-Borel covering theorem for [0,1] but preserves conservativity over PRA for Π^0_2 sentences.^[9] WKL₀ models recursive mathematics augmented with limited choice principles, lying strictly between RCA₀ and stronger systems in the reverse mathematics hierarchy.^[3] In terms of overall strength, these weak subsystems surpass PRA by incorporating second-order objects but are significantly weaker than ZF⁻ (Zermelo-Fraenkel set theory without the axiom of infinity), as they only handle countable sets and lack power set or replacement axioms for uncountable structures.^[3] RCA₀, for instance, has models consisting solely of recursive sets, highlighting its computable focus, while ZF⁻ supports full ordinal arithmetic up to ω.^[8]

Arithmetical and Analytical Hierarchies

In second-order arithmetic, formulas are classified into hierarchies based on the complexity of their quantifiers, distinguishing between those involving only numerical quantifiers and those incorporating second-order set quantifiers. The arithmetical hierarchy addresses the former, encompassing formulas built solely from first-order quantifiers over natural numbers, while the analytical hierarchy extends to formulas with unbounded set quantifiers. These classifications, introduced in foundational works on recursion theory and descriptive set theory, provide a measure of definability and computational complexity for sets of natural numbers. The arithmetical hierarchy partitions formulas (and the sets they define) according to the number and type of alternating numerical quantifiers in prenex normal form, where all quantifiers precede a quantifier-free matrix. A formula is in

\Sigma^0_n

if it begins with an existential numerical quantifier block followed by

n-1

alternations (ending with existential if

n

is odd and universal if

n

is even), such as

\exists x_1 \forall x_2 \dots Q x_n \phi(x_1,\dots,x_n)

where

\phi

is quantifier-free and

Q

is existential for odd

n

. The complementary class

\Pi^0_n

starts with a universal quantifier, and

\Delta^0_n = \Sigma^0_n \cap \Pi^0_n

consists of formulas equivalent in both forms. Levels of this hierarchy correspond to increasing degrees of unsolvability in Turing reducibility; for instance,

\Sigma^0_1

sets are recursively enumerable, while higher levels capture sets computable relative to oracles of greater complexity.^[10] In contrast, the analytical hierarchy incorporates unbounded second-order quantifiers over subsets of natural numbers, classifying formulas by the number of such set quantifier alternations in prenex normal form, with remaining numerical quantifiers absorbed into an arithmetical matrix. A

\Sigma^1_n

formula takes the form

\exists X_1 \forall X_2 \dots Q X_n \psi(X_1,\dots,X_n)

where

\psi

is arithmetical (i.e., in the arithmetical hierarchy), starting with an existential set quantifier;

\Pi^1_n

is the dual, and

\Delta^1_n = \Sigma^1_n \cap \Pi^1_n

. For example,

\Sigma^1_1

formulas assert the existence of a set

X \subseteq \mathbb{N}

satisfying an arithmetical property, defining the class of analytic sets when interpreted over the reals. This hierarchy captures higher-order definability, with each level strictly extending the previous in expressive power. Prenex normal form is essential for these hierarchies, allowing systematic quantifier rearrangement while preserving equivalence under the axioms of second-order arithmetic; any formula can be transformed into this form by pulling quantifiers outward, though set quantifiers require careful handling to maintain boundedness in the arithmetical case. The arithmetical hierarchy corresponds to the Borel hierarchy in descriptive set theory, where boldface

\mathbf{\Sigma}^0_n

sets (allowing real parameters) are Borel sets on Polish spaces like the Cantor space

2^\omega

, generated by countable unions and complements from open sets. Analytical levels align with the projective hierarchy: boldface

\mathbf{\Sigma}^1_n

sets are projective, obtained by iterated projections from Borel sets, enabling the study of definable sets on uncountable Polish spaces without full choice axioms.^[11] A key collapse result is that the entire arithmetical hierarchy coincides with

\Delta^1_1

, meaning every arithmetical set is both

\Sigma^1_1

and

\Pi^1_1

relative to the standard model of natural numbers; this uniformizes their definability using a single second-order quantifier alternation. The distinction between lightface (effective, parameter-free) and boldface (with parameters) versions further refines this: lightface classes like

\Sigma^0_n

and

\Sigma^1_n

emphasize recursive or computable aspects, while boldface counterparts

\mathbf{\Sigma}^0_n

and

\mathbf{\Sigma}^1_n

generalize to arbitrary definable sets, bridging recursion theory with classical descriptive set theory on Polish spaces. These hierarchies thus interconnect computability, proof theory, and topology, formalizing much of the structure of definable reals and ordinals.^[12]^[11]

Stronger Subsystems

In second-order arithmetic, stronger subsystems extend the base theory by incorporating more powerful comprehension axioms or recursion principles, enabling the formalization of advanced mathematical concepts such as non-computable sets and transfinite constructions. These systems are central to reverse mathematics, a program that identifies the minimal axioms needed to prove theorems of ordinary mathematics. Among the key stronger subsystems are ACA₀, ATR₀, and Π¹₁-CA₀, which form part of the "Big Five" hierarchy alongside weaker bases, ordered by increasing proof-theoretic strength: RCA₀ < WKL₀ < ACA₀ < ATR₀ < Π¹₁-CA₀.^[8] ACA₀, or arithmetical comprehension, augments the base system with the full arithmetical comprehension axiom scheme, allowing the existence of sets defined by arithmetical formulas (those without set quantifiers), along with Σ^0_1 induction. This subsystem proves the existence of arithmetic sets, including Turing jumps such as the halting set, and is equivalent over RCA₀ to principles like the sequential least upper bound axiom and the Bolzano-Weierstrass theorem in analysis. ACA₀ is conservative over Peano arithmetic for arithmetical sentences and serves as the foundation for predicative analysis, with its minimal ω-model consisting of the arithmetical sets.^[8]^[13] Building on ACA₀, ATR₀ introduces arithmetical transfinite recursion, which permits defining sets via transfinite iterations along countable well-orderings recognizable arithmetically. Formally, it includes the scheme ∀X (WO(X) → ∃Y H_φ(X,Y)) for arithmetical φ, where WO(X) asserts X codes a well-ordering and H_φ defines the hierarchy. ATR₀ interprets second-order arithmetic over the hyperarithmetic sets, enabling proofs of theorems in descriptive set theory such as the perfect set theorem and Luzin's separation theorem, and its proof-theoretic ordinal is the Feferman-Schütte ordinal Γ₀. This subsystem bridges predicative and impredicative methods, with equivalences over RCA₀ to the existence of iterated arithmetic hierarchies.^[8]^[13] The strongest of these is Π¹₁-CA₀, featuring Π¹₁ comprehension, which asserts the existence of sets defined by Π¹₁ formulas (universal set quantifiers followed by arithmetical formulas). This impredicative axiom scheme proves advanced results like the Cantor-Bendixson theorem and the Kondô-Addison uniformization theorem, handling higher levels of the projective hierarchy. Π¹₁-CA₀ exceeds ATR₀ in strength, formalizing much of countable algebra and descriptive set theory, and is the pinnacle of the Big Five, where many ordinary mathematical theorems reverse to one of these systems, highlighting their foundational role.^[8]^[13]

Advanced Topics

Projective Determinacy

Projective sets are the subsets of the real numbers

\mathbb{R}

(or equivalently, of the Baire space

\omega^\omega

) that are definable by formulas in the language of second-order arithmetic, forming the projective hierarchy

\mathbf{\Sigma}^1_n

\mathbf{\Pi}^1_n

for

n \in \omega

, starting from the analytic sets

\mathbf{\Sigma}^1_1

as existential projections of Borel sets and closing under complements and further projections.^[14] These sets arise naturally in the analytical hierarchy of second-order arithmetic through quantification over sets of naturals, which code reals, and they capture the definable content of the continuum within this theory.^[14] The axiom of projective determinacy (PD) asserts that every projective set

A \subseteq \omega^\omega

defines a determined Gale-Stewart game

G_A

: two players alternately choose natural numbers to build a real

x \in \omega^\omega

, with player I winning if

x \in A

and player II winning otherwise; determinacy means one player has a winning strategy.^[15] This axiom resolves long-standing questions in descriptive set theory about the regularity properties of projective sets, such as Lebesgue measurability and the property of Baire, which follow from PD via game-theoretic arguments.^[16] Historically, PD emerged as a key conjecture in the 1960s amid efforts to extend Borel determinacy (proved by Martin in 1975) to higher levels of the projective hierarchy; it was conclusively established in the 1980s through the seminal work of Donald A. Martin and John R. Steel, who showed that PD follows from suitable large cardinal assumptions.^[15] Specifically, the existence of infinitely many Woodin cardinals below a measurable cardinal implies PD, building on results by W. Hugh Woodin; this connection highlights PD's role as a bridge between inner model theory and descriptive set theory within the framework of second-order arithmetic.^[17]^[14] In second-order arithmetic, PD has profound implications, proving uniformization for all projective sets: for any projective relation

R \subseteq \omega^\omega \times \omega^\omega

with non-empty vertical sections, there exists a projective uniformizing function

f: \omega^\omega \to \omega^\omega

such that

(x, f(x)) \in R

whenever

\exists y (x, y) \in R

. This result, due to Yiannis N. Moschovakis, enables the systematic selection of witnesses in projective definitions, enhancing the theory's expressive power. Moreover, PD strengthens subsystems of second-order arithmetic beyond

\Pi^1_1

-CA

_0

, implying higher levels of comprehension and transfinite induction schemes for projective formulas, thus resolving many undecided statements in descriptive set theory that are arithmetic in the second-order sense.^[14]^[14]

Coding of Analysis and Set Theory

In second-order arithmetic, real numbers are encoded as subsets of the natural numbers

\mathbb{N}

, typically via binary expansions where a real

x \in [0,1]

is represented by the infinite binary sequence coding its decimal expansion, or alternatively through continued fractions or Dedekind cuts.^[8] This coding allows the rationals

\mathbb{Q}

to be formalized as pairs of naturals, and operations such as addition and multiplication on reals are defined set-theoretically using these representations, provable in the base system RCA

_0

.^[3] The formalization of real analysis proceeds in subsystems of second-order arithmetic, with RCA

_0

sufficient to develop the theory of Cauchy reals, including their metric structure and basic properties like completeness (by construction of the Cauchy completion).^[3] Key theorems of analysis require stronger axioms: for instance, the Bolzano-Weierstrass theorem—stating that every bounded sequence of reals has a convergent subsequence—is equivalent to ACA

_0

over RCA

_0

, as its proof relies on arithmetic comprehension to existentially quantify the limit.^[18] Fragments of set theory can be interpreted within stronger subsystems of second-order arithmetic. In ATR

_0

, which extends ACA

_0

with arithmetical transfinite recursion, one can interpret ZF

^-

(Zermelo-Fraenkel set theory without the axiom of replacement) and Kripke-Platek set theory, allowing the formalization of admissible ordinals and hyperexponential hierarchies up to the hyperjump.^[19] ACA

_0

suffices to develop ordinals up to

\varepsilon_0

, the least fixed point of

\alpha \mapsto \omega^\alpha

, via iterated arithmetic comprehension on well-orderings.^[3] Reverse mathematics highlights these encodings through equivalences: the Heine-Borel theorem, asserting that closed and bounded subsets of

\mathbb{R}

are compact, is equivalent to WKL

_0

over RCA

_0

, as compactness corresponds to the existence of paths in binary trees representing covers.^[20] However, second-order arithmetic has inherent limitations; it cannot fully interpret ZFC set theory, as all sets are subsets of

\mathbb{N}

(hence countable), precluding uncountable cardinals like

2^{\aleph_0}

without additional axioms beyond the hyperarithmetic hierarchy.^[8] Moreover, the halting problem is undecidable in RCA

_0

, since the halting set is

\Pi^1_1

-complete and requires comprehension beyond

\Delta^1_0

sets, which RCA

_0

restricts to recursive comprehension.^[3]

Info Pages

Talk Pages

Special Pages

Second-order arithmetic

Recent from talks

Recent from talks

Contribute something

Contribute something

Media Pages

Timelines

Articles

Notes collections

Notes

Notes

Days in Chronicle

Second-order arithmetic