# Prove by induction that if $a,b \in \Bbb{N}$, then $a>b \implies a \ge b+1$

I have to prove using only induction that if $a,b \in \Bbb{N}$, then $a>b \implies a \ge b+1$.

These are the definitions I'm working with:

Inductive set:

A subset $K \subset \Bbb{R}$ is inductive if the following properties hold:

• $1 \in K$
• $r \in K \implies r+1 \in K$

Natural numbers:

The set of natural numbers is the subset $\Bbb{N} \subset \Bbb{R}$ with the following properties:

• $\Bbb{N}$ is inductive
• If $H \subset \Bbb{R}$ is an inductive set, then $\Bbb{N} \subset H$

Induction principle:

Let H be an inductive subset of $\Bbb{N}$, then $H = \Bbb{N}$

Corollary of the induction principle:

Let P(n) be a proposition about a natural number n.

If P(1) is true and $P(n) \implies P(n+1)$, then $P(n)$ is true for any natural number.

The book where I found this exercise already gives a proof in the following way:

First it proves that $a,b \in \Bbb{N} \text{ and } a>b \implies a-b \in \Bbb{N}$ (1)

Then it proves that $n \in \Bbb{N} \implies n \ge 1$ (2)

So the implication follows from these 2 lemmas.

How can I prove by induction that if $a,b \in \Bbb{N}$, then $a>b \implies a \ge b+1$ without using (1) and (2)??

I thought about proving that if $n \in \Bbb{N}$, then:

$\{x \in \Bbb{N} | n<x<n+1 \} = \varnothing$

But I was able to prove this by contradiction, not by induction.

Can anyone please help me??

## 2 Answers

We can prove that $A=\{m \in \mathbb{N}|n>m \Rightarrow n \geq m+1\}$ is an inductive subset of $\mathbb{N}$

$1 \in A$ because if $n \in \mathbb{N}$ and $n>1$ and $n<2$ then $n \notin \mathbb{N}$ which is a contradiction.

Thus $n \geq 2$

Now let $m \in A$ and $m>1$ such that $n>m \Rightarrow n \geq m+1$

We want to prove that $m+1 \in A$

Let $n>m+1$ then $n-1>m$.

But $m \in A$ thus $n-1 \geq m+1 \Rightarrow n \geq m+2=(m+1)+1$

Therefore $m+1 \in A$ so $A$ is an inductive subset of $\mathbb{N}$

Heh, heh... It's a matter of choosing which term you are doing the induction on. No-one said the induction had to be done on $b$. Do it on $a$.

Let $P(n)$ be the property than if $n > b$ then $n \ge b+1$.

If $k = 1$ (assume $\mathbb N$ does not include $0$; Or let $k =0$ if it does). If $1 >b$ than $b \in \mathbb N$ is impossible so: If $1>b$ then $1 \ge b+ 1$ is true as a false hypothesis implies anything. So $P(1)$.

If $k = 2$ then if $2 > b$ and $b\in \mathbb N$ then $b = 1$ and $2 \ge b+1 = 1 + 1 = 2$. So $P(2)$.

Assume $P(k)$. Then if $k + 1 > b$ then $k > b-1$. So $k \ge b-1 + 1 = b$. And $k+1 \ge b+1$. So $P(k+1)$.

• That feels like it is cheating... but it's not. – fleablood Sep 5 '17 at 21:22