Timeline for Induction vs. Strong Induction
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 16 at 13:17 | history | edited | Sam Nead | CC BY-SA 4.0 |
There are two versions of strong induction.
|
| Mar 22, 2020 at 23:27 | history | edited | RobPratt |
added induction tag
|
|
| Mar 22, 2020 at 23:05 | answer | added | user76284 | timeline score: 2 | |
| Sep 11, 2010 at 22:43 | vote | accept | Austin Mohr | ||
| Sep 11, 2010 at 22:42 | vote | accept | Austin Mohr | ||
| Sep 11, 2010 at 22:43 | |||||
| Sep 7, 2010 at 19:18 | comment | added | Arturo Magidin | @Austin and @KConrad: If you replace regular induction with strong induction in the Peano Axioms, you get a different axiomatic theory. $\omega+\omega$ is a model of the modified version but not of the Peano axioms. They only become equivalent if we add a few more axioms to the first four, e.g., "every number is either $0$ or a successor." This is a theorem in the usual system, but not in the modified one. | |
| Sep 7, 2010 at 19:16 | answer | added | Arturo Magidin | timeline score: 10 | |
| Sep 7, 2010 at 14:20 | answer | added | gowers | timeline score: 16 | |
| Sep 7, 2010 at 12:05 | answer | added | Carl Mummert | timeline score: 24 | |
| Sep 7, 2010 at 6:28 | answer | added | Thomas Scanlon | timeline score: 9 | |
| Sep 7, 2010 at 6:26 | answer | added | user5810 | timeline score: 3 | |
| Sep 7, 2010 at 6:22 | comment | added | KConrad | Austin: it's too late to make that change. The two versions of induction are equivalent, and by tradition if your proof only uses the immediately preceding case then it's better style to formulate the induction using the standard induction hypothesis. To formulate a strong induction hypothesis and then not use the "strong" aspect will make it look like you don't know how to write well. | |
| Sep 7, 2010 at 5:06 | history | edited | Austin Mohr | CC BY-SA 2.5 |
added 120 characters in body; edited tags
|
| Sep 7, 2010 at 4:14 | comment | added | Austin Mohr | @Jonas I suppose my use of the word "practical" is inappropriate. I apologize that my question is ill-formed. I just wanted to spark i discussion. It seems to me that, for any induction proof, we are justified in assuming the strong induction hypothesis, even if we only end up using the "standard" inductive hypothesis. Why then, do we even have two notions? Why not let "strong induction" be called "induction" in the Peano axioms and dispense with the other version altogether? | |
| Sep 7, 2010 at 3:45 | comment | added | Andrés E. Caicedo | Why is this tagged set-theory? | |
| Sep 7, 2010 at 3:44 | comment | added | Andrés E. Caicedo | There is also this: mathoverflow.net/questions/11964/… | |
| Sep 7, 2010 at 3:32 | comment | added | Jonas Meyer | Could you please elaborate a little on what you mean by "practical"? Do you just want examples that show that it is often much more convenient to use one vs. the other? | |
| Sep 7, 2010 at 3:22 | history | asked | Austin Mohr | CC BY-SA 2.5 |