All People in Canada are the Same Age (1997)
math.toronto.edu
math.toronto.edu
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.
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.
However, if it were possible to prove the case n = 2, we would have a valid inductive proof 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.
However, it must be coupled with a base case >= 2, which isn’t the case here. The only base case proven is 1.
See also “Induction basis other than 0 or 1” [0].
[0] https://en.wikipedia.org/wiki/Mathematical_induction#Inducti...
Nobody was trying or claiming to be doing any other kind of induction. They said they had the base case and the inductive step, and they were clear about the base case and the inductive step. Their proof of the base case was correct, and their proof of the inductive step did not prove what they said it did. It doesn't matter what it did prove.
I don't know if I'd call it a mind bender, but it does demonstrate that if one holds that all groupings of two individuals must be uniform with regard to an attribute A, then it follows that any grouping of individuals must be uniform with regard to A.
A simple proof by contradiction:
1) Assume some group of more than 2 individuals is not uniform with regard to A
2) There must be at least one pair of individuals for which attribute A differs
3) Create a subgrouping of one of those pairs
4) Now we have a grouping of 2 individuals which is non-uniform with regard to A
5) But we originally held that all groupings of 2 individuals must be uniform with regard to A
6) Contradiction! Hence a non-uniform grouping with regard to A is impossible, Q.E.D.
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.
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.
https://www.math.toronto.edu/mathnet/falseProofs/fallacies.h...
The last one in particular I thought was interesting
Then I realized the aim is to trick you by playing a bit fast and loose with that convention, and hoping you don't notice. e.g. I stumbled at Step 4, and if you click on the details for it the authour admits k is ill-defined. That comes back to bite you when you hit the fallacious step.
I'm fascinated how some very old works by ancient physicists and mathematicians are written using plain (if verbose) language and diagrams, and you didn't need to learn a bunch of shorthand conventions specific to the field in order to participate. Does anyone know any good books on Quantum Mechanics that don't require you to learn Dirac notation first?
This is a very common example in math classes, though in my experience usually presented as a proof that "all horses are the same color".
No cat has eight tails, and every cat has one more tall than no cat. Ergo...
> See if you can figure out in which step the fallacy lies. When you think you've figured it out, click on that step and the computer will tell you whether you are correct or not, and will give an additional explanation of why that step is or isn't valid.
The problem is that we establish the base cases S(0) and S(1), and then we establish the inductive step S(n) -> S(n+1) subject to the restriction that n > 1. But this proof never demonstrates that S(1) implies S(2). The proof is completely correct that S(2) implies S(3), S(3) implies S(4), and so on.
When step 9 says "Let R be someone else in G other than P or Q", the existence of a person in G other than P or Q has not been demonstrated. G is an arbitrary group of k+1 people, and the highest k for which our statement is known to be true is 1. Thus, the minimum size of G is 2, and R may not exist.
"in every group of k people, everyone has the same age"
You can't use your conclusion in your assumption!
In short: You fix k and assume that S(k) holds. If you can show that this always implies that S(k+1) holds, all you need is a base case (e.g. S(1) being true) to "recursively" prove that S(n) holds for all n >= 1 (or whatever your base case was).
Here the fault is that the induction step (proving S(k+1) from S(k)) requires k >= 2 but only specifically S(1) was proven.
It's way more confusing than simply "If A, then B", and I'm not sure why the wording hasn't fallen out of favor, but that's what it is.
Even when doing classic logic, I start with my constructive intuition and the sprinkle in the continuation-passing-style spooky magic when needed to get back the classical craziness.
Everyone should learn constructive first.
[1] https://www.amazon.com/Elements-Discrete-Mathematics-C-Liu/d...
The author shows that S(n)->S(n+1) and that proof is correct if n is at least larger than 1. The hidden assumption of n>1 is the "gotcha" moment, but that part of the proof is still valid as induction step. Imagine starting with this and amending the instructions with "given that n>1".
However, for the purpose of showing that all Canadians are the same age, we now need to find a base case - the first (and now second) step of induction. And here, we see that while n->n+1 holds (for n>1), there simply isn't any n>1 for which S is true! The case of S(1) is irrelevant, since it's not included in the assumption of the induction step.
If we would have started with the induction step, and concluded that our argument holding for n>1 is good enough, we would have then clearly realized that there is no base case and therefore we can not complete the induction proof.
https://en.wikipedia.org/wiki/Doomsday_argument
"In other words, we could assume that we could be 95% certain that we would be within the last 95% of all the humans ever to be born."
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?
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.
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.htm...
> 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.
---
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?
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!
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.
It took me a couple visits to realize that each `Step 1` `Step 2` heading is a link to an explanation for why that step holds true.
"born after 1800"
It seemed so ridiculous to teenage me that such a thing could be said. In 2020 it has been said. I’m no longer falling out of my seat laughing.
Assumption 1. If you are not a racist then you should not support racist policies.
Assumption 2. The opposition wants to enact racist policies while I do not.
Proposition 3. From 2, if you vote for my opposition then you are supporting racist policies.
Theorem 4. Therefore, from 3 and 1, if you don't vote for me then you are racist because you are supporting racist policies.
Assumptions 1 and 2 could be incorrect in certain circumstances (in particular assumption 2), but the reasoning is correct.
That may seem extreme, but what if candidate #1 is racist, but candidate #2 has vowed to eliminate funding for medical care I need to live and can't afford on my own? Is voting for #1 racist?
"A Kafka trap is a fallacy where if someone denies being x it is taken as evidence that the person is x since someone who is x would deny being x. The name is derived from the novel The Trial by the Austrian writer Franz Kafka."
I think this concept is better known under the name "witch hunt".
For each person who voted for Trump in 2016, at least one of the following statements is true. (A) The person was uninformed as to Trump's character. (B) The person was actively being misinformed as to Trump's character, in such a way that correct information was not believed. (C) The person did not believe that racism was a disqualifying factor for office.
Whether this statement reduces to the "vote for X or admit to being racist" depends on several additional statements that I don't think can be entirely stated. First, it asserts that (A) is false, that the amount of media coverage in an election is enough that no voters are uninformed. Second, it asserts that (B) is false, that there was no active misinformation being spread during the 2016 election. Given what we know now, (B) is most certainly true in some cases. Third, it asserts that (C) is equivalent to a person being racist, which is a valid position, but one that is harder to discuss without getting into the nuances of systemic racism.
This also gets into the point where racism will continue to exist so long as "not racist" is seen as one end of the spectrum. Rather, in order to be appropriately egalitarian, one must be anti-racist wherever society is racist.
There is research to indicate people respond to visual cues as an indicator of in-group/out-group tribalism, but that mental software can be overrun by observing the individual as opposed to categorizing the individual into a group. https://greatergood.berkeley.edu/article/item/look_twice This would be connected to one's communication that can be overcome.
As well as this, G. Loury describes racial stigma, which is to observe existing race gaps as a combination of past racist policies, exacerbated by present egalitarian/meritocratic policies, where the inequality is incorrectly ascribed to innate, immutable characteristics of race, rather than a consequence of an individual/hobbled community starting 50 meters behind everyone else in a 100m sprint. https://www.irp.wisc.edu/publications/focus/pdfs/foc241a.pdf This would be connected with one's worldview which can be overcome by understanding racism within history, as well as global weather distributions, and geographical resource distribution (Guns, Germs and Steel by Jared Diamond).
And I don't think I need to cite anything about racist ideas not covered by the above can be overcome by using enlightenment values and unifying messages.
I'd say trump has proclaimed some very racist ideas which run against enlightenment values and consequently are repulsive. There are obviously some percentage of followers of trump that hold worldviews that I'd find repulsive due to my alignment with enlightenment values. That doesn't mean the ideas these people hold are immutable.
Whilst my main political priority is minimising inequality at large, which in this context will disproportionately assist populations currently in poverty and resolve a lot of racial tension and racial stigma, policies that DON'T assist communities suffering from poverty should not be assumed to be racist, but rather are exacerbating gaps generated from previous racist(read discriminating by skin colour) policies. Whilst it might be unpalatable, I believe it is more realistic when you consider a large part of the American dream is about pulling yourself up from your bootstraps.
Also, Trump holds positions on economics that resonate large swathes of the American populous in communities that have been decimated by both automation, and job exportation, as pointed out by Andrew Yang. And as scarcity replaces abundance, individual's sphere of compassion shrinks. As a general example, consider who you would be considerate to if you were in an unescapable location undergoing famine.
Whilst I appreciate the desire to simplify the world around you which all humans try to do, I think to try to compress an individual's political worldview into 3 binary dimensions is dropping the majority of an individual's motivation.
I'd say that the main cause of racial gaps is historical institutional racism, that are exacerbated by today's egalitarian/meritocracy policies practices. And since the 1970s, corporate America began it's ascendance to decimate the middle class, rural America, collective bargaining, profit over economic equality, and almost completely corrupt the political system. This means to me that the biggest problem in America is political corruption and corporate power/corruption which results in increased inequality. Solve that and I think America's other problems of racial stigma, various important gaps across populations, lack of national pride, strength of democracy locally and globally, and the decreasing ability to pursue happiness in America would be much easier to solve.
This is just one Australian's opinion though. I might be wrong about the whole thing.
There are people who believe abortion is murder and still vote in pro-choice candidates because the other policy positions are important to uphold.
The fallacy is assuming that a group with more than 1 person has the same age.
It would be ok to assume this if we were looking for a proof of contradiction, but this statement is never challenged nor contradicted
This sounds very much like those "gotchas" that confuse more than help
The fallacy is in step 9 combined with step 1. Step 9 requires at least 3 people to exist - P, Q, and R. So, step 9 only works for k>=2. So, we have proved S(1),S(k>=2) => S(k+1), but we haven't proved S(2).
Of course, S(2) (in any group of 2 people, both people have the same age) is not true, so the whole conclusion is false.
In inductive proofs you always need to prove some rule that says 'for any k [with some property], assuming case k is true, then case k+1 is true as well', and then you also need to prove that, for some k [with the given property], case k is actually true.
Restating the proof in the article in these terms, step 9 correvtly proves that, for any k [greater than or equal to 2], if S(k) then S(k+1). But there is no proof given that there exists some k>=2 for which the statement actually holds, and in fact it can proved that NO such k exists. So overall the proof doesn't hold.
You're taking a false premise and running with it, then tripping far ahead and saying that's the fallacy.
> but we haven't proved S(2).
Well, not surprising you haven't proven it, because you're already deep down in the mud on steps 7 and 8
> Step 7: Consider everybody in G except P. These people form a group of k people, so they must all have the same age
> Step 8: Consider everybody in G except Q. Again, they form a group of k people, so they must all have the same age.
Given that
> Let G be an arbitrary group of k+1 people
This is already false
Saying that
> Let R be someone else in G other than P or Q.
Is something completely natural for a group with k+1 elements (with the exception of k < 3), but the "proof" is so deep down in its absurdity at this point calling this the fallacy is almost a technicality
The trick in this proof is that the steps for proving k+1 in terms of k don't work for all k > 1, which invalidates the generalization that the induction depends on. The steps obscure an extra predicate on the generalization, so that it's not fully general.
If the proof (of some other property) didn't have that hidden predicate, or something like it, it would be fine. The problem really is that far down.
> in this proof is that the steps for proving k+1 in terms of k don't work for all k > 1,
Yes and those are steps 7 and 8, not step 9. Because that "proof" is already wrong. It comes from a wrong premise, surely, but that's already wrong at this time
This is why I'm calling BS on step 9 being the fallacy there.
> Step 5: Let G be an arbitrary group of k+1 people
> Step 7: Consider everybody in G except P. These people form a group of k people, so they must all have the same age (Right conclusion from wrong premises)
> The trick in this proof is that the steps for proving k+1 in terms of k don't work for all k > 1,
7 and 8 doesn't work for any k > 1, it's not "for all" it's "for any". That's why this is so ridiculous
Step 9 fails for k<=1 and k=2 and that's it.
So yeah the induction doesn't work, but it's not only because of step 9, it's because of 7/8 (which are just erroneous conclusions of a false premise)
The greater point of the excersise is to show a failure mode of an inductive proof. If the property hadn't been so clearly false, it may have been harder to spot the actual mistake ; the excersise is meant to prepare you for those other cases.
The logical formula is right but the premise is wrong. But 7 is considering both.
It's like saying "Person P had 1Mi dollars and got 10% interest last year then now Person P has 1100k dollars". But Person P didn't. The interest calculation is correct, but the premise is wrong.
> The greater point of the excersise is to show a failure mode of an inductive proof.
I see that, but the fact that the other steps are not contributing to the solution makes it harder to argue that the mistake is there. Because that statement needs a qualifier, but it is "not wrong" per se (it's not even affirming anything, it's just saying "pick the person you haven't picked (from a group that might not have anyone else to pick, fair enough)
But everything derived from a false premise can be false. That's how we get the proofs by contradiction, right? We keep going down the wrong path until it obviously blows up
Or we could just prove this whole problem false with a set of two people in Canada with different ages (counterexample to Step 5). Case closed.
No it is not like that. It is like saying "IF person P had 1Mi dollars and got 10% interest last year THEN now Person P would have 1100k dollars". This statement is true regardless of how much money person P has today. That is how steps 5-8 work: they are true regardless of the truth of the antecedent ('in every group of k people, everyone has the same age'). Finding 2 people in Canada of the same age would NOT prove step 5 wrong (though it would show it to be pointless, of course).
Probably a much more interesting problem would have found a less obviously wrong premise to demonstrate this with. I'd love to find a way to build a similar argument for Fermat's last theorem or some other non-trivial observation.
Steps 7 and 8 are perfectly fine. Everything up to that point is perfectly fine. The problem is only in step 9, exactly in that "with the exception of k < 3" (actually k<2) - because the trivially true base case of k=1 is that exception. The induction step is correct, it just doesn't work for the only available true base case.