Older discussion is at /Archive
![]() | This ![]() It is of interest to the following WikiProjects: | ||||||||||
|
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)
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)
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)
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)
@ Golopotw: Can you provide any references for this paragraph that you added to this article? Jarble ;( talk) 23:43, 27 December 2017 (UTC)
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)
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)
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)
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)
As requested on my talk page, here are my reasons for reverting 5.2.200.163's edits of 16 Jan 2018.
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)
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)
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)
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 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)
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)
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:
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)
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)
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)
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)
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)
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)
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)
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:
........... ........... ...........
........... ...........
(Symbolized with logical operator operator notation,
............
............
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)
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)
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)
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)
@ 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)
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)
@ 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 ofthe 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)
@ Julian Benali: Sorry for my delayed answer. Let us abbreviate ordinary induction on ℕ as :
Moreover, just to clarify my point of view, let me distinguish between (used for ℕ) and (used for arbitrary ordinals). I think we almost agree that the following diagram describes the situation ("" meaning "is a generalization of", and "" meaning something like "has the same deductive power as, relative to the other Peano axioms"):
That is, , and are all equivalent on ℕ (bottom row), while their generalizations to an arbitrary ordinal are no longer equivalent (top row). I guess, you consider each equivalent with (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 [] is a special case of transfinite induction as described below [],
although it [, or ?] is no longer equivalent to ordinary induction [".
If the "it" refers to , we'd both agree that the insertion is wrong, since and are equivalent. If the "it" refers to , I still consider the insertion to be wrong, since the general cannot be compared to the special .
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. and ) 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)
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)
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)
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 /info/en/?search=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.
George Rodney Maruri Game ( talk) 17:42, 13 September 2023 (UTC)
Older discussion is at /Archive
![]() | This ![]() It is of interest to the following WikiProjects: | ||||||||||
|
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)
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)
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)
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)
@ Golopotw: Can you provide any references for this paragraph that you added to this article? Jarble ;( talk) 23:43, 27 December 2017 (UTC)
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)
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)
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)
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)
As requested on my talk page, here are my reasons for reverting 5.2.200.163's edits of 16 Jan 2018.
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)
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)
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)
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 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)
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)
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:
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)
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)
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)
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)
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)
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)
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)
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:
........... ........... ...........
........... ...........
(Symbolized with logical operator operator notation,
............
............
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)
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)
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)
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)
@ 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)
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)
@ 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 ofthe 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)
@ Julian Benali: Sorry for my delayed answer. Let us abbreviate ordinary induction on ℕ as :
Moreover, just to clarify my point of view, let me distinguish between (used for ℕ) and (used for arbitrary ordinals). I think we almost agree that the following diagram describes the situation ("" meaning "is a generalization of", and "" meaning something like "has the same deductive power as, relative to the other Peano axioms"):
That is, , and are all equivalent on ℕ (bottom row), while their generalizations to an arbitrary ordinal are no longer equivalent (top row). I guess, you consider each equivalent with (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 [] is a special case of transfinite induction as described below [],
although it [, or ?] is no longer equivalent to ordinary induction [".
If the "it" refers to , we'd both agree that the insertion is wrong, since and are equivalent. If the "it" refers to , I still consider the insertion to be wrong, since the general cannot be compared to the special .
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. and ) 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)
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)
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)
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 /info/en/?search=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.
George Rodney Maruri Game ( talk) 17:42, 13 September 2023 (UTC)