What's wrong in this inductive proof?

Question

Let $a$ be any positive integer. If $x$ and $y$ are positive integers such that $max(x, y) = a$, then we know that $x = y$.

I'm pretty sure this is a false claim, and I need to find what is wrong with the induction proof.

For the base case, we let $a = 1$. Here, if $x$ and $y$ are positive integers such that $max(x, y) = 1$, then $x$ and $y$ must both be $1$.

In the inductive case, we let $k$ be some arbitrary positive integer. The induction hypothesis assumes that if $x$ and $y$ are positive integers such that $max(x, y) = k$, then $x = y$ for some positive integer $k$.

Consider the case where $a = k + 1$ and let $x'$ and $y'$ be two positive integers such that $max(x', y') = k + 1$. Now we have $max(x' - 1, y' - 1) = k$, which, by the induction hypothesis, implies that $x' - 1 = y' - 1$, and therefore that $x' = y'$. Thus, we have proven the claim.

I can identify just one counterexample: if $a = 20, x = 10, y = 20$. Then, $max(10, 20) = 20$, but $20 \neq 10$.

Answer 1

" a=k+1 and let x′ and y′ be two positive integers such that max(x′,y′)=k+1. Now we have max(x′−1,y′−1)=k,"-1$

But $x'-1$ or $y'-1$ need not be a positive integer.

Answer 2

The problem is that $x'-1$ and $y'-1$ might not both be positive integers (since one of $x',y'$ might be 1), so the induction hypothesis doesn't apply.

Answer 3

Sometimes rephrasing things in terms of indicator functions can help.

Let $\mathbb{N}$ be the positive integers

First let's define a function $f$ so that

$$ f(x, y, a) = 1 \;\;\text{if}\;\; \text{max}(x, y) \ne a \;\text{or}\; x = y $$ $$ f(x, y, a) = 0 \;\;\text{otherwise} $$

Your original claim is equivalent to saying $f(x,y,a) = 1$ for all $x$, $y$, $a$.

A simple counterexample like $f(1, 2, 2) = 0$ is enough to refute the claim, but I'll show that the induction step fails for each value of $a$ in $\mathbb{N}$, rather than merely failing for some value of $\mathbb{N}$.

The induction hypothesis is equivalent to:

$$ (\forall x \forall y \mathop. f(x, y, a) = 1) \to (\forall x \forall y \mathop. f(x, y, a+1) = 1) $$

Which is equivalent to the following where $c$ and $d$ are constants. $a$, $x$ and $y$ are variables and implicitly universally quantified.

$$ f(c, d, a) = 0 \;\lor\; f(x, y, a+1) = 1 $$

Let's consider the value of the expression $f(a, a+1, a+1)$ .

$a$ and $a+1$ aren't equal, and $\text{max}(a, a+1)$ is $a+1$, so $f(a, a+1, a+1)$ is zero.

This contradicts our induction hypothesis for every value of $a$, so the induction step never holds.