8 1. The Real Numbers
16. Prove that a subset G of A × B is the graph of a function from A to B if and
only if the following condition is satisfied: for each a ∈ A there is exactly one
b ∈ B such that (a, b) ∈ G.
1.2. The Natural Numbers
The natural numbers are the numbers we use for counting, and so, naturally, they
are also called the counting numbers. They are the positive integers 1,2,3,....
The requirements for a system of numbers we can use for counting are very
simple. There should be a first number (the number 1), and for each number there
must always be a next number (a successor). After all, we don’t want to run out of
numbers when counting a large set of objects. This line of thought leads to Peano’s
axioms, which characterize the system of natural numbers N:
N1. There is an element 1 ∈ N.
N2. For each n ∈ N there is a successor element s(n) ∈ N.
N3. 1 is not the successor of an element of N.
N4. If two elements of N have the same successor, then they are equal.
N5. If a subset A of N contains 1 and is closed under succession (meaning s(n) ∈ A
whenever n ∈ A), then A = N.
Note: At this stage in the development of the natural number system, all
we have are Peano’s axioms; addition has not yet been defined. When we define
addition in N, S(n) will turn out to be n + 1.
Everything we need to know about the natural numbers can be deduced from
these axioms. That is, using only Peano’s axioms, one can define addition and
multiplication of natural numbers and prove that they have the usual arithmetic
properties. One can also define the order relation on the natural numbers and
prove that it has the appropriate properties. To do all of this is not diﬃcult, but
it is tedious and time consuming. We will do some of this here in the text and
the exercises, but we won’t do it all. We will do enough so that students should
understand how such a development would proceed. Then we will state and discuss
the important properties of the resulting system of natural numbers.
Our main tool in this section will be mathematical induction, a powerful tech-
nique that is a direct consequence of axiom N5.
Induction. Axiom N5 above is often called the induction axiom, since it is the
basis for mathematical induction. Mathematical induction is used in making defi-
nitions that involve a sequence of objects to be defined and in proving propositions
that involve a sequence of statements to be proved. Here, by a sequence we mean a
function whose domain is the natural numbers. Thus, a sequence of statements is
an assignment of a statement to each n ∈ N. For example, “n is either 1 or it is the
successor of some element of N” is a sequence of statements, one for each n ∈ N.
We will use induction to prove that all of these statements are true once we prove
the next theorem.