need clearer explanation of mathematical induction.
Posted: Sat Aug 19, 2017 5:05 am
Okay, so I'm reading a book called The Logic Book and I just started the chapter about Metatheory. The topic of Mathematical Induction is being discussed by an example using the recursive definitions of Symbolic Logic.
So, they say how can you prove for every sentence the number of left parenthesis equals the number of right parenthesis for these recursive definitions:
1. Every sentence letter is a sentence.
2. If P is a sentence, then ~P is a sentence.
3. If P and Q are sentences then (P & Q) is a sentence.
4. If P and Q are sentences then (P V Q) is a sentence.
5. If P and Q are sentences then (P ⊃ Q) is a sentence.
6. If P and Q are sentences then (P ≡ Q) is a sentence.
7. Nothing is a sentence unless it can be formed by repeated application of clauses 1-6
They talk about proving the basis clause of the first premise then use the second premise as the inductive step which you need to prove is true
I'm not clear - is the inductive hypothesis the first premise? - the basis clause? They say it's the antecedent of the inductive step.
So they say that if you prove that the basis clause and the inductive step are both true then the conclusion must be true.
They give a generalized example of mathematical induction based on the logic of the above example (whose entirety I omitted):
The thesis holds for every member of the first group in the series.
For each group in the series, if the thesis holds of every member of every prior group then the thesis holds for every member of that group as well.
The thesis holds for every member of every group on the series.
It's not clear to me how this differs from deduction
So, they say how can you prove for every sentence the number of left parenthesis equals the number of right parenthesis for these recursive definitions:
1. Every sentence letter is a sentence.
2. If P is a sentence, then ~P is a sentence.
3. If P and Q are sentences then (P & Q) is a sentence.
4. If P and Q are sentences then (P V Q) is a sentence.
5. If P and Q are sentences then (P ⊃ Q) is a sentence.
6. If P and Q are sentences then (P ≡ Q) is a sentence.
7. Nothing is a sentence unless it can be formed by repeated application of clauses 1-6
They talk about proving the basis clause of the first premise then use the second premise as the inductive step which you need to prove is true
I'm not clear - is the inductive hypothesis the first premise? - the basis clause? They say it's the antecedent of the inductive step.
So they say that if you prove that the basis clause and the inductive step are both true then the conclusion must be true.
They give a generalized example of mathematical induction based on the logic of the above example (whose entirety I omitted):
The thesis holds for every member of the first group in the series.
For each group in the series, if the thesis holds of every member of every prior group then the thesis holds for every member of that group as well.
The thesis holds for every member of every group on the series.
It's not clear to me how this differs from deduction