Someone Please Explain Mathematical Induction

[Orangey]

Hello all,

I am struggling to understand the concept of mathematical induction, and I need to get a grasp of it soon or else I'll end up bombing my philosophy course. Does anyone here know how to do this stuff that could possibly explain it to me? I've tried taking to the prof, but he is this old guy and I think sometimes he forgets what he's talking about (while he's talking to me).

If you need more specifics, here is an example problem that I should be able to do (keep in mind this is a proof theory course). I need to prove, using induction (and Fitch-style proof), that:

For all Gamma and all A, there is an HJ proof of A on hyp Gamma if and only if there is an FJ proof of A on hyp Gamma.

LFJ and LHJ are languages, namely linear fitch intuitionism and linear hilbert intuitionism.

Sorry for the wordy description of the problem, but I wouldn't be able to get the symbols in here anyway.

Anyway, I know that there are a lot of people on this board with fairly specialized knowledge, so if any of you could help me it would be greatly appreciated.

[IlyaK1986]

Originally Posted by Orangey

Hello all,

I am struggling to understand the concept of mathematical induction, and I need to get a grasp of it soon or else I'll end up bombing my philosophy course. Does anyone here know how to do this stuff that could possibly explain it to me? I've tried taking to the prof, but he is this old guy and I think sometimes he forgets what he's talking about (while he's talking to me).

If you need more specifics, here is an example problem that I should be able to do (keep in mind this is a proof theory course). I need to prove, using induction (and Fitch-style proof), that:

For all Gamma and all A, there is an HJ proof of A on hyp Gamma if and only if there is an FJ proof of A on hyp Gamma.

LFJ and LHJ are languages, namely linear fitch intuitionism and linear hilbert intuitionism.

Sorry for the wordy description of the problem, but I wouldn't be able to get the symbols in here anyway.

Anyway, I know that there are a lot of people on this board with fairly specialized knowledge, so if any of you could help me it would be greatly appreciated.

Okay, this might be fast, but you can read it over and over. Induction is like an infinite set of dominoes.

It works by proving a general case by starting with a base case (the first domino), and then showing that for any such domino, it will make the next one fall over just as easily.

For instance, let's say that I want to prove that the sum of numbers 1 through n was n(n+1)/2

Let's take the base case of 1 and 2. The sum of 1 and 2 is 3. n in this case is 2. So...

2(3)/2=3. It works.

Now, let's do the general case.

n(n-1)/2 (the sum of numbers 1 through n-1) + n = n(n-1)/2+2n/2.

Expanding n(n-1), we have n^2-n, and then we add another 2n. So now we have n^2+n=n(n+1)/2, which is the sum for all numbers 1 through n (as opposed to 1 through n-1), which shows that the general case holds, and thus, our proof is done.

I'm not exactly sure what the hell it's doing in a PHILOSOPHY course though. Mathematics, engineering, and computer science, sure...but PHILOSOPHY? Ahahahah!

[Orangey]

Originally Posted by IlyaK1986

Okay, this might be fast, but you can read it over and over. Induction is like an infinite set of dominoes.

It works by proving a general case by starting with a base case (the first domino), and then showing that for any such domino, it will make the next one fall over just as easily.

For instance, let's say that I want to prove that the sum of numbers 1 through n was n(n+1)/2

Let's take the base case of 1 and 2. The sum of 1 and 2 is 3. n in this case is 2. So...

2(3)/2=3. It works.

Now, let's do the general case.

n(n-1)/2 (the sum of numbers 1 through n-1) + n = n(n-1)/2+2n/2.

Expanding n(n-1), we have n^2-n, and then we add another 2n. So now we have n^2+n=n(n+1)/2, which is the sum for all numbers 1 through n (as opposed to 1 through n-1), which shows that the general case holds, and thus, our proof is done.

I'm not exactly sure what the hell it's doing in a PHILOSOPHY course though. Mathematics, engineering, and computer science, sure...but PHILOSOPHY? Ahahahah!

So what you just showed me would be strong induction, yes (or complete induction, I forget the word)? And that second part, where you do the general case, that is the inductive step, right? I think I understand better now- thanks for the reply.

