# Proving by induction that any two natural numbers are equal.

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.

• Try $a=1$, $b=2$, $n=2$. The issue should become apparent. – Slade Jan 16 '15 at 6:01
• Or, more generally, any time $a=1$ or $b=1$. – DanielV Jan 16 '15 at 6:03
• Note that $a-1$ is not necessarily a natural number. – copper.hat Jan 16 '15 at 6:15
• That's a good point, but why stop there. Suppose the OP then thinks, "Well the proof doesn't work for $\mathbb{N}$ but it should work for $\mathbb{Z}$." There's another subtle error in the proof which would still exist. – Squirtle Jan 16 '15 at 6:17
• I'm not claiming induction works for $\mathbb{Z}$; just making the point that I thought this question might appear. You can definitely do induction on $\{0,1,2,...\}$ or $\{-3,-2,-1,....\}$ for that matter. – Squirtle Jan 16 '15 at 6:22

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)$$

• He specifically asked for a hint, not an answer! – DanielV Jan 16 '15 at 6:52
• Sorry, haven't read this...made an edit. – Blah Jan 16 '15 at 7:02
• I believe he is also implicitly assuming $0 \not \in \mathbb N$ – DanielV Jan 16 '15 at 7:04
• Doesn't change anything, what is important is that $\mathbb N$ has a minimal element. – Blah Jan 16 '15 at 7:08

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]$$