Is Mathematical Induction the Key to Understanding Finite and Infinite Concepts?

In summary, the conversation discusses different ways of explaining and understanding mathematical induction. Some students are not convinced by the common analogy of dominoes, and are looking for a more impactful approach. The conversation also touches on real-life applications of induction, including counting and the Euclidean algorithm. The concept of well ordering principle is also mentioned, but it is debated whether it is too abstract for beginners. The conversation concludes with a discussion on the philosophical implications of induction and its relationship to the Peano axioms.
  • #1
matqkks
285
5
Some students are not convinced that a proof by mathematical induction is a proof. I have given the analogy of dominoes toppling but still some remain unconvinced. Is there very convincing way of introducing mathematical induction? I need something which will have an impact. Are there any real life applications of induction?
 
Mathematics news on Phys.org
  • #2
Dominoes or a ladder or stairs are good analogies. Also counting or any example of a unbounded finite process. So explain how do we know we can count to n? Suppose a lock has an integer combination we are sure to open it eventually. Can we weigh an elephant with small pebbles? The Euclidean algorithm will terminate. Pose it not so much as handling all integers (which is true but confusing) but a way to build up to handle some particular large integer.
 
  • #3
Is showing the equivalence of the well ordering principal and induction too abstract for your intended audience? The WOP seems so very obvious and easy to understand, but it's very interesting to look at all it's implications. Maybe there's a way you can de-abstract the WOP, show its equivalence to induction...

Also the peano axioms (in a basic form like here http://mathworld.wolfram.com/PeanosAxioms.html) are very easy to swallow and equivalent to induction.

That of course is the abstract approach. But maybe it could help?
 
  • #4
dkotschessaa said:
Is showing the equivalence of the well ordering principal and induction too abstract for your intended audience?

At the end of the (mathematical) day, the only reason induction is true is because we assume an axiom that says it's true. There are (as far as we know) no infinite sets in the universe. The natural numbers 1, 2, 3, ... along with the induction principle, exist only because

* The Peano axioms (PA) say they do; and

* The Axiom of Infinity of ZF provides a model of PA.

Absent those assumptions, there's no reason to "believe" in infinitary processes. It's intellectually honest to explain to students that induction is "true" because it's true about the abstract mental model of the natural numbers that we assume in order to do mathematics. That's really the only reason.

Induction is not "true" in the same sense, that, say, the law of gravity is true. You can drop a rock from a height and show that general relativity explains its gravitational acceleration to within a dozen decimal places.

Induction has no such justification. Induction is "true" only because we agree that PA is a correct characterization of our mental model of the counting numbers. Ultimately this is a matter for philosophers.

I wonder what would happen if we were honest with students about these kinds of things.
 
  • Like
Likes 1 person
  • #5
Nice points Steve.
 
  • #6
SteveL27 said:
At the end of the (mathematical) day, the only reason induction is true is because we assume an axiom that says it's true. There are (as far as we know) no infinite sets in the universe. The natural numbers 1, 2, 3, ... along with the induction principle, exist only because

* The Peano axioms (PA) say they do; and

* The Axiom of Infinity of ZF provides a model of PA.

Absent those assumptions, there's no reason to "believe" in infinitary processes. It's intellectually honest to explain to students that induction is "true" because it's true about the abstract mental model of the natural numbers that we assume in order to do mathematics. That's really the only reason.

Induction is not "true" in the same sense, that, say, the law of gravity is true. You can drop a rock from a height and show that general relativity explains its gravitational acceleration to within a dozen decimal places.

Induction has no such justification. Induction is "true" only because we agree that PA is a correct characterization of our mental model of the counting numbers. Ultimately this is a matter for philosophers.

I wonder what would happen if we were honest with students about these kinds of things.

This may be true, and I'll leave such considerations to the philosophers, but is it actually helpful for any student who doesn't "believe in" induction? I think it's too close to the "math is just a game played under certain rules" point of view, which I often see here in somewhat extreme forms. For example, someone will ask why 5 times 12 equals 12 times 5 in such a way that it's clear that this person isn't very mathematically sophisticated, and the best explanation is to draw a 5 by 12 rectangle or 5 rows of 12 dots, etc., and then view this in two different ways. Instead, too often the answer is simply something like "by the axiom of commutativity for rings".

I think your answer is similar; it's suitable for advanced students who pretty much already understand induction in terms of dominoes or ladders, but seems to invert cause and effect and is in some sense a non-answer. Isn't it more honest to say that the axiom of induction is chosen because induction is "true", meaning roughly "intuitively clear", instead of the other way around? Then we're back at square one: why do we accept this axiom?

That may have been too wordy and I didn't mean to pick on your answer for two paragraphs (I actually think it's a pretty good answer), I'm just not sure if it's appropriate for beginners. I agree with lurflurf about not trying to consider the infinite sets as a whole, but by "building up" to a number as large as we want (something like the difference between actual and potential infinity). After all, mathematicians who would have outright rejected modern theories of infinite sets were using induction hundreds of years ago, so that doesn't seem to be a huge stumbling block.