The only thing I got from my lecture was that there is a base case, such as, say with my example, that there is a proof in LFJ of A on hyp Gamma (Gamma being a use-language symbol ranging over formulae). Symbolically it would look like "Gamma |=(LFJ) A". Then there was an inductive step, where it would basically be a linear representation of some structural or non-structural rule of the language such as modus ponens (or cut, or weakening, etc..., depending on the language). Then the last step would be a conclusion that would essentially make the whole thing recursive.

Oh, and yes it's a logic course in the philosophy department (proof theory, foundations of mathematics kind of stuff...in advanced logic the math stuff starts appearing). This is a program with a very strong analytic bent. Unfortunately I find it very difficult to follow the professor in lecture (he's old and mumbles a lot, and doesn't explain everything), and even more difficult to follow when asking him questions face to face.

Part of the problem is that, yeah, you've taken a couple years of symbolic logic and thought you had a handle on the material...(you is figurative)...and then you get to grad school and find out that there is this gap between what you learned and what you're learning now. In other words, they don't make the transition between elementary logic (being able to construct proofs and manipulate formulae IN the languages of first order propositional and predicate logic) and advanced metalogical theory very easy.

[Mondo]

Could you explain some of the key differences between LFJ and LHJ?

I'm not familiar with either of those terms.

I'm sorry for stating the obvious but it seems like that Hilbert is kind of Fitch's bitch here.

Unlike most of the humanities, you need to be well-versed in the rules of formal logic to excel in philosophy.
This is no surprise to me. My brother who was a Math major in college is actually on his way to getting a P.H.D in Philosophy right now.

[Orangey]

Originally Posted by Mondo

Could you explain some of the key differences between LFJ and LHJ?

I'm not familiar with either of those terms.

I'm sorry for stating the obvious but it seems like that Hilbert is kind of Fitch's bitch here.

Unlike most of the humanities, you need to be well-versed in the rules of formal logic to excel in philosophy.
This is no surprise to me. My brother who was a Math major in college is actually on his way to getting a P.H.D in Philosophy right now.

Well LHJ has only one inference rule which is modus ponens. LFJ has rules hyp, conditional proof, modus ponens, and reiteration. What I've been given are inductive definitions of each system (which amount to linear representations of the inference rules for each system as the induction step), and from those I'm supposed to use induction to prove that if A is an immediate consequence of the set of sentences Gamma in LFJ, then A is also an immediate consequence of the set of sentences Gamma in LHJ, and vise versa. My problem is that I don't know how I would go about setting up the proof.

[ygolo]

Hi Orangey,

The proof that IlyaK1986 gave you was not an example of "strong" induction. It was simply an example of the normal "weak" induction. The inductive step used in that proof only relied on the truth of the of the statement for n-1. Strong induction uses the truth of the statement for 0 through n-1.

You will likely need strong induction for your proofs.

I am not familiar with the particular terminology you are using, but in my experience of proving statements over languages usually requires proving the desired statement for each of the "ground" or "terminals" of the language, and then using strong induction for each way the language can be constructed from smaller elements.

Regards,
ygolo

[ygolo]

Originally Posted by Orangey

Well LHJ has only one inference rule which is modus ponens. LFJ has rules hyp, conditional proof, modus ponens, and reiteration. What I've been given are inductive definitions of each system (which amount to linear representations of the inference rules for each system as the induction step), and from those I'm supposed to use induction to prove that if A is an immediate consequence of the set of sentences Gamma in LFJ, then A is also an immediate consequence of the set of sentences Gamma in LHJ, and vise versa. My problem is that I don't know how I would go about setting up the proof.

Note here, you are given most of you base case is already given to you. That is, the sentences Gamma immediately follow the sentences Gamma in both systems. You would then have to prove the axioms in one follow from the other, and vice versa, as bart of the base step (this is potentially the hardest part of the proof).

Now your task is actually to create two induction arguments (or a single intertwined argument). One is proving that all statements that immediately follow Gamma in LHJ also follow in LFJ. The other is to prove the reverse.

