Talk:Mathematical induction

Older discussion is at /Archive

Prefix induction

Today, I happend to read the section Mathematical_induction#Prefix induction, which mainly talks about issues in computational complexity theory. For the latter reason, I think it better belongs to an article about recursion. In mathematical induction, it is pointless to count the "number of applications" of the induction step that is needed to arrive at P(n); there isn't even a notion like "applying the induction step". In analyzing the computational complexity of a recursive program, on the other hand, the number of recursive calls does matter. - Any suggestions on what to do with this section are welcome. - Jochen Burghardt (talk) 10:54, 11 April 2017 (UTC)

Logical and mathematical induction

Commenting on this edit and the subsequent revert.

Jochen's edit summary, when reverting, said that the "distinction between mathematical and philosophical induction should be mentioned", with which I agree. But I think it is already mentioned; indeed, the paragraph starts with an explanation that mathematical induction is not the same as inductive reasoning. I have to say that 2600:387:3:805:0:0:0:AF's version reads cleaner to me, and the version to which Jochen reverted strikes me as a bit repetitive. --Trovatore (talk) 07:57, 28 September 2017 (UTC)

This was my change. Not only is the distinction mentioned, but as I wrote in my edit comment, mathematics uses inductive reasoning constantly at all levels. This page is clearly designed to be useful to students learning what it is to do a mathematical proof, and it's disingenuous to communicate to them that the art of proof is a purely deductive one. - ‎ 2601:143:8201:1f52:e460:7d69:aa55:5ffc, 28 September 2017

My yesterday revert was too hasty, please apologize. I should have read the surrounding paragraph text and recognize the redundancy, but I didn't. - Concerning the use of inductive reasoning, I agree with by 2600:387:3:805:0:0:0:AF that find a proof usually does require it. The motivation for my revert was that teh article should be clear about the complete absence of inductive reasoning in a completed mathematical proof. The latter point is made clear by the current version, but the former is not. I agree with 2600:387:3:805:0:0:0:AF it should be explained in some wikipedia article. Should we add a footnote here, or would that be too distracting? - Jochen Burghardt (talk) 11:50, 29 September 2017 (UTC)

A question appears in the context of the above: What is the status of proof by exhaustion? Isn't it a form of inductive reasoning?--109.166.136.245 (talk) 12:24, 10 August 2019 (UTC)

I respectfully disagree that a completed mathematical proof is marked by the "complete absence of inductive reasoning" -- if a proof requires it, as you say, it's impossible to excise. The extent to which a proof is complete-in-itself or embedded within a culture is a significant sociological question dating back to at least Russell and Whitehead. My opinion is that it's not really in the interest of this article to address it, especially since there are already links to inductive reasoning and the problem of induction.— Preceding unsigned comment added by 128.8.206.15 (talk • contribs) 15:25, 29 September 2017 (UTC)

I see this section and I think that the article should underline the status of infinite (number of cases) complete induction of math induction in contrast with finite number of cases complete induction represented by proof by exhaustion.--5.2.200.163 (talk) 14:22, 19 January 2018 (UTC)

---

Another thought: what about Borwein integral? It is a nice example of inductive reasoning failure. Worth to be mentioned here? If only in "See also" with an appropriate comment? Do you know any more impressive case? Boris Tsirelson (talk) 07:17, 21 November 2019 (UTC)

Mathematical induction and Modus ponens

What is the connection between mathematical induction and the inference rule modus ponens? 213.233.84.61 (talk) 11:40, 19 December 2017 (UTC)

That is this type of reasoning as repeated or chain modus ponens? 213.233.84.61 (talk) 11:45, 19 December 2017 (UTC)

Modus ponens is a form of reasoning most famously described and named by Aristotle around 500 BC. It goes from the universal to the particular. If a statement is always true, then it is true in each particular case. Mathematical induction is a distinct form of mathematical reasoning. It may have been implicitly understood by some ancient mathematicians, but in its modern form it was most famously described and named by Giuseppe Peano around 1900. Induction, like every mathematical proof, may make use of modus ponens, but it does not in general go from the universal to the particular, but rather from one particular case to the next particular case. It can be summarized thus: if as statement is true in the first case, and if each particular case implies the next particular case, then it is true for all enumerated cases. Rick Norwood (talk) 12:47, 19 December 2017 (UTC)

Particular is not so particular, just individual. It corresponds to singular categorical propositions, also identified by Aristotle and has an individual notion as subject. — Preceding unsigned comment added by 213.233.84.85 (talk) 11:26, 20 December 2017 (UTC)

It can be said that without modus ponens, there is no math induction. Mathematical induction is a chain/cascade modus ponens, similar in chaining to the concept of chain reaction.--5.2.200.163 (talk) 14:36, 17 January 2018 (UTC)

ZFC set theory

@Golopotw: Can you provide any references for this paragraph that you added to this article? Jarble ;(talk) 23:43, 27 December 2017 (UTC)

Sorry, I cannot find any reference. I learnt the claim from Math Stackexchange[1]. Golopotw (talk) 06:23, 28 December 2017 (UTC)

Clarification for intro - link between the truth value of (some) sentences and natural numbers

There is a very unclear phrasing in intro at the second sentence which says that this inference scheme ″establish statements for all natural numbers″. What is the explicite link between the truth values of some sentences and natural numbers?) is what needs clarification and expliciteness.--5.2.200.163 (talk) 14:14, 17 January 2018 (UTC)

Counter - word use (in a section but not in the lede)

I also that the word counter is used in a (sub)section where it mentions several counters instead of only one/1, in standard variant. Could it be that this word counter is what is needed to clarify the aspect mentioned in the previous section of this talk page?--5.2.200.163 (talk) 14:23, 17 January 2018 (UTC)

Connection of this notion to enumerative induction (and case-based reasoning)

Another aspect that needs a less implicite phrasing is the connection between math induction to enumerative induction (and modus ponens), namely the status of math induction as infinite enumerative induction and also a complete induction by infiniteness instead of ordinary complete induction where the set of all cases to analyze has a rather small cardinality.--5.2.200.163 (talk) 14:32, 17 January 2018 (UTC)

Too soon word use in intro

