1
$\begingroup$

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??

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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

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.