Talk:Principle of Mathematical Induction

From ProofWiki
Jump to navigation Jump to search

I added this page and Second Principle of Mathematical Induction to the Proofs by Induction category. Seeing as they are the basis for the proofs in that category, I thought it made sense. However, I did not add Principle of Finite Induction or Second Principle of Finite Induction to this category. I don't know what other people think would make sense for these in terms of category assignments. --cynic 20:12, 30 September 2008 (UTC)

I'd have no problems with Finite Induction going in there as well.

The "Mathematical Induction" ones are at a "higher level" than the "finite induction" ones (in the computer programming sense), in that they're more user friendly from the point of view of using them in proofs. The "finite induction" ones are there mainly because they need to be proved first before the "mathematical induction" ones can be validated. --Prime.mover 20:56, 30 September 2008 (UTC)

Okay, done. --cynic 23:17, 30 September 2008 (UTC)

Re-evaluating categories

We now have enough different induction principles that I would suggest a separate category of induction principles, perhaps as a subcategory of proof techniques. Perhaps this page could expand to index the second, third, whatever principle of induction, transfinite induction, well-ordered induction, well-founded induction, etc., etc.

Perhaps this page stays as it is, because there are lots of pages that link to this. Changing this one now will cause all sorts of stuff to break.
This page is standalone and needs no expansion. We don't do it like that on this website anyway. Before major grandiose structural architecture work, get to know how the rest of the site fits together, and that means: start small. Suggest you work on an area of mathematics you understand well (you seem to be seriously bogged down in class-theory axiomatics, some of the pages you've made repeated false starts on and don't seem to have a clue what your strategy is for whatever your goal is. etc. etc.), preferably an area for which you have a reliable text book (preferably more than one) that you understand. Otherwise the integrity of this site will suffer. --prime mover (talk) 00:44, 30 December 2012 (UTC)


The framework for induction here is very heavy. Thinking about it, I think the problem is the "inductive hypothesis" section. Unlike the other two sections, it is not itself a proof at all, although the format suggests it to be a lemma like the others. Identifying/naming the inductive hypothesis explicitly may be common in the first few exercises of some texts using it, but it's not actually a logically element of the proof. All you need, logically, to prove that $P(n)$ holds for each natural $n$ is to prove that $P(0)$ holds and that $\forall n \in \N_n: \bigl({ P(n) \implies P(n+1) }\bigr)$. The key to clarity, I believe, is to make sure there can be no confusion over the identities of $P$ and $n$. --Dfeuer (talk) 17:40, 8 March 2013 (UTC)

BLARGH. Someone (me) needs to look in some good texts that do a lot of induction and figure out exactly what it is that they do to avoid so much boilerplate. --Dfeuer (talk) 17:54, 8 March 2013 (UTC)
Absolutely nothing wrong with the way we present induction proofs. --prime mover (talk) 19:11, 8 March 2013 (UTC)
Brevity is the soul of wit. --William Shakespeare 1602
This site exists to give proofs with maximal rigour -- L_F, 2011. --prime mover (talk) 19:50, 8 March 2013 (UTC)
This is not about rigor; it's about language, and how best to express a rigorous proof.
I'm trying to ameliorate the problem expressed backwards in the improve template on Banach Fixed-Point Theorem. If we find more concise ways to express "full-blown induction proofs", we'll be able to use them more liberally.
The general form is:
Prove $P(n_0)$
Prove $P(n) \implies P(n+1)$ (or $P(n) \vdash P(n+1)$)
Invoke the principle of mathematical induction
In a tableau proof, you'd have a single line devoted to induction. The form on this page uses three subsections I believe a compromise would improve matters. --Dfeuer (talk) 20:09, 8 March 2013 (UTC)
I am trying to understand the source of your negative energy.
The usual reaction to meeting this website is: oh, cool, there's stuff on here I use at college. Oh look, there's some gaps I can fill. What's the house rules? Help out with getting my head round the presentation issues, guys.
Your reaction seems to be: what this website needs is to be completely rewritten to have my own personality stamped all over it.
As I do not share that point of view, I am afraid that any attempts you raise to change the way we do things just for the sake of changing them will be resisted by me. I fear I may not be alone in this.
If, of course, it is decided to follow the new style according to your suggestions, then until you, personally, have changed all the pages using induction to match the style you espouse, then every single edit that you perform from here on in will be deleted or reverted. It's a way of saying: don't hand out the work if you're not prepared to do some of it yourself. --prime mover (talk) 20:17, 8 March 2013 (UTC)
I am not suggesting they should all be changed. I am suggesting that more than one form can be used, depending on which is more suitable to the specific context. We have formal and informal proofs. We have proofs using text interspersed with equations and proofs using Template:Eqn. I just want to find a more concise option and make it available. --Dfeuer (talk) 20:22, 8 March 2013 (UTC)
Incidentally, why is this being discussed on L_F's page? I've moved it here instead. --prime mover (talk) 20:24, 8 March 2013 (UTC)
There's nothing to stop you writing an induction proof any which way you like. But as the lady said: are you gonna just talk about it all night? --prime mover (talk) 20:26, 8 March 2013 (UTC)
It indeed makes more sense (and is more visible) to discuss this here. @Dfeuer: Let me tell you a secret about PM. He likes for an idea to be put into action (in this case I personally suggest user space) rather than only being talked about. This also is much more likely to uncover any incompatibility in presuppositions between authors, thus reducing the probability of conflicts. This way of presenting ideas shows the reader both that the proposer has thought his idea through sufficiently as to implement it in some concrete situation, and makes it much easier to provide constructive criticism. Suggest you adhere (note to self: adhere yourself as well). — Lord_Farin (talk) 22:16, 8 March 2013 (UTC)

