Proving by induction that any two natural numbers are equal.

Question

This is something I've been working on for a while now; although it seems trivial, I am confused. I can't seem to find the error.

Originally I thought the problem was with the base case, then I noticed the peculiar structure given to the proof where any two numbers $a, b \leq n$ are equal, then I thought it was something with the general assumption. Unfortunately, I don't get where the problem is.

Can someone HINT me? I don't want the full answer I want to figure it out myself.

Answer 1

You assume that if $a$ is a natural number less than $n+1$ then $a-1$ is a natural number less than $n$. That is:

$$\forall a \Big[\big((a \in \Bbb N^+)\wedge (a\leq n+1)\big) \implies \big((a-1\in \Bbb N^+)\wedge (a-1\leq n)\big)\Big]$$

This is false. There is a smallest natural number, so if you substract one from that, you don't have a natural number. Thus:

$$\forall a \Big[\big(a \in \{1..n+1\}\big) \implies \big( (a-1)\in \{0..n\} \big)\Big]$$

Answer 2

the subtle error is the formulation: Let $$ L(n):=\{(a,b)|a\leq n \text{ and } b \leq n\} $$ No think about a counterexample for $$ (a,b) \in L(n+1) \Rightarrow (a-1,b-1) \in L(n) $$