We will take for granted that we understand the existence of what we call the natural numbers, i.e., the set NN whose elements are the numbers 1,2,3,4,....1,2,3,4,.... Indeed, the two salient properties of this set are that (a) there is a frist element (the natural number 1), and (b) for each element nn of this set there is a “very next” one, i.e., an immediate successor. We assume that the algebraic notions of sum and product of natural numbers is well-defined and familiar. These operations satisfy three basic relations:
Basic Algebraic Relations.
- (Commutativity) n+m=m+nn+m=m+n and n×m=m×nn×m=m×n for all n,m∈N.n,m∈N.
- (Associativity) n+(m+k)=(n+m)+kn+(m+k)=(n+m)+k and n×(m×k)=(n×m)×kn×(m×k)=(n×m)×k
for all n,m,k∈N.n,m,k∈N.
- (Distributivity) n×(m+k)=n×m+n×kn×(m+k)=n×m+n×k
for all n,m,k∈N.n,m,k∈N.
We also take as given the notion of one natural number being larger than another one.
2>1,2>1,5>3,5>3,n+1>n,n+1>n, etc.
We will accept as true the axiom of mathematical induction, that is, the following statement:
AXIOM OF MATHEMATICAL INDUCTION.
Let SS be a subset of the set NN of natural numbers. Suppose that
-
1∈S.1∈S.
-
If a natural number kk is in S,S, then the natural number k+1k+1 also is in S.S.
Then S=N.S=N.
That is, every natural number nn belongs to S.S.
REMARK The axiom of mathematical induction is for our purposes frequently employed as a
method of proof. That is, if we wish to show that a certain proposition holds for all
natural numbers, then we let SS denote the set of numbers
for which the proposition is true, and then, using the axiom
of mathematical induction, we verify that SS is all of NN
by showing that SS satisfies both of the above conditions. Mathematical induction can also be used as a method of definition. That is, using it, we can define an infinite number of objects {On}{On} that are indexed by the natural numbers. Think of SS as the set of natural numbers for which the object OnOn is defined. We check first to see that the object O1O1 is defined. We check next that, if the object OkOk is defined for a natural number k,k, then there is a prescribed procedure for defining the object Ok+1.Ok+1. So, by the axiom of mathematical induction, the object is defined for all natural numbers. This method of defining an infinite set of objects is often referred to as sl recursive definition, or definition by recursion.
As an example of recursive definition, let us carefully define exponentiation.
- Definition 1:
Let aa be a natural number. We define inductively natural numbers anan as follows: a1=a,a1=a, and, whenever akak is defined, then ak+1ak+1 is defined to be a×ak.a×ak.
The set SS of all natural numbers for which anan is defined is therefore all of N.N. For, a1a1 is defined, and if akak is defined there is a prescription for defining ak+1.ak+1. This “careful” definition of anan may seem unnecessarily detailed. Why not simply define anan as a×a×a×a...×aa×a×a×a...×ann times? The answer is that the ...,..., though suggestive enough, is just not mathematically precise. After all, how would you explain what ...... means? The answer to that is that you invent a recursive definition to make the intuitive meaning of the ...... mathematically precise. We will of course use the symbol ...... to simplify and shorten our notation, but keep in mind that, if pressed, we should be able to provide a careful definition.
- Derive the three laws of exponents for the natural numbers:
an+m=an×am.an+m=an×am.
HINT: Fix aa and mm and use the axiom of mathematical induction.
an×m=(am)n.an×m=(am)n.
HINT: Fix aa and mm and use the axiom of mathematical induction.
(a×b)n=an×bn.(a×b)n=an×bn.
HINT: Fix aa and bb and use the axiom of mathematical induction.
- Define inductively numbers {Si}{Si} as follows:
S1=1,S1=1, and if SkSk is defined, then Sk+1Sk+1 is defined to be Sk+k+1.Sk+k+1.
Prove, by induction, that
Sn=n(n+1)/2.Sn=n(n+1)/2.
Note that we could have defined SnSn using the ...... notation by Sn=1+2+3+...+n.Sn=1+2+3+...+n.
- Prove that
1+4+9+16+...+n2=n(n+1)(2n+1)6.1+4+9+16+...+n2=n(n+1)(2n+1)6.
(1) - Make a recursive definition of n!=1×2×3×...×n.n!=1×2×3×...×n.n!n! is called nn factorial.
There is a slightly more general statement of the axiom of mathematical
induction, which is sometimes of use.
GENERAL AXIOM OF MATHEMATICAL INDUCTION
Let SS be a subset of the set NN of natural numbers, and suppose that
SS satisfies the following conditions
-
There exists a natural number k0k0
such that k0∈S.k0∈S.
-
If SS contains a natural number k,k, then SS contains the
natural number k+1.k+1.
Then SS contains every natural number nn that is larger than or equal to k0.k0.
From the fundamental set NN of natural numbers, we construct
the set ZZ of all integers.
First, we simply create an additional number called 0 that satisfies
the equations 0+n=n0+n=n for all n∈Nn∈N and
0×n=00×n=0 for all n∈N.n∈N.
The word “create” is, for some mathematicians,
a little unsettling. In fact, the idea of zero did not appear in mathematics
until around the year 900.
It is easy to see how the so-called natural numbers came by their
name. Fingers, toes, trees, fish, etc., can all be counted,
and the very concept of counting is what the natural numbers are about.
On the other hand, one never needed to count zero fingers or fish, so that the notion of zero as a number easily could have
only come into mathematics at a later time, a time when arithmetic was becoming more sophisticated.
In any case, from our twenty-first century viewpoint, 0 seems very understandable,
and we won't belabor the fundamental question of its existence any further here.
Next, we introduce the so-called negative numbers.
This is again quite reasonable from our point of view.
For every natural number n,n, we let -n-n be a number which, when added to
n,n, give 0.
Again, the question of whether or not such negative numbers exist
will not concern us here.
We simply create them.
In short, we will take as given the existence of a
set Z,Z, called the integers,
which comprises the set NN
of natural numbers, the additional number 0,0, and the set -N-N of all negative numbers.
We assume that addition and multiplication of integers satisfy the three
basic algebraic relations of commutativity, associativity, and distributivity stated above.
We also assume that the following additional relations hold:
(
-
n
)
×
(
-
k
)
=
n
×
k
,
and
(
-
n
)
×
k
=
n
×
(
-
k
)
=
-
(
n
×
k
)
(
-
n
)
×
(
-
k
)
=
n
×
k
,
and
(
-
n
)
×
k
=
n
×
(
-
k
)
=
-
(
n
×
k
)
(2)for all natural numbers nn and k.k.
