need clearer explanation of mathematical induction.

What is the basis for reason? And mathematics?

Moderators: AMod, iMod

Post Reply
ProfAlexHartdegen
Posts: 20
Joined: Mon Jul 31, 2017 5:43 pm

need clearer explanation of mathematical induction.

Post by ProfAlexHartdegen »

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
User avatar
PauloL
Posts: 473
Joined: Fri Jul 07, 2017 10:12 pm
Location: Lisbon, Portugal.

Re: need clearer explanation of mathematical induction.

Post by PauloL »

ProfAlexHartdegen wrote: Sat Aug 19, 2017 5:05 am
.




Mathematical induction differs nothing from deduction. Indeed, that's an example of deductive reasoning.

However, from what I remember from my school time, mathematical induction has nothing to do with your example.

Mathematical induction is a method of demonstration that a statement holds for all natural numbers.

It says a (1) statement will hold for any n if it (2) holds for n=1 and (3) holds for n+1.

Here (1) is the hypothesis and (3) the thesis.




.
ProfAlexHartdegen
Posts: 20
Joined: Mon Jul 31, 2017 5:43 pm

Re: need clearer explanation of mathematical induction.

Post by ProfAlexHartdegen »

My example comes directly from the textbook The Logic Book, Chapter 6 Sentential Logic: Metatheory.

The specific example that I cite comes from the second page of that chapter and is prefaced with the words:

"We introduce mathematical induction with an example. It seems obvious that in each sentence of SL the number of left parenthesis equals the number of right parenthesis......"

Then they continue with the example from my first post.

I read on wikipedia that some forms of deductive reasoning are the same as mathematical induction. If so, why differentiate them with different names?

During the example they do mention using the reasoning that: "as soon as you establish that a claim holds for every sentence with k or fewer occurrences of connectives ( they use the number connectives to help prove there are equal numbers of right and left parenthesis) the same pattern of reasoning shows that the claim holding every sentence that contains k +1 occurrences of connectives"
Averroes
Posts: 535
Joined: Thu Jul 20, 2017 8:48 pm

Re: need clearer explanation of mathematical induction.

Post by Averroes »

ProfAlexHartdegen wrote: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.
If you consider the formation rules 2-6, you will notice that they are conditional statements, i.e. if Γ then φ:
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.
In an inductive proof, there are three parts which can be distinguished:
1. The base case
2. The inductive hypothesis
3. The inductive step.

The base case here are the atomic formulas, i.e. formation rule #1: Every sentence letter is a sentence. In that case, there are neither left nor right parentheses. So, the number of left and right parentheses are equal for the base case, i.e 0 (zero)

