13 December 2002

The Beginning of Numbers

by George E. Hrabovsky, President, MAST

A Special Dedication

This column is dedicated to the future in the form of the children of the world. While there are those of us who may do great deeds, we are mostly set in our courses. The future is truly in the hands of the children. It is not possible to overstate the importance of educating our children. So, I want to dedicate this column to Stephanie, Amanda, and Logan; three good kids who mean a lot to me. May you never lose your curiosity.

Where We Have Been

We have been continuing our focus on the foundations of mathematics. We have discussed the basic ideas of set theory and logic, proof techniques, and quantifiers. Last column we covered the notions of families of sets.

Where Will We Go in This Column

In this column we will begin an exploration of numbers an the technique of mathematical induction.

A Starting Point

When examining numbers the idea of numbers there are several places that we can start. I have chosen to base the discussion on what we have done so far. Let us say that we have a set A with n elements,

In this case n is the number of elements in the set. We call this the cardinal number of the set. We can denote it with the symbol . So, we now have,

This is a good thing to use as the basis for the idea of numbers. We begin with the empty set,

By the definition the cardinal number of any set with a single element (called a singleton set) is 1, and so on.

We can invent a set of numbers that is based on the cardinal numbers. We will call them natural numbers and denote them with the symbol . So we say that,

Please note that not every author includes 0 in the set of natural numbers. Another way of thinking about the set of natural numbers is with the formula

where i is the number of the element preceding the current element; the first element has , the second element has , the third has , and so on so that the nth element has . The formula to describe the ith natural number would be,

The First Step in Proving Something for all Natural Numbers

Let's begin by showing how we can combine natural numbers. If we take two arbitrary sets, A and B, we can then combine them by increasing the cardinal number of A by the cardinal number of B,

This is the definition of the operation of addition. Since we can define the set of natural numbers as cardinal numbers, then it seems reasonable that the result of any addition of natural numbers will result in another natural number. So, we can state,

Theorem 7-1:

Proof: We will begin by assuming both and are equal to 1. This gives us 1 + 1 = 2. It is clear from (1) that 2 is an element of . Thus we know that Theorem 7-1 is true for 1. We can also show that this is true for 2, 3, etc.

The next step requires that we make the hypothesis that Theorem 7-1 is true for arbitrary natural numbers m and n. This is called an inductive hypothesis. The justification is that we have already shown 7-1 to be true for specific arbitrary natural numbers. We are abstracting the results of these specific cases to make a general statement.

If we can now show that 7-1 is also true for , we will have proven the theorem for all natural numbers. This makes sense is you think about a little. We know the theorem works for 1, and by the inductive hypothesis we state that it is true for arbitrary natural numbers. If we can show that it is true for any arbitrary natural number plus one we can show that the answer reproduces the set of natural numbers and so must be true. If we state that and , then,

From basic algebra we know that the order in which we add things doesn't change the answer, so we can rewrite (4)

By the inductive hypothesis the sum is a natural number, we can substitute the symbol p for this sum,

This is identical to (3), so the result reproduces the set of natural numbers. Thus we have proved Theorem 7-1. Specifically this is called the closure property of addition on the set of natural numbers.

This method is called the Method of Mathematical Induction. It has the following steps:

Step 1: Show that the theorem to be proved is true for 1.
Step 2: Use the Inductive Hypothesis to assume the theorem is true for an arbitrary natural number.
Step 3: Show that it is true for the arbitrary natural number + 1.

Suggested Practice Problems

1. Invent three sets and determine their cardinal numbers.
2. Prove the following by mathematical induction.

Theorem 7-2: (Closure Property of Multiplication)

Theorem 7-3: (Associative Property of Addition)

Theorem 7-4: (Associative Property of Multiplication)

Theorem 7-5: (Commutative Property of Addition)

Theorem 7-6: (Commutative Property of Multiplication)

Converted by Mathematica  (December 12, 2002)