|
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). |
About us|Jobs|Help|Disclaimer|Advertising services|Contact us|Sign in|Website map|Search|
GMT+8, 2015-9-11 22:04 , Processed in 0.505881 second(s), 16 queries .
