Talk:Proof of mathematical induction

Untitled

It seems that the proof uses the well-ordering axiom on numbers, which is essentially equivalent to the principle of mathematical induction!!! wshun 04:12, 10 Aug 2003 (UTC)

Yes, ummmm....that's the point. To prove their equivalence. I don't see what your point is.

Merge?

I'm looking at this article, and I'm thinking that maybe this should be merged with Mathematical induction. -- Fogger 00:06, 13 September 2005 (UTC)

Problem with the proof of the converse...

When proving the converse you are using that there is no integer between n and n+1. The problem is that the standard proof of this use well-ordering.

That can be proven using induction, but that proof should be included. Alternately, a proof that a number is either 0 or the successor of a number should be included.

Implicit assumption

While proving induction principle you use the assumption

for all x: x>0 => there exists y such that x=y+1

but this is not provable from the other Peano axioms (in fact you need to add this axiom to Robinson arithmetic (where you no longer have induction).--Pokipsy76 17:11, 26 March 2006 (UTC)

Added this axiom to the set of assumptions to prove the induction principle. The trans-finite naturals (ordinals) are well ordered but standard induction fails because of limit ordinals which are not the successor or another ordinal.

It's not up to our decision to add assumptions to make proofs work: we must just understand how things work in the mathematical literature.--Pokipsy76 08:05, 14 July 2006 (UTC)

Clearer english statement

I believe I can state this proof in a way that would be easier for a reader less mathematically minded (like myself) to understand:

1. Having proved that 0 has a certain property P: formally P(0)
2. And, having proved that, if any natural number n has the property P then n+1 must also have this property: formally P(n)=>P(n+1)
3. It is asserted that every natural number m must have this property: formally P(m)

Proof:

• Assume that there is/are some natural number(s) mˈ which does/do not have the P property: formally notP(mˈ)
• The smallest mˈ, call it mˈˈ, is not 0 (by #1)
• But then mˈˈ-1 must have the property P: formally P(mˈˈ-1)
• And mˈˈ = (mˈˈ-1)+1, so, by substitution in #2, P(mˈˈ-1)=>P((mˈˈ-1)+1), which is simply P(mˈˈ-1)=>P(mˈˈ)
• This says that since the largest natural number smaller than mˈˈ, having the property P, implies that the successor, mˈˈ must also have the property P (by #2)
• The assumption is thus contradicted, and #3 is proved.

I am sure that someone will correct any errors I have made. Too Old 05:34, 22 April 2006 (UTC)

Integer values

should be swap integer values with natural numberrs to be more clear in the line: in other words P is true for all integer values of m.

Changing the tile

What about changing the title to "equivalence between induction principle and well ordering principle"?--Pokipsy76 13:57, 23 July 2006 (UTC)

I should prefer not to, because they're not equivalent. The ordered set (1,2,3...∞) is well ordered, but mathematical induction does not apply to it (consider the property "is finite": 1 is finite, and if n is finite, n + 1 is finite, but ∞ is not.) Transfinite induction is another article. Septentrionalis 18:20, 23 July 2006 (UTC

Also, in intuitionistic mathematics natural induction is (usually) an accepted proof principle, while well-orderability is in general not considered true. --Lambiam^Talk 00:44, 24 July 2006 (UTC)

I don't see how induction on the natural numbers is related to the original post in this section. It is of course true, and provable in ZF without choice, that a linearly ordered set is already well ordered if and only if it supports induction for arbitrary subsets of the order (in the language of ordered sets). I doubt this is provable intuitionistically, because $\lnot \forall$ doesn't translate to $\exists$ in that setting; but this article is not about intuitionistic reasoning, and it is unreasonable to add a caveat to every article that is not valid intuitionistically. CMummert 02:59, 24 July 2006 (UTC)

I thought the article was about induction on the natural numbers, and that the post was related to the subject of the article. Further, I don't see why Wikipedia should claim without caveat that something is true if it is only true under the assumption of an unfounded set of axioms. --Lambiam^Talk 11:25, 24 July 2006 (UTC)

In a structure for PA without induction, every nonzero number is the successor of some other number; the second post in this section (by Septentrionalis) seems confused about this, because the counterexample there does not have this property. I think that the first post in this section (by Pokipsy76) was proposing something more general: change the article to prove the equivalence between an arbitrary ordered set supporting transfinite induction and the set being well ordered. I don' t know that that is any more interesting than the article as it stands, but its how I interpret the post. As to the value of adding intuitionsim disclaimers to everything: let's postpone that discussion to some other time. CMummert 13:04, 24 July 2006 (UTC)

And that's a much narrower property than well-ordering. Septentrionalis 15:23, 24 July 2006 (UTC)

A principled proof

A principled proof can be given by defining the natural numbers to be the carrier of the initial algebra in the class of algebras with signature

zero : 1 → N

succ : N → N

This defines a set with the appropriate "Peano structure" uniquely up to isomorphism. It can now be shown that for this set the proposition usually called the "axiom of induction" is actually a theorem. I've no idea if this is considered standard. --Lambiam^Talk 00:54, 24 July 2006 (UTC)

That is indeed standard; it has been known for a long time that second order PA has only one model, and all the category-theoretical language is just another way to express this fact. CMummert 02:43, 24 July 2006 (UTC)

From Introductory Real Analysis

This excerpt from Kolmogorov and Fomin may be of interest.

---

Theorem 4 (Mathematical induction). Given a proposition P(n) formulated for every positive integer n, suppose that

1. P(1) is true;
2. The validity of P(k) for all k ≤ n implies the validity of P(n+1).

Then P(n) is true for all n = 1, 2, …

Proof. Suppose P(n) fails to be true for all n = 1, 2, …, and let n₁ be the smallest integer for which P(n) is false (the existence of n₁ follows from the well-ordering of the positive integers). Clearly n₁ > 1, so that n₁−1 is a positive integer. Therefore P(n) is valid for all k ≤ n₁−1 but not for n₁. Contradiction! ∎

Replacing the set of all positive integers by an arbitrary well-ordered set, we get

Theorem 4′. (Transfinite induction). Given a well ordered set A, let P(a) be a proposition formulated for every element a ∈ A. Suppose that

1. P(a) is true for the smallest element of A;
2. The validity of P(a) for all a < a^∗ implies the validity of P(a^∗).

Then P(a) is true for all a ∈ A.

Proof. Suppose P(a) fails to be true for all a ∈ A. Then P(a) is false for all a in some nonempty subset A^∗ ⊂ A. By the well-ordering, A^∗ has a smallest element a^∗. Therefore P(a) is valid for all a < a^∗ but not for a^∗. Contradiction! ∎

Remark. Since any set can be well-ordered, by the well-ordering theorem, transfinite induction can in principle be applied to any set M whatsoever. In practice, however, Zorn's lemma is a more useful tool, requiring only that M be partially ordered.

---

Both these proofs are trivial. Munkres, in Topology, mentions that the "Principle of Induction" follows from a definition of the positive integers (which he defines using "inductive sets"), but omits a proof, and only introduces transfinite induction in an exercise. Admittedly neither of these books is concentrating on foundations. (For example, K&F do not give a formal definition of the integers prior to these proofs, but are using the much broader well-ordering of sets Zermelo derived from the axiom of choice.)

Still, my feeling is that this article must do something more to justify its independent existence. For example, contrast the content here with that at Proofs of Fermat's little theorem or Proof that the sum of the reciprocals of the primes diverges. --KSmrq^T 15:56, 26 July 2006 (UTC)

In the article Well-ordering principle there is a sketch of this argument.--Pokipsy76 09:38, 27 July 2006 (UTC)

Looking for more substance on foundations, I checked Enderton, A mathematical introduction to logic (ISBN 978-0-12-238450-9). As expected, there is an extended discussion, but none of it closely matches this article. Perhaps someone would like to check Suppes, Axiomatic Set Theory (ISBN 978-0-486-61630-8) or some other careful source. For alternatives, note that Troelstra's Lectures on linear logic (ISBN 978-0-937073-77-3) considers "inductive proof structures" in the context of Girard proof nets, a radically different discussion. However, the incredibly dense Freyd and Scedrov, Categories, Allegories (ISBN 978-0-444-70368-2) again builds induction into Peano axioms. --KSmrq^T 16:01, 27 July 2006 (UTC)