Also the mentioning of well-ordered set in the first 2 sentences of intro is not useful for clarity of the notion. This further notion is too technical to be mentioned in the first sentences of the article! Thoughts?--5.2.200.163 (talk) 14:43, 17 January 2018 (UTC)

Revert of 5.2.200.163's edits of 16 Jan 2018

As requested on my talk page, here are my reasons for reverting 5.2.200.163's edits of 16 Jan 2018.

• Most commonly, it is used to establish statements from individual cases being true to an unlimited number of cases indexed by for the set of all natural numbers.

The word "case" refers proof obligations ("base case", "inductive case") in the article and in common literature, including the cited mathisfun page. In 5.2.200.163's version, it refers to natural numbers, or propositions involving natural numbers. This is a likely source of confusion. Another confusion is the appearance of both quantifiers "unlimited" and "all" in the sentence.

• It is sometimes desirable to prove a statement involving two counters indexed by natural numbers,

The paragraph is about induction on two or more variables. The latter were somewhat sloppily called "counters" in the text (I'd suggest to change that to "variables" consistently). However, they are not "indexed" by anything.

• In the See also section: Enumerative induction, Modus ponens

Mathematical induction has already been delimitated from inductive reasoning in the lead. There is no need to mention Enumerative induction again. (Both pages are currently under consideration for a merge).

I haven't any idea why Modus ponens should be linked here. It is a (un)related to mathematical induction as any other inference rule mlisted e.g. at Propositional calculus#Basic and derived argument forms.

Best regards - Jochen Burghardt (talk) 18:34, 17 January 2018 (UTC)

Re the delimitation of math induction from inductive reasoning, this is not very clear, convincing and sufficiently detailed neither in the lead nor in the article. This aspect requires further details to be clarified and added to article. Among these details are, of course, those that underlines the connection of math induction to modus ponens, proof by exhaustion aka complete (enumerative) induction in either finite or infinite number of cases.--5.2.200.163 (talk) 15:04, 18 January 2018 (UTC)

I agree with Jochen Burghardt. The changes made by 5.2.163 were unclear.Rick Norwood (talk) 19:40, 18 January 2018 (UTC)

Please indicate concrete examples of wording to improve clarity about the above mentioned aspects re the delimitation of math ind from inductive reasoning, explaining clearly why math ind is a deductive inference scheme rather than an inductive one, as could appear at first glance. These specifications are a very useful addition to the content of this article.--5.2.200.163 (talk) 13:38, 19 January 2018 (UTC)

It is up to the individual making the changes to write clearly. Other Wikipedians should not be expected to do the rewrites necessary to bring the post up to an encyclopedic level. I'll just give one example. Your most recent edit added "proof by exhaustion" to the list of "See also" articles. I do not know of any reference that considers "proof by exhaustion" a form of mathematical induction. Also note that in "mathematical induction" the adjective "mathematical" is not capitalized unless it is the first word in a sentence. Rick Norwood (talk) 13:17, 20 January 2018 (UTC)

I never said/implied that proof by exhaustion is a form of mathematical induction, just a finite complete enumerative induction. Unlike proof by exhaustion, mathematical induction is a form of a ′′infinite′′ (number of cases) complete induction. So ″both″ math ind and pbe are examples of ″complete induction″, either finite or infinite. I′ll insert these specifying sentences about the types of complete induction which I hope are very clear.--5.2.200.163 (talk) 17:28, 23 January 2018 (UTC)

If you insert information into the article, please supply a reference that says it is pertinent.Rick Norwood (talk) 11:55, 24 January 2018 (UTC)

"Course-of-values induction"

As an engineering student with some knowledge of mathematics, this stood out to me as a phrase that seems to have been literally translated from some other language, and indeed not long after introducing the term (and confusingly comparing it to a different term in German, for some reason?) the article switches to using the term "complete induction" to describe this particular method. A cursory glance around at references shows that Wolfram Mathworld uses the term "strong induction", and out of the three terms, "complete induction" has the most hits (2372) on math.stackexchange.com, with "strong induction" not far behind (1729 results), and "course-of-values induction" trailing by far with little more than a tenth as many (243 results).

I propose that the section title and references to the method in this article be changed to primarily use the term "complete induction", as it is the one I am familiar with and the one with the most search results on stackexchange, not to mention being the one half the article already uses. However, rather than edit this myself, I would like to request opinions of others, as I can see a strong case for "strong induction", and someone might have a good reason to keep "course-of-values induction". Are there any mathematicians here who can chime in on what they know the method as?

Additionally, I have looked at the page history (as this does look strange enough to wonder about) and I noticed that the article used to use the term "complete induction" throughout, before this edit, wherein the editor claims to have "Corrected the misnomers for course-of-values induction". No other editor seems to have significantly touched this section of the page. Xolroc (talk) 03:28, 20 February 2018 (UTC)

As I did the last edits especially to this paragraph, I feel addressed to reply.

To me there is essentially just one "mathematical induction" ("Vollständige Induktion" in German) as a method of proof. To distinguish the two flavours "weak" and "strong" is not of interest for applying the method (always assume the more convenient inductive hypothesis to hold), since their equivalence is straightforward to show. Of course one may scrutinize the "mathematical induction" itself and look for some minimal hypothesis, for its relation to other concepts (more-dimensional, backwards, transfinite, recursion!), and -foundationally- to its formal validity in a certain formal logic setting (first, second order, axiom scheme, ...). I came here just by chance, and tried to repair claims I considered as flawed, but clinging as much as possible to the given content (preserving "course-of-value"), since I do not dare to set the framing of this article.

The pinpointed edit by an IP-editor is a solitary contribution to WP, and I am not interested to refute it on a "reliably sourced basis", but I suppose it is based on a misconception of the term "rekursion"(bolded in my edit) as used by Peter and the IP's understanding of "induction". BTW, the hint to a "famous textbook" by Peter, besides being editorializing, is somewhat apocryphal, but I will not dispute that Peter mentioned the insinuated claim somewhere. Purgy (talk) 08:01, 20 February 2018 (UTC)

I do not necessarily have any quarrel with the content the anonymous editor added, merely the terminology. It's inconsistent with the following section of the article, and it appears to be a rare term for the method (at least in English). I also don't dispute that the weak and strong methods are equivalent, but there is value in mentioning both.

I didn't intend to claim anything about the other editors who cleaned up that initial edit; you were doing good work making the content more legible and better-sourced! I apologise for any offense I may have caused.

To be clear, my main problems with the page as it stands are as follows:

• The term "course-of-values induction" is introduced and used primarily for a few paragraphs, but then the article abruptly switches to using "complete induction" for the same concept
• The reference to the term in Peter's textbook seems like it would better belong in the "History" section of the page
• The term "course-of-values induction" is treated as the most correct or most common form of the concept, while actual usage in a community of math learners and educators (stackexchange) and a well-respected resource (Wolfram Mathworld) disagrees. (This makes the article harder to parse, as one might not recognise the uncommon and thus unfamiliar name for the concept)
  • Further, the article seems to treat the common term "complete induction" as a minor or rarely used term, saying it "might be a good idea" to use the term as though it were a proposal and nothing more.

Xolroc (talk) 16:53, 20 February 2018 (UTC)

I believe that the terminology in this section should be returned to complete induction in accordance with Wikipedia:COMMONNAME. The fact that "course of values" is a better translation of the German term is of no consequence in English Wikipedia. Also, the two references that were given are not appropriate. One links to a Wikipedia page that doesn't support the claim and the other is to an ad. A small historical note about the connection to recursion theory would be all that's needed for any of this additional material. While Purgy is correct about the equivalence, in almost all the English texts that cover this material (introductory proof texts), the methods are brought up as separate and then the equivalence is proved. We should treat it the same way. --Bill Cherowitzo (talk) 00:03, 21 February 2018 (UTC)

My knowledge of the English sources does not suffice to exclude "course-of-values" and to exclusively support either "mathematical" or "complete" induction. That's why I only rudimentarily reverted the IP's edit, which I have a lot to quarrel with from my view. In any case (I reverted this!) "course of value" does not translate to "vollständig" (according to IP), but "complete" does (as I hinted to). In my perception (irrelevant to WP!) "mathematical" is the most frequently used term in math print, and "complete" might result from "vollständig" (see also Schubfach/Taubenschlag in "pidgeon hole principle" for intricate effects of translations, also mostly irrelevant to WP). Additionally I think that the IP's remark on not proving the base case is highly suspicious.

In no way I oppose to introducing the terms "strong" and "weak" (they deserve a comment of where exactly the epitheta belong and to what property they refer), and I had subsumed this detail in my consideration about "scrutinizing the 'mathematical induction' itself" to an even higher degree in my first comment above.

The references to Peter were also introduced by the IP, and to my suspicion are based on a mix up of recursion and induction by the IP. I cannot comment on the re-introduction of this ref.

@Xolroc, I do not feel offended in the slightest way, but I rather thank you for your nice words about my edit. :) Purgy (talk) 09:07, 21 February 2018 (UTC)

