# Prove that no $m$ exists such that $n < m < n+1$ for positive integers $m$ and $n$.

I am studying basic real analysis using Foundations of Mathematical Analysis by Richard Johnsonbaugh and W. E. Pfaffenberger.

Well-Ordering Theorem:

If $$X$$ is a nonvoid subset of the positive integers, then $$X$$ contains a least element; that is, there exists $$a \in X$$ such that $$a \leq x$$ for all $$x \in X$$.

Question:

Use the Well-Ordering Theorem to prove that no $$m$$ exists such that $$n < m < n+1$$ for positive integers $$m$$ and $$n$$.

Work so far:

I probably want to construct a non-empty set $$X$$, but I don't know what form $$X$$ should have. Any hints would be appreciated.

• You don't have to construct it. Let $A$ be a set. If $A$ is empty, there is nothing to prove(the statement to be proved is trivially true). So let $A$ be a non-empty subset of the positive integers, and go from there. – ReverseFlow Dec 2 '16 at 3:32
• @ReverseFlow So if I have a nonempty set of positive integers $A$, then $A$ has a least element, call it $a$. Can I suppose that $a+1 \in A$? I'm really not sure where to go from here. – EternusVia Dec 2 '16 at 3:48
• Does @yurnero answer help? – ReverseFlow Dec 2 '16 at 3:51

Let $X_n=\{m\in\mathbb{Z},m>0:n<m<n+1\}$ and $Z=\{n\in\mathbb{Z},n>0:X_n\neq\emptyset\}$. You're trying to prove that $Z$ is empty.

Suppose that $Z$ were nonempty. Then, there would be $a\in Z$ such that $a\leq z$ for all $z\in Z$. Consider $X_a$. By definition, $X_a$ would be nonempty so there would exist $z^*$ such that $a<z^*<a+1$. But then $z^*-1<a<z^*$ so that $z^*-1\in Z$ so you would have both $a>z^*-1$ (from $z^*-1<a<z^*$) and $a\leq z^*-1$ (from $z^*-1\in Z$). This is the desired contradiction.

• When you say $\exists$ $z^* \in (a,a+1)$, do you mean either $z^* = a$ or $z^* = a+1$? – EternusVia Dec 2 '16 at 3:58
• Assuming yes to my previous comment, how do we know $z^* -1 \in Z$? If $a = z^*$, then $z^* -1$ can't be in $Z$, right? – EternusVia Dec 2 '16 at 4:02
• @EternusVia I rewrote the notation slightly. $z^*-1\in Z$ because there is a positive integer $a$ that lies between $z^*-1$ and $(z^*-1)+1$. And no $z^*$ is not $a$ because $z^*>a$. – yurnero Dec 2 '16 at 4:06
• I see now. Very nice proof! – EternusVia Dec 2 '16 at 4:24
• The set $Z$ in your proof is not restricted to the positive integers as requested; could you modify your proof to reflect this. – ReverseFlow Dec 3 '16 at 3:42

Let $A=\{a\in \mathbb{Z}\;|\;\; a>0\}$.

Prove: The set $B=\{m \in A\;| \exists\;n\in A, \;\;\; n<m<n+1\ \;\; \}$ is empty.

Proof: Fist, we know that 1 is the minimum element of $A$, by definition of the set of positive integers. In particular, by the Well-Ordering Theorem(using your notation), $r=1$.

Let B be non-empty. That is, suppose there exists an integer $m$ such that $n<m<n+1$ for some $n\in A$. By the Well-Ordering Theorem, there exists an element $r_0 \in B$ such that $\forall m \in B$, $r_0\leq m$.

In particular, $n < r_0 < n+1$ for some $n$. Now, add $-n$ to get

$$n+(-n) < r_0+(-n) < n+1+(-n)$$ $$0 < r_0-n < 1$$

Since $n,r_0 \in \mathbb{Z}_{>0}$, and $0<r_0-n$ means $n\not=r_0$ we know $\exists q=r_0-n$ such that $q \in \mathbb{Z}_{>0}$ and $q<1$. By the Well-ordering Theorem, this is impossible as $r=1\le q<1$.

Therefore, no such $m$ exists and $B=\emptyset$.

• Saying that $1 < r-n+1 < 2$ is false for all values of $n \in A$ seems to be supposing the hypothesis? The number $r-n+1 = k$ is a positive integer, so $1<k<2$ is just a particular instance of what we want to show, no? I would appreciate any clarification. Thank you. – EternusVia Dec 2 '16 at 4:39