2
$\begingroup$

enter image description here

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.

$\endgroup$
8
  • 1
    $\begingroup$ Try $a=1$, $b=2$, $n=2$. The issue should become apparent. $\endgroup$ – Slade Jan 16 '15 at 6:01
  • $\begingroup$ Or, more generally, any time $a=1$ or $b=1$. $\endgroup$ – DanielV Jan 16 '15 at 6:03
  • 1
    $\begingroup$ Note that $a-1$ is not necessarily a natural number. $\endgroup$ – copper.hat Jan 16 '15 at 6:15
  • 1
    $\begingroup$ 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. $\endgroup$ – Squirtle Jan 16 '15 at 6:17
  • 1
    $\begingroup$ 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. $\endgroup$ – Squirtle Jan 16 '15 at 6:22
2
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.