I can't think of any amazing examples to convince them now, but I always thought the L-shaped tiling problem was interesting. Also prime number factorization, although that's strong induction (which I think I remember being equivalent to regular induction anyway). Both are described http://www.stanford.edu/class/cs103a/handouts/42%20Mathematical%20Induction.pdf.

I actually don't like most of the standard examples using induction, like 1^2+2^2+...+n^2=whatever, because there are usually better and more interesting ways of doing them.
 
  • #7
Tobias Funke said:
This may be true, and I'll leave such considerations to the philosophers, but is it actually helpful for any student who doesn't "believe in" induction?

Oh of course you're right. I was not seriously suggesting that we try to explain this sophisticated point of view to beginners. Or if I did believe it for a moment, it didn't last long. I visualized a room full of students asking, "Will this be on the test?"

The way I explain induction to a beginner is to say, "If P is true for zero; and it's true for n + 1 whenever it's true for n; then it P must be true for all counting numbers. And if you don't believe me ... name the first number where P is false!"

I think that last part makes them visualize the dominos falling. I know it does for me.
 
  • #8
by the way, as an amusing comment, as an abstract principle WO is actually much stronger than induction, i.e. they are not equivalent. They are equivalent for the natural numbers of course but not in general. Think about the well ordered set consisting of the natural numbers but ordered so that all even numbers are larger than all odd numbers. then the usual proof by induction (the truth of P for any element implies P also holds for the "next larger" element) only proves a result for the odd integers, but WO would prove it for the whole set.

A proof by induction is only valid for WO sets in which every element has a predecessor, as in the natural numbers.
 
Last edited:
  • #9
Show the students examples that demonstrate the distinction between "true for any finite number however large" and "true for an infinite number". (e.g. for any finite set of numbers, there is a maximum). If the students see that the power of induction is limited, they are more likely to believe it.
 
  • #10
Stephen Tashi said:
Show the students examples that demonstrate the distinction between "true for any finite number however large" and "true for an infinite number". (e.g. for any finite set of numbers, there is a maximum). If the students see that the power of induction is limited, they are more likely to believe it.
Example: Since the union of two closed sets is itself a closed set, the union of any finite number of closed sets is a closed set by induction. This obviously is not necessarily true for the union of an infinite number of closed sets.

I think what Stephen is getting at is that "Mathematical induction affords, more than anything else, the essential characteristic by which the finite is distinguished from the infinite." (Bertrand Russel)
 

1. What is Mathematical Induction?

Mathematical induction is a method of mathematical proof used to prove that a statement is true for all values of a variable in a given range. It involves three steps: the base case, the inductive hypothesis, and the inductive step.

2. How does Mathematical Induction work?

In mathematical induction, the base case is first proved to be true. Then, the inductive hypothesis is assumed to be true for a specific value of the variable. Finally, using this assumption and the mathematical properties of the statement, the inductive step is used to prove that the statement is true for the next value of the variable. This process is repeated until the statement is proven to be true for all values of the variable.

3. What are the advantages of using Mathematical Induction?

Mathematical induction is a powerful method of proof that can be used to prove statements for all values of a variable in a given range. It is often used in mathematical and computer science to prove the correctness of algorithms and formulas.

4. What are some common misconceptions about Mathematical Induction?

One common misconception about mathematical induction is that it only works for natural numbers. In reality, it can be used for any well-ordered set, such as integers, rational numbers, or even infinite sets. Another misconception is that it can only be used to prove statements in a specific form, but it can actually be used to prove a wide range of statements.

5. Are there any limitations to using Mathematical Induction?

While mathematical induction is a powerful method of proof, there are some limitations to its use. For example, it cannot be used to prove statements that are not true for the values of the variable in the given range. It also requires the statement to have a specific form, which may not always be the case. In these situations, other proof techniques may be more suitable.

Similar threads

  • General Math
Replies
5
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
7K
Replies
3
Views
600
Replies
8
Views
2K
  • STEM Academic Advising
Replies
9
Views
1K
Replies
1
Views
2K
Replies
7
Views
2K
  • Science and Math Textbooks
Replies
28
Views
1K
  • Math Proof Training and Practice
Replies
8
Views
1K
Replies
12
Views
1K
Back
Top