- #1

- 201

- 2

- Thread starter matqkks
- Start date

- #1

- 201

- 2

- #2

lurflurf

Homework Helper

- 2,432

- 132

- #3

- 1,047

- 777

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

- 795

- 7

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 becauseIs showing the equivalence of the well ordering principal and induction too abstract for your intended audience?

* 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.

- #5

- 1,047

- 777

Nice points Steve.

- #6

- 131

- 40

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".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.

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 here.

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

- 795

- 7

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?"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?

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

mathwonk

Science Advisor

Homework Helper

- 11,011

- 1,209

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.

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

Stephen Tashi

Science Advisor

- 7,362

- 1,359

- #10

- 15,393

- 684

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)

- Last Post

- Replies
- 5

- Views
- 1K

- Last Post

- Replies
- 9

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 1K

- Last Post

- Replies
- 2

- Views
- 991

- Last Post

- Replies
- 4

- Views
- 2K

- Last Post

- Replies
- 10

- Views
- 817

- Last Post

- Replies
- 8

- Views
- 2K

- Last Post

- Replies
- 3

- Views
- 3K

- Last Post

- Replies
- 5

- Views
- 2K

- Last Post

- Replies
- 11

- Views
- 1K