Well-founded relations?

I think that the last edits by a knowledgeable editor introduced a new entry level to the content of this article - and it is not a lower one. While I certainly do not object to adding higher levels in an article,especially later on, I want to ask, if the newly achieved generalizations, already in the lead, are advantageous for the expected readership. Maybe, changing in the lead from the structure of naturals to well-founded relations on a set erects a barrage that degrades the accessibility of the whole article. Purgy (talk) 12:47, 13 March 2018 (UTC)

I agree - the new, more general material should be postponed until later in the article. The beginning should focus just on induction for the natural numbers, which is the most important subject for this particular article. — Carl (CBM · talk) 14:16, 13 March 2018 (UTC)

I think induction on general wellfounded relations is most naturally treated at transfinite induction. We could have a brief summary here, with a {{main article}} link. Of course it works even for finite relations, but that's a detail — readers who want to get that involved might as well deal with it in the transfinite context, as it is not really any harder. --Trovatore (talk) 02:43, 14 March 2018 (UTC)

I have simplified the lede a little bit today in light of this thread. I think that it could be improved a little more, over time. — Carl (CBM · talk) 11:08, 16 March 2018 (UTC)

Well, honestly, ... I think you dumbed it down to almost nothing, depriving it of almost all perspectives. Purgy (talk) 11:20, 16 March 2018 (UTC)

What "perspectives" do you mean? The far most important perspective on induction is that it is used to prove facts about the naturals. The lede still says something about structural induction in third paragraph. — Carl (CBM · talk) 11:47, 16 March 2018 (UTC)

Some of what I subsumed under perspectives was contained in the IP's (CP. Wirth?) edits. I am just not that much after eradicating of all his traces. When I am well hidden, I dare to think about a less petrified WP, math-wise. :| Purgy (talk) 08:24, 17 March 2018 (UTC)

Theorem of Noetherian Induction

This section has been removed from the article, but is still mentioned in the section on strong induction as if it were still in the article. That is a problem that often occurs when entire sections are deleted. If you delete a section, I recommend you do a search to find any references to the deleted section. Is Theorem of Noetherian Induction important? I don't know, but either put it back or take out the reference to it. Rick Norwood (talk) 19:03, 16 March 2018 (UTC)

Thanks, I hadn't realized that section had been edited so much. Of course the goal is for everything to work together. I was trying to minimize the amount of direct reverting, which was harder than I thought given the nature of the IP edits that I was looking at. I don't think "Noetherian induction" is of high prominence, although a separate short section could be written to give it a mention. — Carl (CBM · talk) 22:51, 16 March 2018 (UTC)

Example: forming dollar amounts by coins

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

---

This example excludes n < 12 because the proposition to be proven fails for n = 11.

However, the proposition is true for n = 8, 9, or 10.

The given proof by induction does not employ the restriction that n > 11. Therefore, the base case can start with 8, with 9 or with 10 and the step case can proceed and yield the same valid proof.

True n = 11 is a valid counterexample. But this is only pure coincidence/luck that this counterexample is so easy to detect and avoid.

This example raises a more serious issue:

• How does mathematical induction principle addresses a possible situation in which a counterexample exists for some n that is yet to be discovered?

• And further, how can it guarantee that no such n exist? — Preceding unsigned comment added by UriGeva (talk • contribs) 01:26, 16 February 2019 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

