Timeline for Strong induction without a base case
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 11, 2018 at 14:35 | comment | added | Maxis Jaisi | @PeterHeinig You are right. | |
| Feb 11, 2018 at 9:03 | comment | added | Peter Heinig | @MaxisJaisi: this objection at Sep 2'17 at 6:27 does not make any sense (to me): Joel has a an 'if-clause' to check for primality, as it were, and for $2$ and $3$ (and for any prime, for that matter), the line "Otherwise, $n=ab$ for some $a,b<n$" is never reached. | |
| Feb 11, 2018 at 7:25 | history | edited | José Hdz. Stgo. | CC BY-SA 3.0 |
added 1 character in body
|
| Sep 2, 2017 at 6:27 | comment | added | Maxis Jaisi | @Joel Sorry for resurrecting an old answer, but I can't help but point out that $2$ and $3$ are potentially problematic cases when it comes to your "Otherwise, $n = ab$ for some $a,b < n$". There are no integers greater than $1$, but less than $2$, so $P(2)$ should be checked. Since $a,b$ must be greater than $1$ for induction to work, $n = ab$ must be at least $4$, so $P(3)$ should also be checked. These cases, to me, are still "logical base cases", although they are trivial to check. | |
| Jul 8, 2010 at 3:37 | comment | added | Joel David Hamkins | The references I find seem to include both existence and uniqueness. e.g. en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic | |
| Jul 7, 2010 at 21:50 | comment | added | Michael Hardy | Isn't the fundamental theorem of arithmetic the uniqueness assertion? | |
| Jan 17, 2010 at 0:24 | comment | added | Joel David Hamkins | OK, I'm beginning to understand what you want. So I posted another example, on the cumulative hierarchy (see below....or above?) | |
| Jan 17, 2010 at 0:08 | comment | added | François G. Dorais | Bjorn is correct. Primes are the base case in the divisibility ordering - that is what this induction is really on, the standard ordering is just a rank function. | |
| Jan 16, 2010 at 23:26 | comment | added | Bjorn Poonen | @Joel: That is a nice example of strong induction, but I am really hoping for an argument that does not need a separate case to get started (here the separate case is the case where n is prime). Sorry if my question is vague; I'm not sure I can formalize what I want. | |
| Jan 16, 2010 at 23:25 | comment | added | Joel David Hamkins | Thanks, I corrected. @Qiaochu: Yes, but the question wants the most elementary example, so I complied. | |
| Jan 16, 2010 at 23:24 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
added 6 characters in body
|
| Jan 16, 2010 at 23:18 | comment | added | François G. Dorais | Nitpick: Perhaps replace positive by $\geq 2$ in the statement, otherwise the base case is different, though clearly not an "anchor case." | |
| Jan 16, 2010 at 23:15 | comment | added | Qiaochu Yuan | Neither of those cases hold if n = 1, so I guess you want to start the induction at n = 2. In that case the existence proof with "prime" replaced by "irreducible" works in any Noetherian commutative ring and this Noetherian induction also doesn't have a base case, I guess. | |
| Jan 16, 2010 at 23:11 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |