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:
“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)
“Depend upon it there comes a time when for every addition of knowledge you forget something that you knew before. It is of the highest importance, therefore, not to have useless facts elbowing out the useful ones.”
—Sir Arthur Conan Doyle (1859–1930)
“The force of truth that a statement imparts, then, its prominence among the hordes of recorded observations that I may optionally apply to my own life, depends, in addition to the sense that it is argumentatively defensible, on the sense that someone like me, and someone I like, whose voice is audible and who is at least notionally in the same room with me, does or can possibly hold it to be compellingly true.”
—Nicholson Baker (b. 1957)