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)

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(n) D(ivisible by) (x + a), E(n) = xⁿ + aⁿ and the whole expression E(n) D (x + a) can be denoted P(n) or D(n).--109.166.135.99 (talk) 17:51, 4 January 2020 (UTC)