Latest revision as of 02:54, 16 May 2014

A New Look at Mathematical Induction

by: Robert Hansen, proud member of the math squad.

 keyword: tutorial, induction 

Introduction

This is not truly intended to teach anyone anything new about mathematical induction, but rather to teach those who already know mathematical induction another way of look at the problem that they may find easier to grasp or get a handle on.

I, personally, have found this definition and construction of mathematical induction to be very helpful and intuitive. I first read this construction not in a discrete math class or textbook, but on a book on geometry, called Elementary Geometry from an Advanced Standpoint, by Edwin E. Moise. To the reader who find these kinds of basic constructions interesting, I strongly recommend this text.

The Natural Numbers

Let us begin by talking not about mathematical induction, but about the natural numbers, and an alternate definition for the natural numbers.

I'm certain the reader is familiar with the natural numbers. A common way of defining them is just as the positive integers: {1, 2, 3, 4, ...}.

For the purposes of induction, however, it is much more convenient to define them in a different way.

Consider the following two statements about a set S:

(1) 1 is contained in S

(2) if k is in S, then k + 1 is also in S

In more mathematical notation, we have:

$ (1) 1\in S $

$ (2) k \in S \Rightarrow k + 1 \in S $

Using these two properties, let us construct a second definition of the natural numbers:

Definition (alternate): The natural numbers are the smallest set that satisfy both (1) and (2).

This may confuse the reader as smallest is a vague term. However, here, smallest means the following:

If A is a set that satisfies (1) and (2), then $ N \subset A $.

We can see this intuitively. The elements of the natural numbers are {1, 1 + 1, 1 + 1 + 1, ...} and can be defined recursively by defining each element as one plus the element before it. Therefore, if a set were to contain 1, and follow property (2), then the natural numbers must be contained within it.

Mathematical Induction

To formalize it, let us state what we stated above as a theorem:

Theorem (Induction Principle): Let S be a set of numbers. If S satisfies (1) and (2), then S must contain the natural numbers.

This is mathematical induction.

However, as it may not be immediately clear why, let us consider an example.

Example

Proposition: Let A be a set of order k. The number of subsets of A is $ 2^{k} $

Before we begin trying to prove this with the induction principle stated above, let us first define the power set:

Definition: The set of the subsets of a set A is called the power set of A, and can be denoted as $ P(A) $.

Using this new terminology and notation, the above proposition can be rewritten in the following way:

Proposition: Let A be a set of order k. $ \|P(A)\| = 2 ^ {k} $

To prove that this is true for all natural numbers, let S be the set of $ k = \|A\| $ for which the above holds.

Keep in mind that since we are only working with general sets and their subsets in this proposition, we needn't worry about different sets of the same order. They're all going to have the same number of subsets.

The first thing to notice about this proposition is that it is true for a set of order 1. Such a set has only two subsets: the whole set and the empty set. Because $ 2 = 2^1 $ (clearly), the proposition must hold.

Therefore, 1 is contained in S.

The next thing we'd like to notice is that if we have two sets A and A', where the only difference between the two is that A' has one extra element a', which is not in A, then the number of subsets of A' we should be able to divide into two groups: subsets of A' which contain a' and subsets of A' which do not.

The subsets of A' that do not contain a' must simply be the subsets of A, and those that do are simply the subsets of A union a'. Therefore, we have that $ \|P(A')\| = 2*\|P(A)\| $.

Therefore, if A is of order k and $ \|P(A)\| = 2^k $, and k' = k + 1, then:

$ \| P(A') \| = 2 * \| P(A) \| = 2 * 2^k = 2^k + 1 = 2^{k'} $ $ \Rightarrow \|P(A')\| = 2^{k'} $

From this, we see that S satisfies property (2). Therefore, by the induction principle S must contain the natural numbers, and therefore our proposition holds for all natural numbers.

The last thing to check is the empty set, which has order 0, but it can be easily shown that its power set is the empty set (a single element), and therefore our proposition holds for all sets.

Conclusion

Although induction may not necessarily be new to the reader, this definition and construction of mathematical induction I've found it to be very useful in comprehending and working with induction.

Back to the math Squad page.