What's wrong in this inductive proof? 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$.
 A: " 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.
A: 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.
A: 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.
