Peano's Axioms and Induction
Important note: Most textbooks do not include zero among the set of natural
numbers. However, Peano, in his original formulation of these five
postulates, did include zero in this set. Therefore, in this page, I will
be faithful to this original formulation. See "Is
Zero A Natural Number?" for more about this.
Peano's five axioms define the natural numbers starting with just 0 and s, the successor function. (The successor
s(x) is the number immediately after x, ie x+1).
0 in N zero
s: N --> N successor
0 ~= s(x), any x in N
s(x) = s(y) ==> x = y one-to-one
The fifth axiom, induction, is more complex. Suppose F(x) is a statement about natural number x. Then
F(0) and (for all x in N, F(x) ==> F(s(x))) ==> (F(x) for any x in N)
Other arithmetic operators can be defined, e.g. by recursion
0 + n = n base case for +
s(m) + n = s(m + n) recursive case for +
0 * n = 0 base case for *
s(m) * n = n + (m * n) recursive case for *
The ordering relations are defined
m >= n <=> m = n + p, some p in N
m > n <=> m = n + p, some p in N+
Here N+ = N \ {0} is the positive integers.
From these axioms, and simple logical reasoning, all properties of the natural numbers can be deduced,
including the fact that N has no maximum, and the well-ordering theorem:
/0 ~= S subset N ==> S has a minimum element
which is crucial to proving the termination of
recursive programs such as Euclid's gcd algorithm.
The set of Integers (Positive Naturals + 0 + Negatives) is usually denoted Z.
A ring is an algebraic system that it is closed under addition,
subtraction, and multiplication (but not necessarily division). A ring is ordered
if it has a relation of 'greater than', symbolized by ">", with
1>0, b>a if and only if b-a>0, and such that the positive elements
(those greater than 0) are closed under addition and multiplication. An ordered
ring is well-ordered if every nonempty subset of its positive elements
has a (necessarily unique) smallest element. Then, the (positive and negative)
integers Z form the unique (up to isomorphism) well-ordered ring.
The set of Rationals (a/b, where a, b are integers, b not zero) is usually
denoted Q.
A field is a ring that is closed under the four basic arithmetic
operations (addition, subtraction, multiplication, and division by nonzero
elements). Then, the system Q of rational numbers is the unique
(up to isomorphism) smallest ordered field.
The set of Reals (limits of converging series of Rationals) is usually
denoted R.
An ordered field is complete if every nonempty set X of its
elements that is bounded above (there is some element of the field that
is greater than or equal to every element in X) has a smallest upper
bound. Then, the system R of real numbers is the unique (up to
isomorphism) complete, ordered field.
Internet References
The
Foundations of Mathematics, an overview at the close of the second
millennium, by William S. Hatcher
Related pages in this website
Go back to Basic Principles
Sets - how to construct sets of integers, reals,
etc.
Is Zero a Natural Number? --
a discussion of the fact that some authors include zero, and others do not.
The Peano Postulates --
Proving the properties of natural numbers using the Peano Postulates, which
have been formulated so that zero is not included in the set of natural
numbers. (There's quite a debate about this point.)
Introduction to Counting -- explains what
mathematicians mean by "counting" -- that is, putting sets in
one-to-one correspondence.
Set Theory -- an introduction to sets, including
examples of some standard sets.
Counting Ordered Pairs of
Integers -- An explanation of the "square spiral" that puts the
set of natural numbers in one-to-one correspondence with the set of rational
numbers.
Abstract Algebra -- definitions of
terms associated with Ring Theory and Group Theory
