6 ms·

I don't understand some things regarding the resoning: If you assume S(n) is true, n being any natural number, what good does it to to prove that S(n+1) is als

I don't understand some things regarding the resoning: If you assume S(n) is true, n being any natural number, what good does it to to prove that S(n+1) is also true since it is included in the initial assumption imho. If you define "P and Q are any members of G" then "everybody in G except P" can only mean to me an empty group. Also "Let R be someone else in G other than P or Q" can only mean R must be outside the group. Can somebody explain these to me?

zwaps 6y ago
Edit: Let me try to be as clear as possible. Your confusion comes from the language in the question of "ANY SPECIFIC N" versus "ANY, as in ALL N". Say, n=3. Then, we assume S is true for the value n=3, but we don't yet know if S holds for any other n (1,2,4,100 etc.), which we have not assumed. However, we show that IF S is true for n=3, THEN that alone implies it's also true for 4 (n+1). Of course then, we could probably show the same process for SOME value of n, 3 or otherwise, and the corresponding n+1! So instead of writing n=3, we just write n and save ourselves the task of having to check all those numbers. Nevertheless, our assumption was that S was true for one specific n, and not all n at the same time! So we do two things, and it makes sense to think of it in reverse order. First, if S is true for any specific n we pick (and not necessarily ALL other n), is it THEN also true for n+1? At this stage, we have identified two "n" for which S holds of all possible n. More precisely, we have picked one and assumed S holds, and then found a second one. However, note that the choice of which n we assume to be true was "free" among ALL n. Think of "dynamics" instead of "state" if you are an engineer. But we started with the assumption that S is true for at least one n, the n we chose. Maybe we can not find such an n, in which case it doesn't matter that it would also be true for n+1. Therefore, the second question is: can we find an n for which S is true? Then it's true for ALL n! But we need the two components. We need to know the relationship of n->n+1, and we need at least one "real" value of n where S does in fact hold. Your second question is similar. The author means: Pick any two members of G, but you gotta pick two specific members. Since the proof works independently of whom you pick, it goes through for all others. However, it does not mean that you "pick all members" of G! The "gotcha" moment you had, seeing that the choice of the two members was arbitrary, is usually what completes such a proof. You show the thing you want to show for two specific members of G, but then you circle back and state proudly: "But see, I could have picked ANY member of G. Hence, this must holds for all "dyads" of two people in G!" Edit: And to understand why the proof fails - the author does not actually proof the n->n+1 step for any arbitrary n, only for n>=2. The specific "real" value he finds, however, is n=1. Therefore, the two steps are disconnected, the n->n+1 does not hold if n=1. And this is precisely where the "ANY n" versus "ANY as in ALL n" comes into play again. n=1 is qualitatively very different to n=2. S is obviously true for n=1 (one person), but it's obviously not always true for n=2 (two people). While the author proofs that n=2 implies S for all n, this is not true if we start with n=1. However, n=1 is the only thing we can actually show to be really true. In that sense, for the purpose of showing that all Canadians are of the same age, the asserted step of n->n+1 (given n>1) is irrelevant, because we can not find such an n>1 where we can show that this is true! Here you can see that while we do the proof for any arbitrary but specific n, not assuming it is true for any other value of n, we still need to ensure that we do in fact mean ANY of the n we can pick, including n=1!
- trabant00 6y ago
  > our assumption was that S was true for one specific n, and not all n at the same time And here is where my problem with the reasoning is. The example in "A Brief Review of the Principle of Induction" makes no such error. It calculates for 1, and it calculates for n and n+1, in which the n can really by any n as in "all n". Also, no assumption there. So in my understanding the fallacies start at step 3.
