A photograph of Giuseppe Peano
Peano arithmetic (also known as first-order arithmetic) is a first-order axiomatic theory over the natural numbers.
Language[]
The language of first-order arithmetic consists of the language of predicate logic extended by the following:
- Constant symbol \(0\), called zero
- Relation symbol \(=\), called equality
- Unary function symbol \(S(x)\), called successor
- Two binary function symbols, \(+(a,b),\cdot(a,b)\), called addition and multiplication respectively, and often denoted by \(a+b,a\cdot b\).
Axioms[]
- \(\forall n:0\neq S(n)\) - zero isn't a successor of any natural number.
- \(\forall n,m: S(n)=S(m)\Rightarrow n=m\) - two numbers with equal successors are equal themselves, so \(S(x)\) is an injective function.
- \(\forall n: n+0=n\)
- \(\forall n,m: n+S(m)=S(n+m)\) - this and previous axiom state inductive properties of addition.
- \(\forall n: n\cdot 0=0\)
- \(\forall n,m: n\cdot S(m)=n\cdot m+n\) - this and previous axiom state inductive properties of multiplication.
- For every first-order formula \(\varphi(x)\): \((\varphi(0)\land(\forall n:\varphi(n)\Rightarrow\varphi(S(n)))\Rightarrow\forall n:\varphi(n)\) - this is so called axiom schema of induction, which states that if some property \(\varphi\) holds for zero, and if any number \(n\) posseses this property, then so does its successor, then this property holds for every natural number.
Analysis[]
We assume consistency, which is not proven but strongly believed. PA can prove many everyday facts about the natural numbers, and considering Friedman's grand conjecture,[1] it may even be more than enough.
Some examples of googological functions that eventually dominate all functions provably recursive in PA are the Kirby-Paris hydra, Beklemishev's worms, and Goodstein sequences.
PA has proof-theoretic ordinal \(\varepsilon_0\).
Sources[]
See also[]
Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation · Absolute infinity
Theories: Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
Model Theoretic Concepts: structure · elementary embedding
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\eta_0\) · \(\Gamma_0\) (Feferman–Schütte ordinal) · \(\varphi(1,0,0,0)\) (Ackermann ordinal) · \(\psi_0(\Omega^{\Omega^\omega})\) (small Veblen ordinal) · \(\psi_0(\Omega^{\Omega^\Omega})\) (large Veblen ordinal) · \(\psi_0(\varepsilon_{\Omega + 1}) = \psi_0(\Omega_2)\) (Bachmann-Howard ordinal) · \(\psi_0(\Omega_\omega)\) with respect to Buchholz's ψ · \(\psi_0(\varepsilon_{\Omega_\omega + 1})\) (Takeuti-Feferman-Buchholz ordinal) · \(\psi_0(\Omega_{\Omega_{\cdot_{\cdot_{\cdot}}}})\) (countable limit of Extended Buchholz's function) · \(\omega_1^\mathfrak{Ch}\) (Omega one of chess) · \(\omega_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\gamma,\zeta,\Sigma\) (Infinite time Turing machine ordinals) · gap ordinal · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Hardy hierarchy · Slow-growing hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Weak Buchholz's function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Weak Buchholz's function · Extended Buchholz's function · Jäger-Buchholz function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert's Psi function · Arai's psi function
Uncountable cardinals: \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal · Berkeley cardinal · (Club Berkeley cardinal · limit club Berkeley cardinal)
Classes: \(\textrm{Card}\) · \(\textrm{On}\) · \(V\) · \(L\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)