1

I'm having some trouble with the following problem:

"A french man is trying to prove that any non empty group of french soccer players satisfies the following: 'if the group has at least one player who is better than Messi, then all the members of the group are better than Messi'.

To prove this, the french man uses induction on the number n of members of the set of soccer players. The statement is obvious if n=1. Let's suppose now that the statement is true for sets of k french players. We will use this to prove that the statement is true for every set of k+1 french players. Let {P1, P2,..., Pk+1,} be a set of k+1 french players. Let's suppose that at least one of them is better than Messi. Without losing generality, we can assume that P1 is better than Messi. Let's now consider the sets {P1, P3,..., Pk+1} and {P1, P2,..., Pk} (each one of these sets contains at least a player who is better than Messi).By the induction hypothesis, it follows that all the players of these sets are better than Messi, i.e., P1,P2,...,Pk+1 are better than Messi.

Where is the error in this argument?"

This is my guess:

We have 2 sets of players: {P1, P3,..., Pk+1} and {P1, P2,..., Pk}. I will call the first one S1 and the second one S2. Now, S1 ∪ S2 contains players that are better than Messi. I'm guessing that, somehow, S1 ∩ S2 is empty and, thus, S1 and S2 are disjoint.

Please help me!

Thanks.

Amanjo
  • 117

3 Answers3

1

When passing from $n=1$ to $n=2$ you have $\{P_1,P_2\}$. What happens when you remove $P_2$?

SPOILER

Your two sets are $\{P_1\}$ and you gain no information at all!

Pedro
  • 122,002
  • But if my two sets are {P1}, both sets contain a player who is better than Messi. What am I missing? – Amanjo Feb 16 '14 at 05:09
  • @user129120 Consider the case $n=2$ to $n=3$. Then you reduce your problem to ${P_1,P_2}$ and ${P_1,P_3}$. This gives you that $P_2,P_3$ are better than Messi, since $P_1$ is. But in the $n=2$, you get ${P_1}$ and ${P_1}$. This means $P_1$ is better than Messi. But that you already knew! How do you deduce anything about $P_2$? – Pedro Feb 16 '14 at 05:12
  • Excuse me but why do I get {P1} and {P1} when I use n = 2? – Amanjo Feb 16 '14 at 05:25
  • You have ${P_1,P_2}$. If we assume $P_1$ is a player better than Messi, the algorithm in the proof dictates we eliminate the first two distinct players after this one, $P_2,P_3$. Sadly, there is only one in this case, $P_2$. That's where the proof fails. – Pedro Feb 16 '14 at 05:27
1

The problem with the proof, is that the statement uses conditional and not universal quantifier. This is best when written out in English (sorry I don't know French). I am essentially restating what Pedro Tamaroff has as comments.

Here is the complete statement for $n=2$ completely written out.

Let the set be $P_1$ and $P_2$ and suppose that $P_1$ is better than Messi.

We now have

  1. $P_1$ is better than Messi (by assumption), and if $P_1$ is better than Messi then $P_1$ is better than Messi (induction hypothesis for $n-1$); so $P_1$ is better than Messi. So far so good
  2. If $P_2$ is better then Messi then $P_2$ is better than Messi (induction hypothesis for $n=1$). Therefore $P_2$ is better than Messi

It is now clear where the logic breaks down. The conclusion in bold is clearly not valid.

user44197
  • 9,730
0

This is basically the same as has been given in other answers and comments but perhaps I can explain it in a different way.

First consider the step where you assume the result is true for sets of $2$ players and you want to prove it for sets of $3$ players. So, you will consider the set $\{P_1,P_2,P_3\}$ and you will take two subsets $\{P_1,P_3\}$ and $\{P_1,P_2\}$ - that is, for one subset you ignore your second player, for the other you ignore the last. Since you are assuming the result for sets of $2$ players and you know $P_1$ is BTM (better than Messi), both $P_2$ and $P_3$ are BTM. This all seems OK.

But now go back one step and consider the case when you assume the result is true for sets of $1$ player and you have to prove it is true for sets of $2$ players. You will consider the set $\{P_1,P_2\}$ and you will take two subsets: ignoring the second player gives you the subset $\{P_1\}$, and ignoring the last player also gives you the subset $\{P_1\}$. You know that in each of these sets, every player is BTM, but that does not tell you anything at all about $P_2$ as he has "disappeared" from consideration.

Hope this helps.

David
  • 82,662