FANDOM


Hamburger hydraulic press

Pressed burger

Presburger arithmetic is a weak arithmetic theory. It is consistent, complete, and decidable, but is not strong enough to form statements about multiplication. The decision problem of determining whether a given statement is a theorem of Presburger arithmetic is in a doubly exponential complexity class.

Definition Edit

The language of Presburger arithmetic extends predicate calculus with a constant 0, unary operator S, binary operator +, and relation =. Its axioms are:

  • \(\forall n: S(n) \neq 0\)
  • \(\forall n \forall m: S(n) = S(m) \Rightarrow n = m\)
  • \(\forall n: n + 0 = n\)
  • \(\forall n \forall m: n + S(m) = S(n + m)\)
  • For every first-order formula \(\varphi(n)\): \((\varphi(0) \wedge (\forall n: \varphi(n) \Rightarrow \varphi(S(n)))) \Rightarrow \forall m: \varphi(m)\).

Properties Edit

As mentioned before, Presburger arithmetic is weak enough that it is not very useful as a general foundation for number theory. The fundamental theorem of arithmetic, for example, is arguably one of the most important results of number theory, but it is not expressible in the language of Presburger arithmetic.

The interest in the theory is that it is both consistent and complete. This does not violate Gödel's first incompleteness theorem, which only applies to theories with languages that can make statements about elementary arithmetic.

Presburger arithmetic is also decidable. Unlike its older siblings such as Robinson arithmetic and Peano arithmetic, there is an algorithm that determines whether a given statement is a theorem. Fischer and Rabin showed that the decision problem is in a doubly exponential complexity class; that is, there is a positive constant c such that for every non-deterministic procedure that decides the problem, for all sufficiently large n the procedure takes more than \(2^{2^{cn}}\) steps.[1]

Sources Edit

  1. http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps

See also Edit

Ordinals, ordinal analysis and set theory

Basics: cardinal numbers · normal function · ordinal notation · ordinal numbers
Theories: Presburger arithmetic · Peano arithmetic · second-order arithmetic · ZFC
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\Gamma_0\) · \(\vartheta(\Omega^3)\) · \(\vartheta(\Omega^\omega)\) · \(\vartheta(\Omega^\Omega)\) · \(\vartheta(\varepsilon_{\Omega + 1})\) · \(\psi(\Omega_\omega)\) · \(\psi(\varepsilon_{\Omega_\omega + 1})\) · \(\psi(\psi_I(0))\)‎ · \(\omega_1^\mathfrak{Ch}\) · \(\omega_1^\text{CK}\) · \(\lambda,\zeta,\Sigma,\gamma\) · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Slow-growing hierarchy · Hardy hierarchy · Middle-growing hierarchy · N-growing hierarchy
Uncountable cardinals: \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal · more...

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.