schmuelio 6y ago
So induction is a useful method of proving stuff. You can't prove that S(n) is true for all values of n by just going through each possible n and proving it, since n can be anything so you'll be there a while. The way this works is, you attempt to show that _if_ S(n) is true, _then_ S(n+1) is also true. Then you show that S(1) is true. Since S(n) being true implies that S(n+1) is also true, you can show that S(2) is true since 2 = 1+1 (you've proven the case where n=1). Then since S(2) is true, so is S(3), and S(4), S(5), ... and so on. The way the links proof works is: You show that S(1) is true. The set of 1 person {A} must have everyone in that set being the same age (there's only one person in it after all). The next step is to show that if S(n) is true, then S(n+1) is also true. To do this we can take an example set of people {P,Q,R}, in this case we are saying that this is the group of n+1 people (so n=2). We can take {Q,R} (the set of everyone except P) and know that they are the same age (since we have assumed S(n) to be true, as long as we can show this relation works, we only need to prove one value of n to prove all of them, and we've already done this with S(1)). We can also do this for the set {P,R} using the same reasoning. Since Q=R (Q and R are the same age) and P=R, we can prove that P=Q since P=R=Q. This shows that as long as S(n) is true, so is S(n+1). Where this proof breaks down is this proof only works for a set of people larger than 2. So we haven't actually proven that S(1) being true implies S(2) is true, since this relation does not hold, we can't rely on S(n) being true.
istjohn 6y ago
> If you assume S(n) is true, n being any natural number, what good does it to to prove that S(n+1) is also true since it is included in the initial assumption imho. Read the explanation on induction at the bottom if you haven't yet[1]. This is induction. The idea is to prove that for any 'n' for which S(n) is true, S(n+1) is true also. I'm guessing Step 4 is where the wording tripped you up? > Step 4: We can do this by (1) assuming that, in every group of k people, everyone has the same age; then (2) deducing from it that, in every group of k+1 people, everyone has the same age. Maybe its meaning is more clear stated this way: Step 4: We can do this by showing that (1) for any k where it is true that "within every group of k people everyone has the same age," then (2) showing that it necessary follows that "within every group of k+1 people everyone has the same age." [1] https://www.math.toronto.edu/mathnet/falseProofs/sameAge.html#1 https://www.math.toronto.edu/mathnet/falseProofs/sameAge.htm...
- trabant00 6y ago
  I understand (at some level) what induction is. But the example given in the explanation of induction in the bottom is fundamentally different in that it does not assume anything. It simply calculates the formula for 1 and n+1 and both fit it. > Step 4: We can do this by showing that (1) for any k where it is true that "within every group of k people everyone has the same age," then (2) showing that it necessary follows that "within every group of k+1 people everyone has the same age." Try as I might this only looks like circular reasoning to me.
  - istjohn 6y ago
    Let me try again. Think of Step 4 like this: --- STEP 4 REDUX RELOADED Imagine a powerful argument. Let's call it "The Decider." "The Decider" is a series of logical steps that allows us to go from A to B, where A is a certain set of assumptions or facts that we know to be true, and B is a conclusion that we can demonstrate must be true if A is true. We can use the metaphor of a machine. “The Decider” is a machine that takes material in on one side, and spits out a product on the other. The input material is facts or assumptions, and the output is new facts or assumptions that logically follow from the input. For now, let's not worry about how "The Decider" works. Let's just imagine that there is in fact some way to fabricate such a logical apparatus that works the way we need it to work. Now, suppose that the kind of fact “The Decider” ingests is a very special kind of fact. If you tell it “the sky is blue,” the metaphorical gears within “The Decider” grind to a halt. It doesn’t know what to do with this kind of fact. Instead, it requires a fact of the following form: IN: “Within any group of k people, everyone has the same age.” So for example, you can tell “The Decider”: IN: “Within any group of 1 person, everyone has the same age.” And “The Decider” will grind away until it spits out a shiny new assertion that must be true if your input was true. In fact, let’s suppose that the shiny new assertion “The Decider” would produce in this case would be: OUT: “Within any group of 2 people, everyone has the same age.” You could tell “The Decider,” IN: “Within any group of 9 people, everyone has the same age.” and it would work, too. OUT: “Within any group of 10 people, everyone has the same age.” In fact, “The Decider” follows a pattern. Whatever value k is in the input, the number in the output will be k+1. In other words, for any k that is a positive whole number, “The Decider” can turn “within any group of k people, everyone has the same age” into “within any group of k+1 people, everyone has the same age.” If “The Decider” actually existed, if there was a general pattern of reasoning that could be used to go from A to B in this way, we would accomplish the task set out for us in Step 3. Namely, we would prove that, “whenever S(n) is true for one number (say n=k), it is also true for the next number (that is, n=k+1).” END STEP 4 REDUX RELOADED --- Steps 5 through 13 then proceed to describe how “The Decider” actually works. Or at least they try to. That is, they describe a general pattern of reasoning that purportedly can be used to show that if “within any group of 9 people, everyone has the same age,” then it must also be true that “within any group of 10 people, everyone has the same age.” It can also show that if it is true that “within any group of 2 people, everyone has the same age,” then it must also be true that “within any group of 3 people, everyone has the same age.” In fact, Steps 5 through 13 endeavor to create a logical argument so powerful that it can take any statement of the form “within any group of k people, everyone has the same age” and demonstrate that if that is true, it’s also true that “within any group of k+1 people, everyone has the same age.” This is “The Decider” I describe above. Spoiler The argument ultimately falls down because “The Decider” has a fatal flaw. When k=2, the logical machinery chokes. It implicitly relies on k being greater than or equal to 3. Is that helpful at all?

zwaps 6y ago

Edit: Let me try to be as clear as possible. Your confusion comes from the language in the question of "ANY SPECIFIC N" versus "ANY, as in ALL N". Say, n=3. Then, we assume S is true for the value n=3, but we don't yet know if S holds for any other n (1,2,4,100 etc.), which we have not assumed. However, we show that IF S is true for n=3, THEN that alone implies it's also true for 4 (n+1). Of course then, we could probably show the same process for SOME value of n, 3 or otherwise, and the corresponding n+1! So instead of writing n=3, we just write n and save ourselves the task of having to check all those numbers. Nevertheless, our assumption was that S was true for one specific n, and not all n at the same time! So we do two things, and it makes sense to think of it in reverse order. First, if S is true for any specific n we pick (and not necessarily ALL other n), is it THEN also true for n+1? At this stage, we have identified two "n" for which S holds of all possible n. More precisely, we have picked one and assumed S holds, and then found a second one. However, note that the choice of which n we assume to be true was "free" among ALL n. Think of "dynamics" instead of "state" if you are an engineer. But we started with the assumption that S is true for at least one n, the n we chose. Maybe we can not find such an n, in which case it doesn't matter that it would also be true for n+1. Therefore, the second question is: can we find an n for which S is true? Then it's true for ALL n! But we need the two components. We need to know the relationship of n->n+1, and we need at least one "real" value of n where S does in fact hold. Your second question is similar. The author means: Pick any two members of G, but you gotta pick two specific members. Since the proof works independently of whom you pick, it goes through for all others. However, it does not mean that you "pick all members" of G! The "gotcha" moment you had, seeing that the choice of the two members was arbitrary, is usually what completes such a proof. You show the thing you want to show for two specific members of G, but then you circle back and state proudly: "But see, I could have picked ANY member of G. Hence, this must holds for all "dyads" of two people in G!" Edit: And to understand why the proof fails - the author does not actually proof the n->n+1 step for any arbitrary n, only for n>=2. The specific "real" value he finds, however, is n=1. Therefore, the two steps are disconnected, the n->n+1 does not hold if n=1. And this is precisely where the "ANY n" versus "ANY as in ALL n" comes into play again. n=1 is qualitatively very different to n=2. S is obviously true for n=1 (one person), but it's obviously not always true for n=2 (two people). While the author proofs that n=2 implies S for all n, this is not true if we start with n=1. However, n=1 is the only thing we can actually show to be really true. In that sense, for the purpose of showing that all Canadians are of the same age, the asserted step of n->n+1 (given n>1) is irrelevant, because we can not find such an n>1 where we can show that this is true! Here you can see that while we do the proof for any arbitrary but specific n, not assuming it is true for any other value of n, we still need to ensure that we do in fact mean ANY of the n we can pick, including n=1!

trabant00 6y ago
> our assumption was that S was true for one specific n, and not all n at the same time And here is where my problem with the reasoning is. The example in "A Brief Review of the Principle of Induction" makes no such error. It calculates for 1, and it calculates for n and n+1, in which the n can really by any n as in "all n". Also, no assumption there. So in my understanding the fallacies start at step 3.

schmuelio 6y ago

So induction is a useful method of proving stuff. You can't prove that S(n) is true for all values of n by just going through each possible n and proving it, since n can be anything so you'll be there a while. The way this works is, you attempt to show that _if_ S(n) is true, _then_ S(n+1) is also true. Then you show that S(1) is true. Since S(n) being true implies that S(n+1) is also true, you can show that S(2) is true since 2 = 1+1 (you've proven the case where n=1). Then since S(2) is true, so is S(3), and S(4), S(5), ... and so on. The way the links proof works is: You show that S(1) is true. The set of 1 person {A} must have everyone in that set being the same age (there's only one person in it after all). The next step is to show that if S(n) is true, then S(n+1) is also true. To do this we can take an example set of people {P,Q,R}, in this case we are saying that this is the group of n+1 people (so n=2). We can take {Q,R} (the set of everyone except P) and know that they are the same age (since we have assumed S(n) to be true, as long as we can show this relation works, we only need to prove one value of n to prove all of them, and we've already done this with S(1)). We can also do this for the set {P,R} using the same reasoning. Since Q=R (Q and R are the same age) and P=R, we can prove that P=Q since P=R=Q. This shows that as long as S(n) is true, so is S(n+1). Where this proof breaks down is this proof only works for a set of people larger than 2. So we haven't actually proven that S(1) being true implies S(2) is true, since this relation does not hold, we can't rely on S(n) being true.

istjohn 6y ago

> If you assume S(n) is true, n being any natural number, what good does it to to prove that S(n+1) is also true since it is included in the initial assumption imho. Read the explanation on induction at the bottom if you haven't yet[1]. This is induction. The idea is to prove that for any 'n' for which S(n) is true, S(n+1) is true also. I'm guessing Step 4 is where the wording tripped you up? > Step 4: We can do this by (1) assuming that, in every group of k people, everyone has the same age; then (2) deducing from it that, in every group of k+1 people, everyone has the same age. Maybe its meaning is more clear stated this way: Step 4: We can do this by showing that (1) for any k where it is true that "within every group of k people everyone has the same age," then (2) showing that it necessary follows that "within every group of k+1 people everyone has the same age." [1] https://www.math.toronto.edu/mathnet/falseProofs/sameAge.html#1 https://www.math.toronto.edu/mathnet/falseProofs/sameAge.htm...

trabant00 6y ago
I understand (at some level) what induction is. But the example given in the explanation of induction in the bottom is fundamentally different in that it does not assume anything. It simply calculates the formula for 1 and n+1 and both fit it. > Step 4: We can do this by showing that (1) for any k where it is true that "within every group of k people everyone has the same age," then (2) showing that it necessary follows that "within every group of k+1 people everyone has the same age." Try as I might this only looks like circular reasoning to me.
- istjohn 6y ago
  Let me try again. Think of Step 4 like this: --- STEP 4 REDUX RELOADED Imagine a powerful argument. Let's call it "The Decider." "The Decider" is a series of logical steps that allows us to go from A to B, where A is a certain set of assumptions or facts that we know to be true, and B is a conclusion that we can demonstrate must be true if A is true. We can use the metaphor of a machine. “The Decider” is a machine that takes material in on one side, and spits out a product on the other. The input material is facts or assumptions, and the output is new facts or assumptions that logically follow from the input. For now, let's not worry about how "The Decider" works. Let's just imagine that there is in fact some way to fabricate such a logical apparatus that works the way we need it to work. Now, suppose that the kind of fact “The Decider” ingests is a very special kind of fact. If you tell it “the sky is blue,” the metaphorical gears within “The Decider” grind to a halt. It doesn’t know what to do with this kind of fact. Instead, it requires a fact of the following form: IN: “Within any group of k people, everyone has the same age.” So for example, you can tell “The Decider”: IN: “Within any group of 1 person, everyone has the same age.” And “The Decider” will grind away until it spits out a shiny new assertion that must be true if your input was true. In fact, let’s suppose that the shiny new assertion “The Decider” would produce in this case would be: OUT: “Within any group of 2 people, everyone has the same age.” You could tell “The Decider,” IN: “Within any group of 9 people, everyone has the same age.” and it would work, too. OUT: “Within any group of 10 people, everyone has the same age.” In fact, “The Decider” follows a pattern. Whatever value k is in the input, the number in the output will be k+1. In other words, for any k that is a positive whole number, “The Decider” can turn “within any group of k people, everyone has the same age” into “within any group of k+1 people, everyone has the same age.” If “The Decider” actually existed, if there was a general pattern of reasoning that could be used to go from A to B in this way, we would accomplish the task set out for us in Step 3. Namely, we would prove that, “whenever S(n) is true for one number (say n=k), it is also true for the next number (that is, n=k+1).” END STEP 4 REDUX RELOADED --- Steps 5 through 13 then proceed to describe how “The Decider” actually works. Or at least they try to. That is, they describe a general pattern of reasoning that purportedly can be used to show that if “within any group of 9 people, everyone has the same age,” then it must also be true that “within any group of 10 people, everyone has the same age.” It can also show that if it is true that “within any group of 2 people, everyone has the same age,” then it must also be true that “within any group of 3 people, everyone has the same age.” In fact, Steps 5 through 13 endeavor to create a logical argument so powerful that it can take any statement of the form “within any group of k people, everyone has the same age” and demonstrate that if that is true, it’s also true that “within any group of k+1 people, everyone has the same age.” This is “The Decider” I describe above. Spoiler The argument ultimately falls down because “The Decider” has a fatal flaw. When k=2, the logical machinery chokes. It implicitly relies on k being greater than or equal to 3. Is that helpful at all?