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 Fitchstyle 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.
User Tag List
Results 1 to 9 of 9

09252008, 03:40 PM #1
Someone Please Explain Mathematical Induction
Artes, Scientia, Veritasiness

09272008, 11:05 PM #2
 Join Date
 Aug 2008
 MBTI
 ENTJ
 Posts
 481
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(n1)/2 (the sum of numbers 1 through n1) + n = n(n1)/2+2n/2.
Expanding n(n1), we have n^2n, 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 n1), 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!I am an ENTJ. I hate political correctness but love smart people ^_^

09282008, 12:20 AM #3
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 uselanguage 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 nonstructural 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.Artes, Scientia, Veritasiness

09282008, 11:06 AM #4
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 wellversed 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.MBTI Type: iNTj
Enneagram Type: 3w4 sp/sx

09282008, 03:14 PM #5
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.
Artes, Scientia, Veritasiness

09282008, 04:06 PM #6
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 n1. Strong induction uses the truth of the statement for 0 through n1.
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
Accept the past. Live for the present. Look forward to the future.
Robot Fusion
"As our island of knowledge grows, so does the shore of our ignorance." John Wheeler
"[A] scientist looking at nonscientific problems is just as dumb as the next guy." Richard Feynman
"[P]etabytes of [] data is not the same thing as understanding emergent mechanisms and structures." Jim Crutchfield

09282008, 05:53 PM #7
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 "0step 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 "nstep proof" in LFJ can also be proven in LHJ, but you are allowed the assumption that all statements that take n1 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 overkill).
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.
Accept the past. Live for the present. Look forward to the future.
Robot Fusion
"As our island of knowledge grows, so does the shore of our ignorance." John Wheeler
"[A] scientist looking at nonscientific problems is just as dumb as the next guy." Richard Feynman
"[P]etabytes of [] data is not the same thing as understanding emergent mechanisms and structures." Jim Crutchfield

09282008, 06:23 PM #8
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).Artes, Scientia, Veritasiness

09282008, 06:51 PM #9
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.
Accept the past. Live for the present. Look forward to the future.
Robot Fusion
"As our island of knowledge grows, so does the shore of our ignorance." John Wheeler
"[A] scientist looking at nonscientific problems is just as dumb as the next guy." Richard Feynman
"[P]etabytes of [] data is not the same thing as understanding emergent mechanisms and structures." Jim Crutchfield
Similar Threads

Can someone please explain this to me?
By NEMESlS in forum What's my Type?Replies: 2Last Post: 10292012, 12:54 PM 
Could someone please help explain shadow functions?
By swift sylvan in forum MyersBriggs and Jungian Cognitive FunctionsReplies: 12Last Post: 12102010, 07:44 PM 
Can someone please explain...
By Amethyst in forum Arts & EntertainmentReplies: 10Last Post: 09022010, 07:09 PM 
someone please explain Ni to me!
By miss fortune in forum MyersBriggs and Jungian Cognitive FunctionsReplies: 59Last Post: 06092010, 06:14 PM