# Proof by contradiction that if a set $A$ contains $n_0$ and contains $k+1$ whenever it contains $k$, then it contains all numbers $\ge n_0$

Prove that if a set $A$ of natural numbers contains $n_0$ and contains $k+1$ whenever it contains $k$, then $A$ contains all natural numbers $\geq n_0$.

I have attempted a proof by contradiction as follows:

Let $N_0=\{i:i \in \mathbb{N},i\geq n_0 \}$ and let $B=N_0\setminus A$ therefore by the well-ordering principle $B$ must have a least element. So let $m_0 \in B$ such that $m_0$ is the least element of B.

$m_0-1\not\in B \implies m_0-1\in A$ (this implication I'm not sure on) but if $m_0-1\in A \implies m_0\in A \therefore m_0\not\in B$ a contradiction. Therefore $B$ has no least element and therefore A contains all natural numbers $\geq n_0$.

The step I'm not sure on is $m_0-1\not\in B \implies m_0-1\in A$ but my reasoning is that since $m_0 \not=n_0$ then $m_0\gt n_0 \implies m_0\geq n_0+1$ therefore $m_0-1\geq n_0 \implies m_0-1\in N_0$ therefore $m_0-1\in A$ since it's not in $B$.

I'm not even sure it's a correct proof even if I was certain the above implication was true; it's from Spivak's Calculus and the answer in the back is much more concise but I wanted to have a go at trying to prove it a different way to practise writing and constructing proofs (I'm still quite new to it).

• You should just explicitly say that $m_0 = n_0$ cannot be, hence $m_0 > n_0$, before that step. Then $m_0-1 \in A$ is unproblematic. – Daniel Fischer Dec 15 '13 at 14:50
• To be precise, what is the definition of $\ge$? – Hagen von Eitzen Dec 15 '13 at 14:55
• from the book the question was from: $a>b$ if $a-b$ is in P where P is "the collection of positive numbers" and therefore $a\geq b$ if $a>b$ or $a=b$. – Jay Dec 15 '13 at 15:01
• @DanielFischer so if I made the changes you indicate the proof would be a valid one? Thanks! – Jay Dec 15 '13 at 17:11
• Yes. Well, you should also explicitly state that you assume $B \neq \varnothing$ at the beginning of the proof. Otherwise, you can't invoke the well-ordering principle to deduce the existence os a least element. You know $m_0 \geqslant n_0$ since $m_0 \in B\subset N_0$, so you have $m_0-1 \notin B$. But you need something that guarantees that $m_0-1 \in N_0$ to deduce $m_0-1 \in A$, the observation $m_0 > n_0$ gives you that. And I would rephrase the last sentence, "Therefore $B$ must be empty". – Daniel Fischer Dec 15 '13 at 17:18

Let $N_0=\{i:i\in \mathbb{N}, i\geq n_0\}$ and let $B=N_0 \setminus A$ and given $B\neq \emptyset$ we can invoke the well ordering principle. Let the least element of B be defined such that: $m_0\in B$ and $m_0$ is the least element of $B$.
Since $m_0 \neq n_0$ this implies that $m_0 \gt n_0$ we can then deduce that $m_0-1 \not\in B \implies m_0-1\in A$ but by the given condition that $k+1\in A$ if $k\in A$ then $m_0\in A \therefore m_0\not\in B$ which is a contradiction. Therefore $B$ must be empty.