Given a room with any (finite) number of people in it, if 1 of them is a redhead, then all of them are.

This is patently false, of course. Nonetheless we have the following "proof" by induction.

We'll denote the number of people in the room by n.

  • base case: n=1.
    This case is clear: it says that for a room with one person in it, if one of them (and there's only one) is a redhead, then all of them are redheads.
  • induction case: we shall suppose the untheorem true for n, and prove it for n+1.

    Consider a room with n+1 people in it, one of them a redhead. Ask one of the non-redheads to step outside the room for a moment. Then we are left with a room with n people in it, and one of them is (still) a redhead. By the induction hypothesis, all n people are redheads!

    Now ask the (only) non-redhead who stepped out to return to the room; ask some other person to step out, and again we're left with n people in a room, one of them (in fact, all but one of them!) a redhead. By the hypothesis, we deduce that all n are redheads, in particular the remaining person. Returning the redhead who stepped outside to the room, we see that all n+1 people are redheads.

By the principle of mathematical induction, the theorem is proved (or rather, the untheorem is unproven).

What's wrong here??

Notes about comments:
Both prole and DaVinciLe0 are giving wrong arguments. prole is mistaken about the proof: every time we ask someone who is not a redhead to step out, thus fulfilling the induction hypothesis. DaVinciLe0 says something about not being able to prove by induction anything regarding n people. Apparently he does not believe (a finite number of) people can be counted, since the primary way of telling if a set can be placed in a bijection with an initial subset of the naturals is to count it!

This is a common problem with this unproof: it's false, but for much simpler reasons than what people try to make up!

It's false because the induction step assumes n > 2.

You can't send out a non-redhead, bring them in, and then send out a different non-redhead if you only have one non-redhead.

SPUI's comment is mistaken on two counts:

a) If you have no people in a room, it is true that they are all redheads! This is because the converse is 'there is a person in the room who is not a redhead' which is false.

b) You don't need to do the "true for n=0" -> "true for n=1" step since we know it's true for n=1 anyway.

Oh, and how come these last three noders know words like probability, set, integer, function, and (gasp) bijection, when their grasp of maths is clearly about as good as my grasp of pre-twelfth-century formal Korean?...

Aozilla. You are entirely correct, but so am I. Our arguments are just slight variations on one another. The point we are both making is that when n=2, you cannot do the second sending-out and still have a red-head left in the room. My version was "You have to keep your original red-head, so there's no-one you can send out", and yours was "If you send out the other person, you have lost your red-head".
The following writeup is erroneous. I leave it here purely for the benefit of other fools like me who do not understand induction (and as of now, nine people have upvoted this, so there are some). Details at the end.

The mistake that glared at me when I read the original writeup came here:

"...we're left with n people in a room, one of them (in fact, all but one of them!) a redhead. By the hypothesis, we deduce that all n are redheads, in particular the remaining person."

(i.e. 1 person in room is a redhead, hypothesis states that if 1 person is redheaded all people in the room are, therefore all people in the room are redheaded)

This seems to be using the original "untheorem" to prove itself; you can't do that. This is a logical fallacy known as "begging the question". If it was valid, you could make the following, simpler argument:

Hypothesis: If one person in the room is redheaded, all of them are
Presume the existence of a room with n people in it, one of them redheaded
By the hypothesis, if one person is redheaded, all n of them are
Therefore, if one person is redheaded, all of them are, and the hypothesis is true

(actually, this is essentially the argument form used, as far as I can see, and the rest is simple handwaving)

Swap has informed me, albeit more politely, that I am in fact talking utter bollocks, due to my lack of sound mathematical training. When using induction, I now understand, once you have (un)proved the (un)theorem for the smallest possible value (in this case, one person), you can then take the theorem with regard to n to be true for the purpose of proving the theorem with regard to n+1. Since this was the manner in which the assumption was used, my criticism is wrong.

Log in or register to write something here or to contact authors.