Alternative form

Given the Existence of Minimal Infinite Successor Set, the form of the Principle of Mathematical Induction that Halmos states (in quantified form) is

$\forall S\in\mathcal{P}(\omega)\,(\varnothing\in S \wedge \forall n\in S(n^+\in S) \Rightarrow S=\omega)$

is a consequence of $\omega$'s existence, its minimality property, and definition of set equality. I think its more immediate why the PMI applies to $\omega$ than to a Peano structure, as $\omega$'s existence has been demonstrated. Should we add this form? --Robertbiggs34 (talk) 21:16, 27 May 2013 (UTC)

What? The principle of mathematical induction is one of the Peano axioms. I don't see what you're getting at. --Dfeuer (talk) 21:25, 27 May 2013 (UTC)

Backup from Talk:Principle of Finite Induction

"As $S$ is well-ordered, and $T' \subseteq S$, it follows that $T'$ has a minimal element. Call this minimal element $x$." Should this just be based on the well ordering principle? --cynic 23:19, 30 September 2008 (UTC)

Not the way I see it, as the Well-Ordering Principle specifically refers to the set $\N$ of natural numbers. The Principle of Finite Induction is demonstrated on the naturally ordered semigroup before we've gone anywhere near defining what the natural numbers are, and in fact is used in the construction of the proofs that establish that $\N$ is a naturally ordered semigroup in the first place. To assume the well-ordering principle would make the argument circular.
The fact that the natural numbers are mentioned at the bottom is an explanatory amplification which is not germane to the proof itself but follows a lot later down the line after the set of natural numbers has been defined and proven to be a naturally ordered semigroup. --Prime.mover 06:09, 1 October 2008 (UTC)

On the proposed merge

L_F: I would be against a merge here, as the principles are effectively saying different things.

The page Principle of Finite Induction is defining the properties of a set: that if the first element is in the set then they all are.

The page Principle of Mathematical Induction is a higher level: it specifically discusses elements of the natural numbers for which a property holds.

The way this set of pages got crafted originally was that Principle of Finite Induction was used in order to develop the structure of the Natural Numbers (either from Naturally Ordered Semigroups or the Peano Axioms -- or both) and then having done so, showing that $\N$ had those same properties.

Then Principle of Mathematical Induction takes that principle as a proven entity and uses it to allow the proof of propositions which have elements of $\N$ as a parameter.

I thought it was a good idea to divorce the set-theoretical version of this from the more general mathematical version, so as to allow "conventional" mathematical work to progress without getting the user bogged down in the specialised set-theoretical jargon that exists in Principle of Finite Induction. --prime mover (talk) 22:33, 19 April 2014 (UTC)

I understand that. However I do think it's wrong to have different names for what is essentially the same thing, looked at from different axiomatisations.
The whole concept of a "proof" of induction is void when taking PA as axiomatic. OTOH, it is evidently necessary for other axiomatisations and constructions.
Invariably the induction pages will be part of the exercise I'm going through, so in the mean time, please just read the merge request as a reminder for me that the two pages are actually talking about the same thing.
In the end, I predict the usual paradigm: modularity and transclusion. I can see it crystallize already in my mind, but I'll have to spend more time on preparing the various approaches to $\N$ for the exercise. — Lord_Farin (talk) 22:50, 19 April 2014 (UTC)
Okay no worries, treat the above as an explanation for the original structuring. Yes I know that PoI is already built into PA, but when I first attacked this I came in via the Natural Ordered Semigroup direction, because that was what my at the time limited library yielded. --prime mover (talk) 23:03, 19 April 2014 (UTC)

The more I look at this, the more I am convinced that it makes sense to differentiate between Principle of Mathematical Induction and Principle of Finite Induction by name.

a) It's convenient. You can directly link to whichever you want, without having to ask the question: do I need the "predicate" or "set" version of this?
b) The names are accessible and backed up by literature. Many of the books that analyse the two forms in detail tend to use principle of finite induction.
c) It provides a convenient springboard to allow a smooth progression to Definition:Principle of Transfinite Induction, which is work in progress.

Hence a lovely fiddly renaming operation is going to progress.--prime mover (talk) 02:57, 18 April 2019 (EDT)

New refactoring task

Never been happy with the existing Induction framework so I'm going to try restructuring it. --prime mover (talk) 02:06, 16 April 2019 (EDT)

I am going to set up a new page Definition:Mathematical Induction, which will be an overall top-level page which will contain links and/or transclusions of all the variants, so as to be the one-stop shop for all your induction needs. --prime mover (talk) 02:57, 18 April 2019 (EDT)
I support all your efforts! Well done! — Lord_Farin (talk) 08:46, 26 April 2019 (EDT)
Thank you for your endorsement -- it feels more logically structured and modular and easier to use now. A great deal of effort goes into making the site look effortless. --prime mover (talk) 12:21, 26 April 2019 (EDT)

True that! The hardships to make things look easy! Additionally, the clearest insights are somehow always progressive insights, which while frustrating due to the feeling of surplus work, is also rewarding in itself due to the greater innate beauty achieved. — Lord_Farin (talk) 14:48, 29 April 2019 (EDT)