2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – ReverseFlow Dec 2 '16 at 3:32
  • $\begingroup$ @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. $\endgroup$ – EternusVia Dec 2 '16 at 3:48
  • 2
    $\begingroup$ Does @yurnero answer help? $\endgroup$ – ReverseFlow Dec 2 '16 at 3:51
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ When you say $\exists$ $ z^* \in (a,a+1)$, do you mean either $z^* = a$ or $z^* = a+1$? $\endgroup$ – EternusVia Dec 2 '16 at 3:58
  • $\begingroup$ 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? $\endgroup$ – EternusVia Dec 2 '16 at 4:02
  • 1
    $\begingroup$ @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$. $\endgroup$ – yurnero Dec 2 '16 at 4:06
  • $\begingroup$ I see now. Very nice proof! $\endgroup$ – EternusVia Dec 2 '16 at 4:24
  • $\begingroup$ The set $Z$ in your proof is not restricted to the positive integers as requested; could you modify your proof to reflect this. $\endgroup$ – ReverseFlow Dec 3 '16 at 3:42
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – EternusVia Dec 2 '16 at 4:39

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.