Setup you induction based on the number of proof steps. You prove the "0-step proof" case. Gamma in LFJ is Gamma in LHJ. Then prove the axioms of LFJ are axioms in LHJ.

Now your "strong" inductive step would be to prove that the statements that take an "n-step proof" in LFJ can also be proven in LHJ, but you are allowed the assumption that all statements that take n-1 steps or less in LFJ can be proven in LHJ.

I may be mistaken, but after some googling, I believe the axioms for LHJ are a subset of the rules for LFJ. So proving the what follows from Gamma in LHJ, but also follow from LFJ is trivial. That is every LHJ proof is an LHJ proof. Proving that inductively ought to be straight forward (perhaps even over-kill).

Still, it would be helpful to know what the rules for LHJ and LFJ actually are. It is hard for me to believe that someone would create extra axioms if they aren't needed.

[Orangey]

Originally Posted by ygolo

Note here, you are given most of you base case is already given to you. That is, the sentences Gamma immediately follow the sentences Gamma in both systems. You would then have to prove the axioms in one follow from the other, and vice versa, as bart of the base step (this is potentially the hardest part of the proof).

Now your task is actually to create two induction arguments (or a single intertwined argument). One is proving that all statements that immediately follow Gamma in LHJ also follow in LFJ. The other is to prove the reverse.

Setup you induction based on the number of proof steps. You prove the "0-step proof" case. Gamma in LFJ is Gamma in LHJ. Then prove the axioms of LFJ are axioms in LHJ.

Now your "strong" inductive step would be to prove that the statements that take an "n-step proof" in LFJ can also be proven in LHJ, but you are allowed the assumption that all statements that take n-1 steps or less in LFJ can be proven in LHJ.

I may be mistaken, but after some googling, I believe the axioms for LHJ are a subset of the rules for LFJ. So proving the what follows from Gamma in LHJ, but also follow from LFJ is trivial. That is every LHJ proof is an LHJ proof. Proving that inductively ought to be straight forward (perhaps even over-kill).

Still, it would be helpful to know what the rules for LHJ and LFJ actually are. It is hard for me to believe that someone would create extra axioms if they aren't needed.

ygolo,

This is extremely helpful- thank you. So the idea is that I need to prove that what follows from Gamma in LHJ follows from Gamma in LFJ, using induction. I think I see how I would go about doing this from your explanation...an added complication is that I have to set up the induction in subproof notation, which confuses the hell out of me. But I will try and see what I get.

About the rules for LHJ and LFJ- they are as follows:

LFJ- Reit, MP, CP, Hyp.

LHJ- MP, Axioms;
A -> A
(A -> B -> C) -> .A -> B -> .A -> C
A -> .B -> A

The def of the relation Gamma |=(LHJ) A:
If A is a member of the Axioms of HJ, then Gamma |=(LHJ) A
If A is a member of Gamma, then Gamma |=(LHJ) A
If A is a member of Gamma, and Gamma|=(LHJ) A->B, then Gamma|= B

And then there is a closure clause that substitutes psi(Gamma, A) for all instances of Gamma|=(LHJ) A, and basically repeats the above definition.

The LFJ one is similar to the LHJ one with the difference being that the rules MP, CP, Reit, and Hyp are all in linear form as the inductive step, similar to how it was in LHJ with MP.

Anyway, I appreciate the all the help. I'm thinking that if I transfer this to the fitch subproof notation, with the basis and inductive steps each as their own subproof, then I can substitute Gamma|=(LFJ) A in for psi(Gamma, A) in the HJ subproof and go from there (and vise versa for the FJ subproof).

[ygolo]

I think I had to do something similar to this in my "Elements of Artificial Intelligence" class, but the terminology and symbolism were slightly different.

I am glad to be of help. You probably have it figured out. Explaining notation over the web in a forum without explicit support for symbols is difficult.

It seems like the Axioms of HJ are equivalent to the use of CP, Reit, and Hyp.

I'd imagine the part that makes the proof difficult is remembering the exact definitions and following the steps in tedious detail.

But it seems like CP (after more googling) is like the second axiom. I don't know what Reit and Hyp are.