(New page: = Induction = by: Robert Hansen, proud member of the math squad. <pre> keyword: tutorial, induction, strong induction, weak induction </pre> ---- == The...)
 
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
= Induction =
+
= A New Look at Mathematical Induction =
  
 
by: [[user:Hansen12 | Robert Hansen]], proud member of [[Math squad|the math squad]].
 
by: [[user:Hansen12 | Robert Hansen]], proud member of [[Math squad|the math squad]].
−
<pre> keyword: tutorial, induction, strong induction, weak induction </pre>
+
<pre> keyword: tutorial, induction </pre>
 
----
 
----
−
== The Natural Numbers ==
+
== Introduction ==
  
−
Before we can talk about induction, we must first talk about the natural numbers, and their properties.
+
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'm certain the reader is familiar with standard definitions of the natural numbers.  A common one is defining them as the positive integers: {1, 2, 3, 4, ...} and so 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.
−
For the purposes of this article, however, I'd like to introduce a new, equivalent definition of the natural numbers.  Consider a set of numbers, S, that follows the following two axioms:
+
To the reader who find these kinds of basic constructions interesting, I strongly recommend this text.
−
 
+
−
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:
+
−
 
+
−
<math> 1\in S</math>
+
−
<math> k \in S \Rightarrow </math>
+
−
 
+
−
An equivalent definition of the natural numbers is that it is the smallest set S that follows the two axioms given above.
+
−
 
+
−
For the readers familiar with mathematical induction, one may notice that these two axioms are the two things that need to be proven in a proof by induction.
+
  
 
----
 
----
−
== Mathematical Induction ==
+
== The Natural Numbers ==
  
−
Now that we have the natural numbers defined in a convenient package, let us continue to mathematical induction.
+
Let us begin by talking not about mathematical induction, but about the natural numbers, and an alternate definition for the natural numbers.
  
−
Let f(k) be a statement that is either true or false, and let S be the set of all k for which it is true.  By the above construction of the natural numbers, we can see that if S follows the two axioms described above,  
+
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, ...}.
−
S must contain the natural numbers.
+
  
−
----
+
For the purposes of induction, however, it is much more convenient to define them in a different way.
−
== Example ==
+
  
−
On first sight, the above definition may be a little hard to grasp and use, so let us consider an example:
+
Consider the following two statements about a set S:
  
−
Let A be a set or order n.  Show that the number of subsets of A is <math>2^n</math>
+
(1) 1 is contained in S
  
−
Proof by induction:
+
(2) if k is in S, then k + 1 is also in S
  
−
Before we begin, let's first define some terms.  The set of the subsets of a set A is called the power set of A, and
+
In more mathematical notation, we have:
−
can be denoted as <math>mathcal{P}(A)</math>.  It is also often denoted as <math>2^A</math>, but as we have yet to prove
+
−
that its order is <math>2^{|A|}</math>, that should probably be avoided.
+
  
−
Using the above terms, we can rephrase our example into proving the following:
+
<math>(1) 1\in S</math>
  
−
<math>|mathcal{P}(A)| = 2^{|A|}</math>
+
<math>(2) k \in S \Rightarrow k + 1 \in S</math>
  
−
Now that we have definitions and terms out of the way, let us begin induction:
+
Using these two properties, let us construct a second definition of the natural numbers:
  
−
Let S be the set of numbers k such that <math>|mathcal{P}(A)| = 2^{|A|}</math>, where
+
Definition (alternate):  The natural numbers are the smallest set that satisfy both (1) and (2).
−
|A| = k.
+
  
−
Let us begin by proving that the first axiom holds on S:
+
This may confuse the reader as smallest is a vague term.  However, here, smallest means the following:
  
−
Consider a set of order 1:
+
If A is a set that satisfies (1) and (2), then <math>N \subset A</math>.
  
−
<math>A = \{a\}</math>
+
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.
  
−
We know that therefore:
+
----
 +
== Mathematical Induction ==
  
−
<math>mathcal{P}(A) = \{\{a\}, \{\}\}</math>
+
To formalize it, let us state what we stated above as a theorem:
  
−
or alternatively:
+
Theorem (Induction Principle): Let S be a set of numbers.  If S satisfies (1) and (2), then S must contain the natural numbers.
  
−
<math>mathcal{P}(A) = \{A, /varnothing\}</math>
+
This is mathematical induction.
  
−
the two trivial subsets.
+
However, as it may not be immediately clear why, let us consider an example.
  
−
Therefore, we have that <math>|mathcal{A}(S)| = 2^{|A|}</math>.
+
----
 +
== Example ==
  
−
Therefore, the first axiom holds.
+
Proposition:  Let A be a set of order k. The number of subsets of A is <math>2^{k}</math>
  
−
Next, we wish to show that the second axiom also holds on S:
+
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 <math>P(A)</math>.
  
−
Suppose we know that k is in S.  Prove that k + 1 is also in S.
+
Using this new terminology and notation, the above proposition can be rewritten in the following way:
  
−
Let <math>A</math> be a set of order k.   
+
Proposition:  Let A be a set of order k.  <math> \|P(A)\| = 2 ^ {k} </math>
  
 +
To prove that this is true for all natural numbers, let S be the set of <math>k = \|A\|</math> for which the above holds.
  
−
are such that:
+
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.
  
−
<math>mathcal{P}(A) = 2^{|A|}</math>
+
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 <math>2 = 2^1</math> (clearly), the proposition must hold.
  
−
We need to show that <math>|mathcal{P}(A \cup b)| = 2^{|A| + 1} = 2^{|A \cut b|}</math>, where b is some element not
+
Therefore, 1 is contained in S.
−
in A.
+
  
 +
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 <math>\|P(A')\| = 2*\|P(A)\|</math>.
  
−
The common notation for the set of subsets of a set A is <math>2^A</math>.
+
Therefore, if A is of order k and <math>\|P(A)\| = 2^k</math>, and k' = k + 1, then:
  
−
Therefore, what we wish to
+
<math>\| P(A') \| = 2 * \| P(A) \| = 2 * 2^k = 2^k + 1 = 2^{k'}</math>
 +
<math>\Rightarrow \|P(A')\| = 2^{k'} </math>
  
−
Let S be the numbers for which the following statement is true:
+
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.
  
−
Let A be a set of order k.  The number of subsets of A is <math>2^k</math>
+
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.
  
−
To begin, let us consider a set of order 1, let's say
+
== Conclusion ==
  
−
<math>A_1 = \{a\}</math>
+
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.
−
This set has two subsets:
+
----
−
 
+
Back to [[Math squad|the math Squad page]].
−
<math>\{a\}, \{ \}</math>
+
−
 
+
−
Or alternatively:
+
−
 
+
−
<math> A_1, /varnothing</math>
+
−
 
+
−
Which the reader may recognize as the two trivial subsets.
+
−
 
+
−
Therefore, we have that S contains 1, as the set with one element has <math>2^1</math> elements.
+
−
 
+
−
Now, let us suppose that S contains k.  We wish to show that S also contains k + 1.
+
−
 
+
−
We know that the fact that S contains k means that
+

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.

Retrieved from "https://www.projectrhea.org/rhea/index.php?title=Induction_S14&oldid=66119"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

Correspondence Chess Grandmaster and Purdue Alumni

Prof. Dan Fleetwood