4 ms·
So this article shows that you can infer S(n+1) from S(n) for n > 1, and a base case of S(1) is true. However, you can't infer S(2) is true from assuming S(1)
by cf-d-ycom 6y ago
So this article shows that you can infer S(n+1) from S(n) for n > 1, and a base case of S(1) is true.
However, you can't infer S(2) is true from assuming S(1) is true in the same way, ie. a group of 2, could be represented as two groups of S(1) and S(1). You can't claim these two S(1) groups share the same age.
This means that the base case and the inductive step are not connected, which means the proof is invalid.
- cheez 6y agoNot exactly, it was saying that you assumed S(2) implicitly which is wrong.
- cf-d-ycom 6y agoYeh, that makes more sense.
- solids 6y agoWhy can’t you asume S(2)? Is it not included in the inductive hypothesis S(k)?
- cf-d-ycom 6y agoSo the base case that they prove is S(1). And the inductive step is to show: S(1) ->(implies) S(2) -> S(3) -> S(4) -> .... Or to write it more succinctly, that S(n) -> S(n + 1) assuming S(n) is true. In this particular problem, the proof that is provided can be used to show S(2) -> S(3), that S(3) -> S(4), etc... are valid and true. However, the proof could NOT be applied to show that S(1) -> S(2). So whilst you CAN assume S(2) is true in a proof, the whole inductive chain needs to be attached to a valid base case.
- cheez 6y agoThe page gives a better explanation than I could :-)
- repsilat 6y agoIt's simpler than that -- the "proof" of the inductive step is just incorrect. It wouldn't be a theorem in a sound logical system.
- cf-d-ycom 6y agoPotentially. However, I believe the inductive step is correct. I could be wrong though. ie. If you assume S(2) is true, lets prove S(3), consider a set of 3 people, {a, b, c}. apply S(2) to {a, b} are therefore the same age, apply S(2)_ to {b, c} are therefore the same age, this implies a.age == b.age == c.age, there for S(3) is true. The inductive step is done. Thats what I thought made this a mind bender.
- repsilat 6y agoRight, it proves S(2)->S(3), but induction asks you to prove S(n)->S(n+1) for n in general, and not just for some n. The inductive proof doesn't work for S(1)->S(2), so it clearly can't work for the more general n->n+1.
- cf-d-ycom 6y agoI believe so yeh.
- pansa2 6y agoThe inductive step is fine, but it only works for n >= 2. The issue is a disconnect with the base case n = 1. However, if it were possible to prove the case n = 2, we would have a valid inductive proof for n >= 2.
- repsilat 6y ago> it only works for n >= 2 Right, so it doesn't work -- either it's a correct proof of a non-sequitur ("true for n implies true for n+1, provided n meets some criteria"), or an incorrect proof of an inductive step ("true for n implies true for n+1"). Because it's claimed to be proof by induction, it's meant to be the latter -- the person doing the proving claimed to have proven the inductive step, and their proof of it was incorrect.
- Aeolun 6y agoI got really confused when they just seemed to assume that. But that doesn’t appear to be what they consider the fallacious step.
- brazzy 6y agoIt doesn't just assume that, it proves it - but the proof has the hidden assumption that there are at least 3 elements in the set (of k+1 elements).
- leto_ii 6y ago> However, you can't infer S(2) is true from assuming S(1) is true in the same way, ie. a group of 2, could be represented as two groups of S(1) and S(1). Yup, I think this nails it. The more I think about this problem the more it seems meaningless to me. Adding the whole induction stuff just obfuscates this core problem. It seems to me that if you can prove S(2) you've immediately proven S(n). You don't need the subsequent induction.