Addition
The theory of the natural numbers with a successor function has signature consisting of a constant 0 and a unary function S ("successor": S(x) is interpreted as x+1), and has axioms:
- ∀x ¬ Sx = 0
- ∀x∀y Sx = Sy → x = y
- Let P(x) be a first-order formula with a single free variable x. Then the following formula is an axiom:
- (P(0) ∧ ∀x(P(x)→P(Sx))) → ∀y P(y).
The last axiom (induction) can be replaced by the axioms
- For each integer n>0, the axiom ∀x SSS...Sx ≠ x (with n copies of S)
- ∀x ¬ x = 0 → ∃y Sy = x
The theory of the natural numbers with a successor function is complete and decidable, and is κ-categorical for uncountable κ but not for countable κ.
Presburger arithmetic is the theory of the natural numbers under addition, with signature consisting of a constant 0, a unary function S, and a binary function +. It is complete and decidable. The axioms are
- ∀x ¬ Sx = 0
- ∀x∀y Sx = Sy → x = y
- ∀x x + 0 = x
- ∀x∀y x + Sy = S(x + y)
- Let P(x) be a first-order formula with a single free variable x. Then the following formula is an axiom:
- (P(0) ∧ ∀x(P(x)→P(Sx))) → ∀y P(y).
Read more about this topic: List Of First-order Theories
Famous quotes containing the word addition:
“But the best read naturalist who lends an entire and devout attention to truth, will see that there remains much to learn of his relation to the world, and that it is not to be learned by any addition or subtraction or other comparison of known quantities, but is arrived at by untaught sallies of the spirit, by a continual self-recovery, and by entire humility.”
—Ralph Waldo Emerson (1803–1882)
“The addition of a helpless, needy infant to a couple’s life limits freedom of movement, changes role expectancies, places physical demands on parents, and restricts spontaneity.”
—Jerrold Lee Shapiro (20th century)
“Napoleon wanted to turn Paris into Rome under the Caesars, only with louder music and more marble. And it was done. His architects gave him the Arc de Triomphe and the Madeleine. His nephew Napoleon III wanted to turn Paris into Rome with Versailles piled on top, and it was done. His architects gave him the Paris Opera, an addition to the Louvre, and miles of new boulevards.”
—Tom Wolfe (b. 1931)