Nevertheless, I used this objection to add a remark in the article, stating that there is no similar induction proof for an n smaller than 12. More general, if a formally valid induction proof has been performed, there cannot be a counterexample. - Jochen Burghardt (talk) 08:32, 16 February 2019 (UTC)

Measure Theoretic Induction/Standard Machine

Should the proof technique of extending a result inductively to all functions (first by showing the result for indicators and then linear combinations of indicators (simple functions), then to monotone increasing functions, and finally to all negative and positive functions) be included here or in its own article?Aaronjaneiro (talk) 02:47, 4 March 2019 (UTC)

Please, add new threads at the bottom, it's WP-standard. (Use tab "New section" in top bar) Purgy (talk) 08:29, 4 March 2019 (UTC)

Significance of n in P(n)

What exactly is the significance of n in P(n)? The wording in the article is unclear on the nature of the n variable from a logical perspective. If a property P is considered as a monadic predicate which has an associated universe set of individual constants which bound the object variable x of the predicate P(x), how does n relate to x?--185.53.196.147 (talk) 02:12, 10 August 2019 (UTC)

I see these comments re the status of n and I think it can be statele that n is a variable associated to sequences, namely the number of order of the elements of a sequence. Then the properties depending on n, P(n), is actually a sequence of properties P(x_n), n as variable having as set of values the set of natural numbers. Thus P(x_n) as an explicite predicate variable has as universe set (or universe of discourse) the set of natural numbers as the set of individual constants for the range of the universal quantifier tacitly present in the usual form P(n) of the property P.--109.166.136.245 (talk) 12:55, 10 August 2019 (UTC)

Thanks for reaching out. Unfortunately, this is outside of my expertise -- the subtleties in the logical foundations of induction are not something I've put much thought into. I think about induction naively as a consequence of the defining properties of the natural numbers (Peano axiom #9), but I've never really thought about its foundations in logic. Someone around here will certainly have some insight. Alsosaid1987 (talk) 15:47, 10 August 2019 (UTC)

I undid the 10 Aug edits of 109.166.136.245. Imo, neither the question of 185.53.196.147 nor the answer of 109.166.136.245 makes much sense from a formal logic point of view. If there is an issue at all, it shouldn't be discussed in the article's lead section. Section "Formalization" seems more appropriate, and I think it is sufficiently clear about P. - Jochen Burghardt (talk) 08:13, 14 August 2019 (UTC)

Subsets of natural numbers

The article says that the studied property holds for every natural number. Is this mandatory? Couldn't the property P hold only for subsets of natural number like the even or odd naturals or the multiples of 3, or the set of prime numbers...?--185.53.197.197 (talk) 23:39, 13 September 2019 (UTC)

Structural induction can be used for this; it just needs a well-ordering on the set under consideration. Induction on natural numbers is (I believe to remeber) its historical precursor, and a special case. - Jochen Burghardt (talk) 07:04, 14 September 2019 (UTC)

Well-ordering absolutely required or something else but related? I see that the linked article says something about a recursively defined structure! I see that well-ordering has a requirement of a least element. This brings the question of validity of math induction in sets without least element, but with a recursively defined structure.--185.53.198.164 (talk) 17:12, 14 September 2019 (UTC)

I never saw the word "induction" used for the latter. To prove, e.g., that each integer x satsfies some property p(x), an ordinary induction on the absolute value of x might be appropriate; in this case, ℤ is mapped (by abs(.)) to a well-founded set, viz. ℕ. On the other hand, "generalizing" structural induction to the non-well-founded (w.r.t. its usual order) set ℤ by omitting the base case, would allow one to prove a lot of false statements, like "each x∈ℤ is both odd and even": it is well-known that if x is both odd and even, then x+1 is both even and odd, respectively. Also, in a computer-science sense, recursion always requires some base cases (minimal elements of a well-ordered set) in order to avoid endless-recursion. - Jochen Burghardt (talk) 17:43, 14 September 2019 (UTC)

I'm not saying that a generalization should have no base cases. For instance when considering the extension of ordinary factorial (which has the property of recursivity) to negative integers the base case could be 0! like in the case of usual factorial or -1 as the additive inverse (a sort of a mirror image) of the number 1. So the factorial has two possible variants of extension in integers: 1) the mirror image of the positive integers factorial (with possibly the same base case as ordinary factorial), 2) the bidirectional factorial as product of the usual factorial of positive integers and negative integers factorial, the two factorials possibly starting from the same base (0!) case but in opposite ways.--185.53.198.164 (talk) 19:38, 14 September 2019 (UTC)

Interesting remark about the involvement of absolute value, this seems to be an equivalent formulation to the informal mirror image label. On the page integer I notice that this set has a total order. Could this be sufficient for integers instead of well-ordering, without lack of base case(s)?--185.53.198.164 (talk) 19:46, 14 September 2019 (UTC)

These aspects about integers can be discussed in a separate section below.--185.53.198.164 (talk) 19:52, 14 September 2019 (UTC)

Please see WP:NOTFORUM -- the purpose of this page is to discuss the article, not the subject of the article. --JBL (talk) 21:05, 14 September 2019 (UTC)

I have opened the discussion with the intent of subsequent additions/modifications to article.--185.53.198.164 (talk) 21:29, 14 September 2019 (UTC)

In that case please see our policy on original research. --JBL (talk) 23:12, 14 September 2019 (UTC)

Perhaps there are some modifications which are below the originality threshold which would need a citation. There remains to be seen.--185.53.198.164 (talk) 00:46, 15 September 2019 (UTC)

Induction on the integers

Some aspects having occured in the previous section re the induction on the integers (without omitting base case, well-ordering and total order, etc) can be further analyzed here.--185.53.198.164 (talk) 19:56, 14 September 2019 (UTC)

In order to modify/edit the article after the result of the discussion.--185.53.198.164 (talk) 21:32, 14 September 2019 (UTC)

Suggestion for mathematical terminology in lead

The intro definition can include some more maths jargon to refine the notion. Eg, "Mathematical induction is used to infer if a function f(n) is defined on the set of natural numbers as its domain" or something like that. How'd that be? This also can be made a parenthetical statement. It just seems too informal at this point hence this proposition. Akshay Aher (talk) 15:16, 22 September 2019 (UTC)

