@F.Zer I already clarified that phrase in the sentence immediately after it.
@F.Zer Your outer logical structure is completely reasonable, but your attempt to prove it seems to arise from not first understanding why strong induction is correct. If you only apply induction to P, how are you going to prove P(k+1) from P(k)? "∀i∈ℕ ( i<k+1 ⇒ P(i) ) ⇒ P(k+1)" is not enough if you only have P(k). It ought to be intuitive that you need to apply induction to a stronger property Q, so that you can make use of the given condition for P.
Prithu has not yet given a complete proof, but has correctly set up suitable properties that can be used in a complete proof (using normal induction).
I believe both you and @Prithubiswas will benefit from learning this stuff together. You have the knowledge of formal FOL, and Prithu has a good intuition. What do you both think?
Martin R has linked a number of posts, but they are cluttered with many wrong explanations, with few exceptions (such as Henning Makholm's and Gadi A's). Even in this thread, the other posts do not really explain why we can choose to have $x^0 = 1$, even though they give motivation for why we wan...
It's a vague notion. It may be similar in flavour to satisfying ∀k∈ℕ ( Q(k) ⇒ P(k) ), but restricting yourself to that may lead to inferior proofs.
The general idea is simply that if you think something can be proven via induction, but the property you are using doesn't seem to provide enough information to prove the inductive step, then you can try strengthening the property (demanding more), but of course you also have to prove more (to get the inductive step). Nevertheless, asking for whatever you want sometimes does work out in the end.
@user21820 Good. But you are asking for a general proof, right ? P should account for every possible property; how it's possible that I find something even stronger than P ? I am trying to clarify what I'm being asked to do.
In the end, P is only a variable.
If you said, for example: strengthen the property "x ≥ 1", then I would reply with "x ≥ 2", for example. Is this correct ?
@F.Zer Technically, P is not a variable. That is why I never phrased the task in the way you did. I wrote, "for each property P on ℕ prove ...", because P is just a symbol for some property, just like a predicate-symbol, namely P : ℕ→Bool.
@F.Zer Yes that is indeed a stronger property about x.
But I didn't want to bother you with the distinction between properties and objects earlier, which is why I didn't say anything about your proof structure above.
It's just that you need to realize that PA has one axiom for each property, which literally means that those induction axioms grow longer and longer for longer properties.
There is no single axiom that generates all those induction axioms.
Similarly for strong induction.
For example, if A is a sentence and P is a property on ℕ, then Q, defined by Q(k) ≡ P(k) ∧ A for each k∈ℕ, would be a stronger property.
The point is that you do not necessarily have to know anything about P to construct stronger properties.
@user21820 I see. Thank you. I am starting to understand.
@user21820 Oh, if Q is stronger than P, it has to satisfy more conditions. So, Q is "telling me more" than P. If I am applying for a job A, and the only requirement is that I have basic computer skills, and a job B requires, additionally, basic English competency, job B is requiring more. Does this make sense ?
@user21820 for clarification , can you tell me what is the big difference between the logic you are currently teaching (formal FOL) and the logic that Mendelson is currently teaching (just for clarification).I am kind of worrying that my way of studying from mendelson is kind of pointless.
@Prithubiswas Right now, I'm teaching almost only how to use FOL. Part of that is how to use a deductive system for FOL, and only after learning that can one do mathematics fully rigorously. Before learning how to use FOL, it is unwise to attempt to study FOL (which is what most logic texts are about, Mendelson's included).
Of course, it's not pointless to learn from logic texts, but it's the wrong time for you to try.
Even if you ignore the parts of logic texts that study FOL, and only look at the parts describing a deductive system for FOL, there is still a huge difference from what I teach and what they describe. The reason is that there are many possible deductive systems for FOL, but the ones that are suitable for humans doing actual mathematics are not Hilbert-style, but logic texts tend to give Hilbert-style systems because those are easier to study!
A large fraction of good textbooks that aim to teach people to use FOL will present Fitch-style systems (like mine). I am biased, but I think mine is superior for practical use compared to most systems you can find out there.
@Prithubiswas ← Anyway, I do want you to finish fixing your solution using the (correct) properties you have found, after which I can explain more about this relation between induction and strong induction. Hopefully F.Zer will have also finished the task I gave him, since it is closely related, and then you can both benefit from looking at each other's work.
If for any property P on ℕ, P(0) ∧ ∀ k ∈ ℕ ( P(k) ⇒ P(k+1) ) ⇒ ∀ k ∈ ℕ ( P(k) ):
Given P on ℕ:
Given k ∈ ℕ:
If ∀ i ∈ ℕ ( i < k ⇒ P(i) ) ⇒ P(k): [Inductive hypothesis]
Given j < k:
If j < k:
If j < k + 1 ⇒ P(j):
...
For any property P on ℕ, ∀k∈ℕ ( ∀i∈ℕ ( i<k ⇒ P(i) ) ⇒ P(k) ) ⇒ ∀k∈ℕ ( P(k) )
@user21820, I worked on the proof and this is what I got so far.
@F.Zer I don't understand what you're doing. Earlier it was more correct.
If for any property P on ℕ, P(0) ∧ ∀ k ∈ ℕ ( P(k) ⇒ P(k+1) ) ⇒ ∀ k ∈ ℕ ( P(k) ):
Given property P on ℕ:
If ∀k∈ℕ ( ∀i∈ℕ ( i<k ⇒ P(i) ) ⇒ P(k) ):
...
For any property P on ℕ, ∀k∈ℕ ( ∀i∈ℕ ( i<k ⇒ P(i) ) ⇒ P(k) ) ⇒ ∀k∈ℕ ( P(k) )
You wrote this, with some useless (but not wrong) bits inside. But the outer structure was correct. In your last attempt, you got it wrong because you mixed up the order of ∀ and ⇒.
@user21820 Do I have to prove strong induction using induction or prove strong induction assuming induction is true ? I am not fully clear about that.
So, in the first case, I would assume "∀i∈ℕ ( i<k ⇒ P(i) ) ⇒ P(k)" holds, and try to prove "∀i∈ℕ ( i<k+1 ⇒ P(i) ) ⇒ P(k+1)" also holds. That was my latest attempt intention.
Strong induction isn't given as axioms in PA, but the point is that you can prove each instance of strong induction in PA. That's why strong induction is derivable from induction over PA without induction (i.e. PA−).
Whenever you use induction, you ought to explicitly define the property you want to apply it to. Otherwise you are more likely to confuse yourself.
:58309334 We say that a rule (or set of axioms) A can be derived from another rule B over formal system S iff each instance of A can be proven from S+B (i.e. S plus the rule B).
The reason we say it in such a roundabout manner is because A and B may not be given by finitely many axioms, so we can't say just S proves ( B ⇒ A ) as it just doesn't make sense.
These conceptual features of induction is also why PA is an important step in learning FOL. When you go on to Set Theory (such as ZFC), it too has such schemas (infinitely many axioms one for each XXX of a certain kind).
@user21820 You emphasised many times on the phrase "infinitely many axioms". I guess that is an important concept. Could you tell me a little bit more ? In the case of induction, do I have one and only one axiom for a specific P or there could be more than one ?
The point is just to understand that these axioms correspond to what you can actually define. Properties do not correspond to subsets of ℕ, and so induction in PA also does not apply to arbitrary subsets of ℕ, contrary to what a semi-crank on Math SE always keeps spouting.
So if you find me over-emphasizing this issue, it's probably because I'm unhappy with the nonsense that that user on Math SE spouts all the time.
@user21820, Ok, if I am working withing PA, and allowed to use all axioms (including induction), the proof skeleton could be reduced to this, I think:
Given P on ℕ:
If ∀k∈ℕ ( ∀i∈ℕ ( i<k ⇒ P(i) ) ⇒ P(k) ):
Given k ∈ ℕ:
...
∀k∈ℕ ( P(k) )
For any property P on ℕ, ∀k∈ℕ ( ∀i∈ℕ ( i<k ⇒ P(i) ) ⇒ P(k) ) ⇒ ∀k∈ℕ ( P(k) )
@user21820 Q(k) ≡ i < k ⇒ i < k+1, for all k ∈ ℕ. I should prove it using induction and then use it for the main proof. However, I am not sure if this is the right Q.
Given P on ℕ:
If ∀k∈ℕ ( ∀i∈ℕ ( i<k ⇒ P(i) ) ⇒ P(k) ):
Given k ∈ ℕ:
∀i∈ℕ ( i<k ⇒ P(i) ) ⇒ P(k)
Given i ∈ ℕ:
If i < k:
i+1 ≤ k
...
∀k∈ℕ ( P(k) )
For any property P on ℕ, ∀k∈ℕ ( ∀i∈ℕ ( i<k ⇒ P(i) ) ⇒ P(k) ) ⇒ ∀k∈ℕ ( P(k) )
@user21820, this is my latest proof outline. Unfortunately, I couldn't find a Q, even after looking closely at Prithu's work
Tinkering with the second half now. this is an (maybe) possible outline.
Statement:P(n) := "3^(-m) - 2^(-m) = f(-m) for all natural numbers m<=(n+1)" Base Case: P(0) holds. Inductive Case: P(n) -> P(n+1) Conclusion: P(n) holds for all n>=0……(i)
@user21820 just for clarifying , I used <= to mean "less than or equal". I dont know exactly how to type the proper symbol for it in chat because I am new here.
@Prithubiswas That's perfectly fine; programmers all can read that, and I am a programmer as well.
I can type symbols here because I am using an AutoHotkey script and a number of hotstrings to enable me to type symbols in every application, not just my browser. AHK is only available for Windows though.
I also read some posts about "hilbert style" and "fitch-style" and the pros and cons between them. Seems interesting .I might want to stick with hilbert style and learn fitch style later. I might not be able to comprehend with learning two styles at ones. (Maybe it is true that hilbert style is kind of impractical for proofs)
@Prithubiswas But if you cannot do formal proofs, you cannot study logic, so what's the point?
It doesn't work backwards; I've observed that almost all students who are unable to use a deductive system for logic get hopelessly confused in logic courses, even at the honours year level or graduate level.
There are always exceptions who unconsciously figure it out, but it's really risky.
Personally, I was lucky to learn programming before my undergraduate, and so when it came to mathematics I already did my proofs in roughly Fitch-style even before knowing there was such a thing, and then in my first year I had a lecturer who taught a natural deduction system, which is somewhat related to Fitch-style, so I ended up discovering Fitch.
To be honest , learning for me works kind of backwards for me. In fact , proofs kind of started to make some sense for me after studying logic FOL at a theoretical level instead of from a deductive system. I might be not competent to create proofs , but I could figure out the mistakes more easily.
@Prithubiswas That's precisely the problem; it should not have been like this. If you had learnt a deductive system from the start, you would have saved an immense amount of confusion and logical mistakes.
And I'm not saying you should switch over to Fitch-style just like that. I want you to first get a fully rigorous English proof of the test exercise using induction, before I show you what it looks like in formal Fitch-style, and then you can decide for yourself whether it is beneficial to learn it.
I will guarantee one thing; every mathematically competent person can read a Fitch-style proof without problems. In my undergraduate, I wrote all my proofs in actual exams in Fitch-style, and still got all my marks.
The style doesn't depend on the symbols, by the way. Writing "for every" instead of "∀" doesn't change the style. It's just that seeing it in purely symbolic form will drive home the point that it is 100% rigorous with no room for subjective intuition.
@Prithubiswas Sorry I forgot to reply to that! Give me a moment to think through it.
@F.Zer I also forgot to reply to that! Lol.
@F.Zer Yes that is right, and do you feel you get why you can prove P(n+1) from P(n) for that exercise I gave Prithu? And do you see why it is similar to what you want to do to derive strong induction? See, the "∀i∈ℕ ( i<k ⇒ P(i) )" in strong induction looks similar.
@Prithubiswas This outline works for the second part, yes.
@user21820 I kind of started studying logic as just a hobby , because I kind of wanted to know about what logic exactly meant , thus I am here. This is the same reason why I tried to learn "calculus" , because in the tintin comics , becuase in the "tintin" comic series , there was a charecture named "Professor Cuthbert Calculus". So yeah , i didn't know what I was doing at the time.
@Prithubiswas Ah hahaha. I also know Tintin, and Calculus. It's an amusing comic, though the biggest thing I dislike is that it portrays smoking and alcoholism in a slightly positive light. In any case, I'm glad you started dipping into calculus and logic. I hope you stick around for a while, because it won't be long before you can start to see the beauty of logic (even just in how basic FOL can be used for all of mathematics).
There was one and only one book in which Calculus invented a pill that would make alcoholics detest the taste of alcohol, but unfortunately it never continued in the later books. =|
@user21820, I wonder why I can't apply what I am learning playing Cosmic Express. I discovered I seem to have some (little) Logic reasoning skills since I've passed the first 11 levels without much trouble. But, this kind of Logic reasoning is really hard for me. You've just showed two similar patterns and I can't see why they are similar.