For composite formulas, (i.e. formation rules #2-6), we assume the antecedent of the formation rules and deduce the consequent. It looks like this:

For negation (i.e. formation rule 2)

Inductive hypothesis: Assume P has an equal number of right and left parenthesis, say n.

Note here we have assumed the antecedent of formation rule 2, ie “If P is a sentence then ~P is a sentence”

Inductive step: By the induction hypothesis (i.e. assuming the inductive hypothesis holds), then α = ~P, has the same number of right and left parentheses as well, i.e. n left parenthesis and n right parenthesis.

For the binary connectives (i.e. formation rules 3-6)

We will consider the formation rules 3-6 collectively by letting the symbol * stand for any binary connective from the set {&, V, ⊃, ≡} (otherwise you will have to do for each one!)

Inductive hypothesis: Assume P and Q are sentences and we assume that they have an equal number of left and right parentheses, say n and m respectively.
Note here we assume the antecedent of the formation rules 3-6, i.e. “If P and Q are sentences then (P * Q) is a sentence.”

Inductive step: By induction hypothesis, then α= (P * Q) has the same number of left and right parenthesis as well, namely n+m+1 left parenthesis and n+m+1 right parenthesis.

Hence, by mathematical induction the statement that every sentence of sentential logic has the same number of left and right parenthesis is proved.


So to answer your question,
ProfAlexHartdegen wrote:is the inductive hypothesis the first premise? - the basis clause? They say it's the antecedent of the inductive step.
The basis clause is not the inductive hypothesis. The basis clause/case is the number of left and right parenthesis in the atomic formula, which is none (=0).

The inductive hypothesis is the assumption (i.e. we suppose it to be true) of antecedent of the formation rules for composite/molecular formulas, i.e. the antecedent of rules 2-6. The inductive step is the whole conditional statement with which the formation rules for the logical constants are expressed, (i.e. rules 2-6) and for which we have assumed the antecedent and derived the consequent.
ProfAlexHartdegen wrote:It's not clear to me how this differs from deduction
Well, it is not clear to me either, and fortunately so!

Mathematical induction is not the same as inductive reasoning like in science where we infer general principles from a number of special cases. Inductive reasoning of the latter sort is invalid in logic/mathematics. Mathematical induction or inductive proofs are forms of deductive reasoning. Only deductive proofs are admitted as valid proofs in mathematics and logic. So it is good that the difference was not clear to you, because there was not (and should not be) much difference to be observed!

You can read this material to get some more accessible examples of mathematical induction: http://www.cs.cornell.edu/courses/cs280 ... uction.pdf
ProfAlexHartdegen
Posts: 20
Joined: Mon Jul 31, 2017 5:43 pm

Re: need clearer explanation of mathematical induction.

Post by ProfAlexHartdegen »

thanks again for your detailed replies. Just a slight clarification request, so in mathematics and mathematical induction: are you hypothesizing a general principle and trying to prove as many cases as possible are applicable?
User avatar
PauloL
Posts: 473
Joined: Fri Jul 07, 2017 10:12 pm
Location: Lisbon, Portugal.

Re: need clearer explanation of mathematical induction.

Post by PauloL »

ProfAlexHartdegen wrote: Sun Aug 20, 2017 7:15 am
I think you're hypothesizing a general statement, that it applies to all natural numbers in my case. After you test it against mathematical induction methods and it passes, you deduct the hypothesis holds true and thus applies to ALL possible cases.
Averroes
Posts: 535
Joined: Thu Jul 20, 2017 8:48 pm

Re: need clearer explanation of mathematical induction.

Post by Averroes »

ProfAlex wrote:so in mathematics and mathematical induction: are you hypothesizing a general principle and trying to prove as many cases as possible are applicable?
Concerning mathematical induction, in my understanding, what can appropriately be said to be a general principle is the inductive step, and the latter is always in the form of a conditional, i.e. if p (k ) then p (k+1); even though it might not be explicitly stated as such, as in the recursive definitions (i.e. rules 2-6) that you gave in the OP. Consider the following carefully. What we assume is the antecedent of the inductive step, i.e. p(k) (which we call the inductive hypothesis), and from this assumption we derive the consequent, i.e. p (k+1).

Now recall from the truth table for implication, that it can only be false if its antecedent is true and its consequent false. But this possibility was discarded in our proof, because we have proved that when the antecedent holds then the consequent follows. So the inductive step, i.e. the conditional "if p (k) then p (k+1)" was proved and not assumed/hypothesized. What you should carefully consider is this: the conditional “if p(k) then p(k+1)” was proved.

Now the base case is the first value of k for which p(k) holds. Say the base case is when k=0, so p (0) is shown to hold. And then we have proved in the inductive step that p (k) entail p (k+1). So as we know p (0) holds, we also know by the inductive step that p (1) also holds. As we now know p (1) holds, by the inductive step again, we now also know p (2) holds etc... All we did is show the base case, and proved the inductive step, and when we do that it is as if there is a "domino or ripple effect" that starts from the base case and propagates through all subsequent cases! So we prove all the cases starting as from the base case in this fashion!

For example in the previous proof of the number of left and right parenthesis, it was proved for all SL sentences and not just for as many as possible sentential logic sentences. Every senstence of SL is ultimately constructed from atomic sentences. All the rules that can be applied to construct molecular sentences from atomic sentences will introduce the same number of left and right parenthesis. However far one is in this construction process, the same rules apply. So the idea is that we show the base case (the atomic sentence), and take an arbitrary step far ahead in the construction process and show that the left and right parenthesis are still balanced. And the induction proof is thus completed. You can then imagine the "domino effect" to be convinced by the proof!
User avatar
Arising_uk
Posts: 12314
Joined: Wed Oct 17, 2007 2:31 am

Re: need clearer explanation of mathematical induction.

Post by Arising_uk »

Not that it helps much but on my Logic course it was called Structured Induction and I think there's Structured Recursion in there somewhere as well.
Averroes
Posts: 535
Joined: Thu Jul 20, 2017 8:48 pm

Re: need clearer explanation of mathematical induction.

Post by Averroes »

ProfAlexHartdegen

If you are still having trouble with this, you can ask more questions. If that be the case, tell me where you are stuck.
ProfAlexHartdegen
Posts: 20
Joined: Mon Jul 31, 2017 5:43 pm

Re: need clearer explanation of mathematical induction.

Post by ProfAlexHartdegen »

thank you so much for your willingness to help, I think I might understand now - I am reading farther along the book. I'm just finishing the section about Truth Functional Completeness. :)
ProfAlexHartdegen
Posts: 20
Joined: Mon Jul 31, 2017 5:43 pm

Re: need clearer explanation of mathematical induction.

Post by ProfAlexHartdegen »

Actually, I do have another question that involves the concepts of Mathematical Induction and Truth Functional Completeness.

In that section of the Logic Book there is another example of Mathematical Induction that discusses a minor point in passing that confuses me. The example involves showing that the set of connectives {'∨' '&'} are NOT Truth Functionally Complete. Unfortunately to address the minor point I must present the entire discussion so I will write it verbatim hereafter.

First, I should say that I have seen them do this with a couple other examples prior. The confusing issue for me involves how Case 1 says it has fewer than k + 1 occurrences of connectives while Case 2 has k or fewer occurrences of connectives. Should not both Cases be concerned with k + 1 occurrences of connectives?

Their thesis is presented verbatim:

"Every Wedge-Ampersand sentence has the truth value T on every truth value assignment on which its' atomic components all have the truth value T.

This is a general claim about all W-A sentences so it cannot be proved by examining W-A sentences one by one ( there are infinitely many). Instead we shall prove the thesis by mathematical induction. The shortest W-A sentences - that is, those with zero occurrences of connectives, are simply the atomic sentences of SL.

Basis clause: Every atomic sentence of SL has the truth value T on every truth value assignment on which its' atomic components all have the truth value T.
Proof of basis clause: The basis clause is obviously true since an atomic sentence is itself its' only component.
Inductive step: if every W-A sentence of SL with k or fewer occurrences of connectives is such that it has the truth value T on every truth value assignment on which its' atomic components all have the truth value T, then every W-A sentence with k + 1 occurrences of connectives has the truth value T on every truth value assignment on which its' atomic components all have the truth value T.

Proof of Inductive step: we now assume that the inductive hypothesis is true for an arbitrary nonnegative integer k, that is we assume that every W-A sentence with k or fewer occurrences of connectives is true whenever all its' atomic components are true. we must show that it follows that the thesis also holds for any W-A sentence P with k + 1 occurrences connectives. since these sentences contain only '∨' and '&' as connectives there are two cases:

Case 1: P has the for Q ∨ R. Then Q and R each contain fewer than k + 1 occurrences. (Me: Why?) They are also W-A sentences. So by the inductive hypothesis, each disjunct is true on every truth value assignment on which each of its atomic components is true. So, if all the atom components of Q ∨ R are true then both Q and R are true and hence Q ∨ R is itself true.

Case 2: P has the form Q & R. then each of Q and R is a W-A sentence with k or fewer occurrences of connectives. (Me: Why?) hence the inductive hypothesis holds for both Q and R. Each conjunct is true on every truth value assignment on which all its' atomic components are true. So if all the atomic components of Q & R are true then both Q and R are true and hence Q & R itself is true."


Okay, that's almost all the discussion verbatim.

I really don't understand why the two cases differ in this matter of k and k +1
Averroes
Posts: 535
Joined: Thu Jul 20, 2017 8:48 pm

Re: need clearer explanation of mathematical induction.

Post by Averroes »

ProfAlex wrote:thank you so much for your willingness to help
In my way of life and frame of mind, the more I share what I have been given and the more I help others in doing beneficial things, the more I am helped and the more good things I get. So, it is a win-win situation for both of us!
ProfAlex wrote:Case 1: P has the for Q ∨ R. Then Q and R each contain fewer than k + 1 occurrences. (Me: Why?)
Since P has k+1 occurrences of W-A, and P has the form Q V R, then Q and R each contain fewer than k+1 occurrences of W-A. This is evident! Check the form of P! Isn’t it shown that there is a wedge in the form of P, i.e. Q V R (the bolded and underlined wedge). Since the whole ‘Q V R’ has k+1 occurrences of W-A, then Q and R each must have fewer than k+1, i.e. at least one less than P. I say 'at least' because there are mainly three cases to be distinguished here (but this is not important for the purposes of the explanation in the book you are reading):

1. Either each of Q and R are themselves composite, in which case the total W-A is k (one less than P). and each of Q and R will have a share of k W-A. Say they have an equal number of W-A, in this case each will have k/2 W-A. Here k is strictly greater than 1 (k>1), because each of Q and R is composite.

2. Or, one of Q or R is atomic and the other is composite/molecular. In this case, the composite sentence (say Q) will have k occurrences of W-A and the other none. Here k is greater than or equal to 1 (k>=1).

3. Or, both are atomic. In this case k=0, and each have k, i.e. 0 occurrences of W-A.

In all these cases, it makes sense to say, as the authors said, "Then Q and R each contain fewer than k + 1 occurrences." They say "fewer that k+1", i.e. each has at least one less than in P, which has k+1 occurrences.
ProfAlex wrote:Case 2: P has the form Q & R. then each of Q and R is a W-A sentence with k or fewer occurrences of connectives. (Me: Why?)
The same reasoning as above.
ProfAlex wrote:I really don't understand why the two cases differ in this matter of k and k +1
You should relax! This was the easiest part of all, and you already know this!

Compare the two statements once again, here they are:

Case 1: P has the for Q ∨ R. Then Q and R each contain fewer than k + 1 occurrences.
Case 2: P has the form Q & R. then each of Q and R is a W-A sentence with k or fewer occurrences of connectives.

Is there truly a difference?

Let us consider another example.

From Wikipedia:
A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

So we can say a prime is a natural number >1, but we can also say a prime is a natural number >=2. Isn’t it the same thing?

So, back to our example, in case 1, the authors of you book said: Q and R each contain < k+1 occurrences. And in case 2, they said: Q and R each contain <= k occurrences. As k is a natural number, they were saying the same thing in each case. May be to check if you were paying attention, they changed the formulation of expressing the same meaning. And it turns out you were paying attention, but in focusing on the logical operators, you forgot the easiest part, i.e. the meaning of the comparison operators! It happens, no need to worry. When studying you must also pause and relax and get some fresh air every so often. Otherwise what you would ordinarily have had no trouble understanding presents itself as a big difficulty. That should be a signal for you to slow down a little, and not exercise yourself to intellectual exhaustion.
Post Reply