The property P(n) mentioned in the lead could be e.g. "n belongs to the domain of f"; this way, your example is covered by the lead. - Jochen Burghardt (talk) 16:30, 22 September 2019 (UTC)

What is the involvement of n as argument of the function(s) f(n) or P(n) of math induction? Is it a variable or just a dummy variable, a placeholder of some sort? --93.122.249.16 (talk) 17:50, 4 October 2019 (UTC)

I see that below an ordered proposition set is mentioned, the ordering of the proposition being done with numbers of order from the ordered set {0, 1, 2, 3,....n}. This seems to indicate that n is just a number of order.--93.122.249.16 (talk) 18:17, 4 October 2019 (UTC)

Suggestion of addition from Portuguese version of this article

I see that on the Portuguese version of this article there is a statement which could be translated and inserted here. The statement is: Indução matemática é um método de prova matemática usado para demonstrar a verdade de um número infinito de proposições. --2A02:2F07:D5FF:FFFF:0:0:6478:4403 (talk) 14:08, 30 September 2019 (UTC) Translation: Mathematical induction is a method of mathematical proof used for proving the truth of an infinite number of propositions.--2A02:2F07:D5FF:FFFF:0:0:6478:4403 (talk) 14:12, 30 September 2019 (UTC)

The Portuguese sentence is too unspecific. Induction (in its basic form) can be used only if the proposition set has the form { p(0), p(1), p(2), p(3), ... }. This is already said in the lead. - Jochen Burghardt (talk) 18:38, 30 September 2019 (UTC)

I see this discussion and that above and a question appears: What is the nature and involvement of enumeration 0,1,2,3,..... in the mentioned proposition set {p(0), p(1), p(2)...p(i)..} Is this proposition set an ordered set? --93.122.249.16 (talk) 18:05, 4 October 2019 (UTC)

Chain of succesive implications p(1)→p(2)→.....p(k)→p(k+1)→...p(n)

The structure of this type of reasoning (having a base/start case and (successive) inductive case(s)) can be noticed that it is is based on the following chain of implications:

If p(1), then p(2) notation ($p(1)\to p(2)$)

p(1)

Therefore, p(2)

........... ........... ...........

If p(k), then p(k+1) notation ($p(k)\to p(k+1)$)

p(k).

Therefore, p(k+1)

........... ...........

Therefore, p(n), ...

(Symbolized with logical operator operator notation,

$p(1)\to p(2),$

$p(1)$

$\vdash p(2)$

$p(2)\to p(3),$

$p(2)$

$\vdash p(3)$

............

$p(k)\to p(k+1),$

$p(k)$

$\vdash p(k+1)$

............

$p(n-1)\to p(n),$

$p(n-1)$

$\vdash p(n)$,...)

I think that this aspect re the chain of forward reasoning should be mentioned in article.--37.251.221.82 (talk) 11:32, 2 October 2019 (UTC)

I see that the inductive step has the structure of succesive implication P(k)→P(k+1), given P(k). This should be in article.--86.127.33.116 (talk) 12:10, 30 November 2020 (UTC)

Number of order? - {0, 1, 2, 3,... n}

Some aspects from above sections point to the conclusion that n (in P(n)) as a variable is just a number of order for an ordered proposition set {p(0), p(1), p(2),.....,p(n)}. Is this a valid understanding?--93.122.249.16 (talk) 18:35, 4 October 2019 (UTC)

To reply to this and to your above question: yes, I think, the proposition set could be made an ordered set. However, I don't remember to have seen this somewhere in a book, and I can't imagine that it would lead to new insights. Note that, beyond being ordered, all members of the set must be of the form "p of someting", for a fixed property p. - Jochen Burghardt (talk) 05:59, 5 October 2019 (UTC)

I see this discution and I think that distinct symbols p(i) and P(x(i)) are needed. p(i) is a proposition from the ordered set {p(0), p(1), p(2), .......} and P is the symbol of the predicate letter from the structure of the ordered set of propositions p_i. The ordering of the propositions p_i is given by the succesive implication p(i) →p (i+1), mentioned in a section above.--109.166.135.99 (talk) 15:23, 4 January 2020 (UTC)

This distinction is important in cases when the numbering of propositions is different than the value of variable depending on the index in the predicate formula P(x_i), such as in the examples of subsets of natural numbers like even or odd, multiples of 3, etc.--109.166.135.99 (talk) 17:02, 4 January 2020 (UTC)

For instance the sum xⁿ + aⁿ is divisible by the sum x + a for every odd n. In this example n takes values in a subset of N, the odd positive integers.--109.166.135.99 (talk) 17:33, 4 January 2020 (UTC)

The predicate expression is E(x_n) D(ivisible by) (x + a), E(x_n) = xⁿ + aⁿ and the whole expression E(x_n) D (x + a) can be denoted P(x_n) or D(x_n).--109.166.135.99 (talk) 17:51, 4 January 2020 (UTC)

The order number of proposition in this example (re divisibility) can be every value from {0, 1, 2, 3, 4, 5,.....}, but the order number of the predicate formula is from {1, 3, 5, 7, 9, 11, ....2k + 1}.--109.166.135.99 (talk) 18:06, 4 January 2020 (UTC)

The structure of the inductive step as implication/conditional sentence

I think that implicational structure/nature of the inductive step should be stated in article.--86.127.33.116 (talk) 12:15, 30 November 2020 (UTC)

Level of this article

It has been claimed that the level of this article is only school-level introductory and as a consequence some logical notions appearing in the structure of this reasoning method should not be linked. I think this claim of just introductory level is unfounded or problematic.--86.127.32.116 (talk) 00:41, 1 December 2020 (UTC)

Problematic in the sense that the level varies (as is typical for many articles; we want the introductory stuff first and more technical parts later per WP:TECHNICAL), problematic in the sense that some passages (which ones?) are not written in as introductory a level as they should be, or problematic in that you reject the idea that making articles as readable as possible is a good idea? Be specific. —David Eppstein (talk) 01:28, 1 December 2020 (UTC)

I agree with the variation of level as typically/usually done for many articles. In this context the questionable/problematic aspect is the exclusion of aspects considered more technical based on self-limitation of the article only to presumed introductory aspects.--86.127.34.116 (talk) 03:00, 1 December 2020 (UTC)

