Solve Proof by Induction: Explain What's Wrong

[cepheid]

Homework Statement

Explain what is wrong with the structure and/or reasoning of the following proof. Remember that saying the claim is false is not a justification.

For all x,y,n in {0,1,2,...}, if max(x,y) = n, then x=y.

Proof (by induction):

Base case: Suppose that n=0. If max(x,y) = 0 and x,y are in {0,1,2,...}, then x = y = 0.

Induction step: Assume that whenever we have max(x,y) = k, then x = y must follow. Next, suppose x,y are such that max(x,y) = k+1. Then it follows that max(x-1,y-1) = k, so by the inductive hypothesis, x-1 = y-1 ==> x = y, completing the induction step.

Homework Equations

N/A

The Attempt at a Solution

The claims is obviously false, but I cannot say for sure exactly where the reasoning fails. I think it has something to do with the statement: "Then it follows that max(x-1,y-1) = k."

Somehow, this must not be valid. I just don't know why. Can anyone shed light on this.

 

[Dick]

If x and y are in N={0,1,2,..} it isn't necessarily true that x-1 and y-1 are in N. If you want to show max(0,1)=1 implies 0=1, you are looking at max(-1,0)=0. That isn't covered in the k=0 case.

 

[cepheid]

I don't know how to mark a thread as solved, but thanks for the help. That makes sense

 

[HallsofIvy]

It is possible that either x or y is equal to 0. If x= 0, then x-1 is not in the set 0, 1, 2, ... Same if y= 0.