0

I was given a complete proof and have to figure out the flaw that prevents the argument from being valid but I can't find it. I thought maybe it had something to do with replacing A and removing B but I am not sure. If anyone sees the error and can explain it to me I would greatly appreciate it!

Claim: For all $n ≥ 1$, in every group of $n$ cats, all cats have the same name.

Proof: We proceed using induction. Define $P(n)$ to be the statement “in every group of $n$ cats, all cats must have the same name.”

Base case: In a group consisting of only one cat, the claim is trivially true. In other words, $P(1)$ is true.

Inductive step: Suppose that $P(n)$ is true. In other words, suppose that in every group of $n$ cats, all cats have the same name. We want to show that in every group of $n + 1$ cats, all cats have the same name.

Consider an arbitrary group of $n + 1$ cats. Temporarily remove a cat (let’s call it cat $A$) from the group, so that you are left with a group containing $n$ cats. By our supposition, these cats all have the same name. Now replace cat $A$ and remove a different cat, cat $B$. The remaining group contains $n$ cats, so again they must all have the same name. Since we’ve already shown that cat $B$ also has this name, we can conclude that all $n + 1$ cats have the same name. Thus $P(n + 1)$ is true.

Applying the principle of mathematical induction, all cats have the same name. QED

egreg
  • 238,574
  • 2
    https://en.wikipedia.org/wiki/All_horses_are_the_same_color Same problem, different items – John Lou Nov 17 '17 at 23:58
  • @JohnLou okay so based on what I read in that link it doesn't work because if the group of, in my example, cats is only 2 cats then all you have is 1 cat left so there isn't anything to compare it with? –  Nov 18 '17 at 00:02
  • 2
    The inductive step cleverly hides an assumption that $n > 2$. Try the argument with a set of $2$ cats with two different names! – Theo Bendit Nov 18 '17 at 00:03
  • 1
    My preferred version is “All trains arrive on schedule” (you need to start induction at zero, here), but the problem is always in the step next to the base case. I chose this version one morning when I arrived just in time for the lecture about induction because my train was very late. ;-) – egreg Nov 18 '17 at 00:10
  • @egreg Okay so the flaw here would be that if the group of cats was only 2, meaning n = 1, then you wouldn;t be proving anything because you are just comparing a cat to itself? –  Nov 18 '17 at 00:12
  • Only $n \geq 2$ right? And that'd be correct since P(1) already was proven. @TheoBendit – SuperSjoerdie Nov 18 '17 at 00:13
  • @MirrandaRyan No, in your case the problem is in the case $n=2$, where the two cats might have different names: when you remove cat $A$, the remaining cats all have the same name and the same holds when you remove cat $B$; but there's no cat $C$ to bridge between $A$ and $B$. – egreg Nov 18 '17 at 00:16

1 Answers1

2

For $n> 2$ , it would work. This is because there you would have some cat $C$, so that after removing $B$ and $A$ you would land up at least with the sets $\{A,C,...\}$ and $\{B,C,...\}$ having cats with the same name. Since $C$ is a common element we would have been able to conclude that $A$ and $B$ have the same name.

The problem here is the case $n=2$.

So if $A$ and $B$ are two cats, then attempting the inductive hypothesis, removing $A$ leads to the all cats in the set $\{B\}$ to have the same name, and similarly, removing cat $B$ leads to all cats in the set $\{A\}$ to have the same name.

However, $\{A\}$ and $\{B\}$ are disjoint, so they may very well have different names. This is the problem with the question : if something is wrong at an inductive step, from all steps onwards the deductions are incorrect.

Sarvesh Ravichandran Iyer
  • 76,105