As a consequence of the previous paragraph at least a question appears: Are the logical aspects mentioned in a previous section above (and on an user talk page) considered non-introductory or more technical? If yes, what is the frame that considers logical aspects as non-introductory?--86.127.34.116 (talk) 03:08, 1 December 2020 (UTC)

(The mentioned user talk is: User_talk:Jochen_Burghardt#Unneeded_links_(at_mathematical_induction)?)--86.124.195.101 (talk) 00:34, 2 December 2020 (UTC)

Euclid and mathematical induction

@Jochen Burghardt: Hey, i have no problem with mentioning Euclid in the history section, but as i said in my edit summary, the cited source nowhere mentions him as an early user of mathematical induction. The current version is therefore WP:OR and WP:POV. Please let me know if you think i'm mistaken. Best.---Wikaviani ^{(talk) (contribs)} 10:54, 13 January 2021 (UTC)

What's more, the text explicitly refers to the proof of the infinitude of primes. That proof is not a proof by induction, but a proof by contradiction from the assumption that there is a finite number of primes. 85.156.129.147 (talk) 18:31, 21 January 2021 (UTC)

@Wikaviani: I consider Euclid's proof as an induction on n to show "for all n, if ≥n distinct primes exist, then ≥n+1 distinct primes exist". Maybe you are right in that Euclid's phrasing is not too clear a use of induction. - Jochen Burghardt (talk) 20:33, 21 January 2021 (UTC)

@Jochen Burghardt: Hi, thanks for your response. Euclid's proof is all but a proof by contradiction (as the IP said above too), since he supposed that there is a finite number of prime numbers and then he found an argument that contradicts that point (no "initialization" of the process and no "heredity" either). Also, i checked the cited source (and others), Euclid's proof is not considered to be a use of mathematical induction (example : [2]). Therefore, the history section needs to be reworded and, in my humble opinion, Euclid's proof removed from it.---Wikaviani ^{(talk) (contribs)} 20:45, 21 January 2021 (UTC)

It is not a proof by contradiction. It is a direct proof that, for any finite set of primes, there are additional primes not in the set. But I agree that it is also not induction. Much closer is Euclid VII.2 (the GCD algorithm), which Euclid only takes to a finite number of steps, leaving the jump from that to an arbitrary number of steps to the reader. In any case we should base the history on reliable sources on the history of mathematics, not our own interpretation of historical sources and also I think for this not popular-mathematics sources that are likely to get it wrong. —David Eppstein (talk) 21:10, 21 January 2021 (UTC)

It's much closer to a proof by contradiction than to mathematical induction for the least. Also, from the beginning of this thread, i'm saying that we should go by what the sources say, instead of what we think. Euclid's proof is said to be be a proof by contradiction in many reliable sources, you can check the one i linked above or this one, in French : [3].---Wikaviani ^{(talk) (contribs)} 21:32, 21 January 2021 (UTC)

You did see the "Euclid's argument was different, but" disclaimer on your first link, no? And the similar note about "énoncés plus modernes" in your second link, which looks to me more like a student essay than a published scholarly work in the history of mathematics? —David Eppstein (talk) 21:42, 21 January 2021 (UTC)

Euclid's argument was slightly different, that's sure, since his proof goes back to 2300 years. Also, please pay attention to whom the second source is from : [4], IREM are the Mathematics Education Research Institutes of France, the source says "EUCLIDE a mis à l'honneur un type de raisonnement très puissant, le raisonnement par l'absurde. En voici un exemple à cette occasion."---Wikaviani ^{(talk) (contribs)} 22:05, 21 January 2021 (UTC)

Sorry to come late to this discussion. David Eppstein is correct when he says that Euclid's proof is constructive. He starts with three primes and constructs a fourth prime that is not one of them. From this he concludes that there is an infinitude of primes. Today we would say that in order to make this inference rigorous we should use mathematical induction, using Euclid's construction to prove the inductive step. It is quite ahistorical to claim that Euclid used induction, in fact, his thought process is unknown. I agree with Wikaviani's edit that removed this statement. There are many published sources, some by quite well known mathematicians, that claim this is a proof by contradiction. While the proof can be rephrased as a contradiction proof, it is clearly a constructive proof as Euclid wrote it. These claims have to be rejected on the grounds that they run counter to his clearly stated proof.--Bill Cherowitzo (talk) 21:12, 22 January 2021 (UTC)

I think that the first time I saw "Euclid's" proof, in whatever book I found as a kid, it was presented as a proof by contradiction. But I suspect that was more indicative of pop math copying other pop math, without any connection to history. XOR'easter (talk) 05:04, 24 January 2021 (UTC)

I'm even later than Bill here, but I think it's reasonable to call the most common presentation a proof by contradiction. It's true that it doesn't have to be viewed that way.

But the claim that the proof "constructs" a prime not in the original set is true only in a fairly non-obvious sense. It doesn't give you a formula for such a prime. It does give you an upper bound on such a prime, so you can find it by exhaustive search over a finite set using an algorithm guaranteed to terminate (though it might take a long time).

That's enough to make the proof "constructive" in some technical sense. The easiest way to understand it, though, is still as a proof by contradiction. --Trovatore (talk) 00:35, 18 April 2021 (UTC)

Ok, but that's someone else's presentation of Euclid's proof, rather than Euclid's proof as Euclid presents it. —David Eppstein (talk) 01:29, 18 April 2021 (UTC)

Relationship to well-ordering of the natural numbers

The common induction does follow from the well ordering principle, because the well ordering assumed is not just any well ordering, but the transitive closure of n < S(n). This entire section, as well as professor Öhman's article, hinges on a misunderstanding of an elementary definition. Tkjanacek (talk) 22:48, 17 April 2021 (UTC)

You may be right in that requiring the transitive closure of n < S(n) to be a well-ordering implies the induction axiom. However, Öhman apparently uses a wider understanding of 'well-ordering principle', and infers correct properties from it, so there is no reason why they shouldn't be presented here. Feel free to add your (claimed) equivalence of induction with your narrow understanding of well-ordering, preferrably with a reference or/and a proof. - Jochen Burghardt (talk) 10:24, 18 April 2021 (UTC)

Complete and transfinite induction

@Julian Benali: I still don't agree with your recent edits:

In section Mathematical_induction#Complete (strong) induction, you made the green insertion

"This is a special case of transfinite induction as described below, although it is no longer equivalent to ordinary induction".

I think it is obvious that a special case is not equivalent to a general case, so "although" confuses the reader, and your green sentence is at best redundant. By analogy, nobody would make an insertion like

"x+5 is greater than x+3, although they are no longer equal."

In section Mathematical_induction#Transfinite induction, you made the insertion

"One variation of the principle of complete induction can be generalized for statements about elements of any well-founded set ..."

I think there is only one form of complete induction, viz. (∀m∈ℕ. (∀n∈ℕ. n<m → P(n)) → P(m)) → (∀n∈ℕ. P(n)), and this generalizes to transfinite induction by replacing ℕ by an arbitrary (set representation of an) ordinal number α. I wouldn't call transfinite induction a variant of complete induction, and I think, the article didn't that neither.

I feel that you intend to emphasize that standard induction doesn't immediately generalize to arbitrary ordinals, and, following Öhman (2019), I agree with that - see the discussion in Mathematical_induction#Relationship to the well-ordering principle. I just think your recent edits aren't adequate to achive that goal. - Jochen Burghardt (talk) 16:47, 12 August 2021 (UTC)

Hi @Jochen Burghardt:, thanks for the response. Perhaps my use of "they" was too ambiguous in the phrase "although they are no longer equivalent." since you seem to have misinterpreted what I was referring to, in which case I apologize for the ambiguity. I was not saying that complete induction is not equivalent to transfinite induction. I was saying that complete induction, as described in that paragraph, is not equivalent to ordinary induction. The reason is exactly the same as why the well-ordering principle is not equivalent to induction.

In the first paragraph of Mathematical_induction#Complete (strong) induction, complete induction is defined in a way which translates formally as

$\forall P{\Bigl (}P(0)\land \forall m{\bigl (}\forall n(n\leq m\to P(n))\to P(m+1){\bigr )}\to \forall n{\bigl (}P(n){\bigr )}{\Bigr )}$

which I will refer to as $\phi _{1}$. This sentence is indeed equivalent to ordinary induction. However, the third paragraph describes another form of complete induction, which formalizes as

$\forall P{\Bigl (}\forall m{\bigl (}\forall n(n<m\to P(n))\to P(m){\bigr )}\to \forall n(P(n)){\Bigr )}$

which I will refer to as $\phi _{2}$. This second variation, however, is equivalent to the well-ordering principle relative to the first four Peano axioms, and is therefore strictly weaker than both ordinary induction and $\phi _{1}$. Furthermore, the paragraph immediately after the one where $\phi _{2}$ is introduced goes on to explain how "complete induction" is equivalent to ordinary induction, correctly making use of the $\phi _{1}$ definition while doing this. My issue is that this section would seem to suggest that both variations of complete induction are equivalent to each other and thus to ordinary induction, when this is not the case. Perhaps you can think of a better way to make this clear than the edit I made.

Next, in Mathematical_induction#Transfinite induction, it is stated that complete induction can be generalized to statements about elements of any (well-founded) set. This, of course, is only actually a generalization if by "complete induction" the section means $\phi _{2}$, but there's no indication which variation this sentence is referring to, hence why I felt it necessary to specify that it is a specific variation of complete induction which generalizes. You claim to believe that "complete induction" only refers to one thing (specifically, $\phi _{2}$), which is fine by me. But this article does not currently reflect that belief, and so long as that is the case, I think the distinction between $\phi _{1}$ and $\phi _{2}$ needs to be maintained. Let me know what you think. - Julian Benali (talk) 06:49, 13 August 2021 (UTC)

@Julian Benali: Sorry for my delayed answer. Let us abbreviate ordinary induction on ℕ as $\phi _{3}$:

$\forall P{\Bigl (}P(0)\land \forall m{\bigl (}P(m)\to P(m+1){\bigr )}\to \forall n{\bigl (}P(n){\bigr )}{\Bigr )}$

Moreover, just to clarify my point of view, let me distinguish between $\phi _{i}$ (used for ℕ) and $\phi '_{i}$ (used for arbitrary ordinals). I think we almost agree that the following diagram describes the situation ("$\uparrow {\text{gen}}$" meaning "is a generalization of", and "$\equiv$" meaning something like "has the same deductive power as, relative to the other Peano axioms"):

${\begin{array}{rrclll}{\text{ordinal }}\alpha :&\phi '_{1}&\not \equiv &\phi '_{2}\\&{\text{gen}}\uparrow &&\uparrow {\text{gen}}\\\mathbb {N} :&\phi _{1}&\equiv &\phi _{2}&\equiv &\phi _{3}\\\end{array}}$

That is, $\phi _{1}$, $\phi _{2}$ and $\phi _{3}$ are all equivalent on ℕ (bottom row), while their generalizations to an arbitrary ordinal $\alpha$ are no longer equivalent (top row). I guess, you consider each $\phi _{i}$ equivalent with $\phi '_{i}$ (since the formulas are the same in unsorted logic), while I consider them different (since the formulas differ in sorted logic: "...∀n∈ℕ..." vs. "...∀n∈α...", and "<" is defined inductively for ℕ but obtained from the well-order definition for α).

I then read your first edit as

"This [$\phi _{2}$] is a special case of transfinite induction as described below [$\phi '_{2}$], although it [$\phi _{2}$, or $\phi '_{2}$?] is no longer equivalent to ordinary induction [$\phi _{3}$]".

If the "it" refers to $\phi _{2}$, we'd both agree that the insertion is wrong, since $\phi _{2}$ and $\phi _{3}$ are equivalent. If the "it" refers to $\phi '_{2}$, I still consider the insertion to be wrong, since the general $\phi '_{2}$ cannot be compared to the special $\phi _{3}$.

Concerning your second insertion, I now see your point, and agree with you. I'd suggest to present the two different forms of complete induction for ℕ (i.e. $\phi _{1}$ and $\phi _{2}$) more clearly (i.e. using formulas) in the previous paragraphs. From the lengthy text I find it hard to grasp that there are two forms. - Jochen Burghardt (talk) 07:54, 20 August 2021 (UTC)

Mathematical induction versus Well-ordering theorem

It is argued that mathematical induction is not equivalent to the well-ordering theorem, and that literature is wrong about that. But I only know literature in which it is indicated that complete mathematical induction is equivalent to the well-ordering theorem. The counterexample does not apply for complete mathematical induction, so I think both are equivalent, and that it is all about mathematical induction versus complete mathematical induction. — Preceding unsigned comment added by 178.84.82.19 (talk) 17:14, 19 December 2021 (UTC)

Induction hypothesis

I changed the definition of "induction hypothesis" from the statement in the induction step to the statement, independent of the induction step. The statement, whether used in the induction step or not, is the induction hypothesis. User:Jochen_Burghardt is mistaken about that part. However, it is reasonable to delete my addition about alternate bases, so I accept that. It is also reasonable to delete the "natural numbers" explanation of using base 0 or 1, because it is irrelevant what one thinks about natural numbers.

I hope User:Jochen_Burghardt will discuss this here instead of reverting immediately. Zaslav (talk) 21:30, 10 April 2022 (UTC)

I usually follow the policy WP:BRD: I give a brief justification for my revert in the edit summary, and discuss in more detail on the talk page if my revert is challenged.

In your case, I found, at first glance, the phrase "the statement" insufficient to make clear which formula is actually meant. After reading a second time the section in context, I admit that it consistently uses "the statement" to mean P(n) when an induction proof of ∀n∈ℕ.P(n) is discussed. However, the old phrasing makes more clear that the induction hypothesis may be used only inside the induction step. Otherwise, I could prove e.g. "Every number is odd" by induction as follows: let n be any natural number, then n is odd by the induction hypothesis, hence (trivially) n is odd, qed.

As a related issue, I suggest to add a minimum of formal notation to this section, viz. "P(n)", "P(0)", "P(n+1)", which is used throughout the article, but never introduced. This section is the appropriate place to introduce it.

Finally, if the remark on 0 vs. 1 is deleted, two appearences of "or 1" should be deleted, too. Indeed, deletion may be ok, since the issue is mentioned already in the lead, and in more detail in section Mathematical_induction#Induction_basis_other_than_0_or_1. - Jochen Burghardt (talk) 08:24, 11 April 2022 (UTC)

Thanks for the thoughtful reply. I'm short of time so I'll just say that base 0 or 1 is not related to the definition of natural numbers. It's only that some people want to say one proves P(n) for "all natural numbers", which is just choice of language. Serious answers later. Zaslav (talk) 19:07, 11 April 2022 (UTC)

Mathematical induction is related to induction reasoning internally but, as a whole, it is deductive. This article might use some re-phrasing/re-wording.

This article is wrong when:

1. saying that this mathematical induction is deductive*.- In deductive reasoning you use logical procedures to infer a particular truth/use case/etc. from a more general known truth. It might be used when finding a "new" particular case. That is not the case of mathematical induction. There is no general truth already known and accepted but there is one of interest (hypothesis) that requires a proof. Then, you prove a PARTICULAR BASE CASE; later, you assume certain UNSPECIFIED CASE as true (one might be tempted consider it general in the sense it may be "any" particular case, so that might be the reason some may get confused and think this method is deductive but you must resist that as it is clearly stated that it represents certain particular case that despite unknown cannot be considered the "general" case); and, finally, take that generalization a level/step higher/forward. If you can do that, from the base case that was proved and, the inductive step (containing the inductive inference that was just successfully produced), you infer (not deduce) that your hypothesis (general case) is true.

The foundation of this comes from the logical implication/inference rules such as 1 --> 0 = 0 that would imply the inductive step was not possible; but, if possible, one must continue by relying on what is explained at https://wiki.riteme.site/wiki/Mathematical_induction#Formalization for the whole reasoning on which mathematical induction is founded.

2. using the terms "deduce", "deduction" and similar instead of "infer", "inference", etc. when meaning arriving to a conclusion by means of logical devices/principles/etc..- Even if they are used as if they were exchangeable in daily conversations, their use must be rigorous here.

• The source used to support the fact that mathematical induction is deductive (https://earlham.edu/~peters/courses/logsys/math-ind.htm) is broken. And, if it were not, I'd still consider it wrong. Proving successive cases IS NOT a form of deduction as each particular case is at the same "level". Only the "general" case stated in the form of hypothesis is the "real" general case and it is not a proven truth like the one used for deductive reasoning.

George Rodney Maruri Game (talk) 17:42, 13 September 2023 (UTC)

Your thoughts on this topic constitute original research and should not be pushed into our article. We can only include content describing the consensus of scholarly research on the topic, based on published sources. Unless you can demonstrate that your position is accepted in scholarly research on this topic, it should not be included. —David Eppstein (talk) 18:10, 13 September 2023 (UTC)

In the same vein, I request academic support for your claim that mathematical induction is deductive. This article cites a broken link to back this claim. If not, I demand such claim to be removed. I propose contributors vote and present reputable sources to support either claim in the next couple of months. It should not be difficult to find the correct category for this topic. George Rodney Maruri Game (talk) 21:05, 13 September 2023 (UTC)

The contested language does actually omit an important point, which is that, while mathematical induction is deductive reasoning, it's not deductive reasoning just from the base case $P(0)$ and the induction step $\forall n[P(n)\implies P(n+1)]$. It's deductive reasoning from those two things plus (an instance of) the induction axiom. George, if the intro were to clarify that point, would it address your concerns? --Trovatore (talk) 21:26, 13 September 2023 (UTC)

Thanks, Trovatore. I just read some sources and my understanding is similar to yours. There is an inductive step but the "overall reasoning" is based on what is specified at the "Formalization" sub-section which happens to be classified as deductive in Philosophy. It would be useful for people who come here to be told about this to avoid confusion. I myself was confused for the way this article categorized this mathematical proof method as "deductive" without explaining a source that is not broken. There should always be more sources to avoid this kind of problems. I still think that the terms "deduce" and "infer" must not be used the way they are being used here. It will surely cause confusion.George Rodney Maruri Game (talk) 21:44, 13 September 2023 (UTC)