In a thread in GD (I think GD at least) colonial links to a page about the terminology of logic, but one of its statements is confusing. (The argument in the thread itself is irrelevant)
I thought strong induction was when P(k), P(k+1), P(k+2)… P(n) are true, the P(n+1) can be shown to be true, whereas weak induction just says if P(n) is true, P(n+1) can be shown to be true. Rr as my instructor at the time said, if you can get from any arbitrary stair in the staircase to the next, it’s weak induction. If you can only get to the next stair after travelling (at least some if not all of) the previous ones, it’s strong. The page, on the other hand, seems to be using “weak induction” to mean “unsound.”
A few google searches for “weak vs strong induction” confirm what I was taught. Whence the disparity? Is it a difference between, say, the logic terminology of philosophy and mathematical logic? Is the page just wrong?
But they stem from the same type of reasoning. Why use such wildly different definitions for the same terms? After all, deductive proofs use “valid” and “invalid” (and soundness etc) the same way.
No, they’re not really the same type of reasoning.
Inductive reasoning: I’ve seen a lot of crows, and all the crows I’ve observed have been black. Therefore I conclude that (it is likely that) all crows are black.
Mathematical induction-style proof: I’ve seen one or more crows, which have been black. Furthermore, I can demonstrate that all other crows are gentically related to the ones I’ve observed, in such a way that they must have the same color. Therefore I conclude that (I know for sure) all crows are black.
Hypotheses are produced by a kind of inductive reasoning (namely, “inference to the best explanation”) so in that sense, yes.
“Inductive reasoning” is a very broad term, encompassing many different kinds of arguments. The only thing they all have in common is that the premises are intended to give the conclusion merely probable support.
How did mathematical induction come to be called mathematical induction? I assume that “induction” in the broader sense came first, and “mathematical induction” was constructed from that concept somehow. But is that not right?
Why aren’t “strong” and “weak” the other way around?
I would have expected to be able to say something like “I couldn’t prove that P(N) implies P(N+1). I could only prove the weaker statement that P(N-1) & P(N) together imply P(N+1)”.
Well, yeah, your example is closer to the way (“weak”) mathematical induction actually works. It’s typically used to prove a statement about an arbitrary positive integer, such as “For any positive integer n, the nth crow is black.” In my example, I was trying to highlight the difference between an inductive argument and a proof that worked similarly to the way mathematical induction works.
I don’t know for sure, but I think so. Following up a footnote in the Wikipedia article led me to this page, which the OP may wish to consult if he’s still confused about the distinction between “ordinary” induction and mathematical induction. It says
Anybody know the origin(s) of the term “mathematical induction”?
IIUC it’s because “P(k), P(k+1), P(k+2)… P(n) are true” is a stronger statement than just “P(n) is true.” The stronger hypothesis does, as you point out, make the conclusion P(n+1) easier to deduce.
For what it’s worth, I think the etymology in both cases is something like “induction” as marching from claims about claims about particular instances* to claims about all instances (“All…”, “Every…”, “Whenever…”). Which both mathematical and non-mathematical induction do.
*: (Albeit, in the mathematical case, this may mean arbitrary particular instances)
ETA: Oh, damn, I started writing that 20 minutes ago, then went off and came back, and didn’t realize new posts had been made in the meanwhile. Well, here.
IF
for every natural number n it is true that
… if all natural numbers less than n are in S, then n is also in S
THEN S = N
Weak induction
IF
if any natural number n is in S, then n+1 is also in S
and
0 is in S
THEN S = N
Strong induction is called strong because you just have to prove the general rule that for every natural, the assumption that all smaller naturals are in S entails that n is in S. If you can do that, you have shown that S is N.
For weak induction, you have to show the general rule that the if n is in S then n+1 is in S. Then you have to prove an initial case (usually 0, sometimes 1). Only then have you shown that S is N.
Mathematicians and logicians think having to show that something holds for a particular case makes you less of a man, and therefore call that method weak induction.
I’m not sure that is so. Do you agree that this is the principle of strong induction (where A is the universal quantifier, e is membership, and => is the conditional)?
(An)[(Am)(m<n => meA) => neA]
Therefore: A = N
Then, taking the part before the “Therefore:” as true, one implication is
(Am)(m<0 => meA) => 0eA
Since, under your hypothesis, the membership criteria of A are never satisfied, the consequent is false. To preserve the truth of the conditional, the antecedent must be false. But,
(Am)(m<0 => meA)
cannot be false, because there is no natural less than 0.
Accordingly, the part above the “Therefore:”, the inductive step, is inconsistent with A being the null set.
Huh? What Kimmy Gibbler said is correct; one doesn’t need a separate base case. Show P(0) is exactly the same as showing True -> P(0), which is exactly the same as showing (For all x < 0, P(x)) -> P(0), which is already handled as just a special instance of the general pattern Kimmy Gibbler set out.
The induction principle “(For all y, (For all x < y, P(x)) -> P(y)) -> for all z, P(z)”, with no special handling of base cases, holds true in any well-founded order; indeed, it serves as one common constructive definition of well-foundedness.
One of the articles used for that blog entry is avaliable at JSTOR, it is short but thorough, and not behind a pay-wall. It is well worth a look.
On the terms “strong” and “weak” in this context, given two logics, if, for every set of premises, one of the logics entails all the other does, and for some set of premises it entails more than the other, it is said to be the stronger logic. Or, in short, a stronger logic is one that entails more.