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

  • 2
    $\begingroup$ 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. $\endgroup$ – Daniel Fischer Dec 15 '13 at 14:50
  • $\begingroup$ To be precise, what is the definition of $\ge$? $\endgroup$ – Hagen von Eitzen Dec 15 '13 at 14:55
  • $\begingroup$ 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$. $\endgroup$ – Jay Dec 15 '13 at 15:01
  • $\begingroup$ @DanielFischer so if I made the changes you indicate the proof would be a valid one? Thanks! $\endgroup$ – Jay Dec 15 '13 at 17:11
  • $\begingroup$ 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". $\endgroup$ – Daniel Fischer Dec 15 '13 at 17:18

I thought that since the proof only needed a bit of refinement I would restate it here with the corrections mentioned:

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.


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.