# Proof with Supremum, Infimum, and Well ordering principle

• Nov 23rd 2010, 09:17 PM
magic88
Proof with Supremum, Infimum, and Well ordering principle
1. The problem statement, all variables and given/known data

We just started learning about supremums and infimums in my math proofs class. I am having trouble with the following question:

Let x, y be real numbers with y - x > 1. Prove that there exists an integer n such that x < n < y. Hint--use the well ordering principle.

2. Relevant equations

Well-ordering principle: a nonempty set S of real numbers is said to be well-ordered if every nonempty subset of S has a least element. This is proved using induction.

Upper bound: a real number m is called an upper bound of S if for every s in S, s <= m.
Lower bound: a real number m is called an lower bound of S if for every s in S, m <= s.
Maximum: If m is an upper bound of S and m is in S, then we call m the maximum of S.
Minimum: If m is a lower bound of S and m is in S, then we call m the minimum of S.

Supremum: least upper bound
Infimum: greatest lower bound

3. The attempt at a solution

I am unsure of how to incorporate the well ordering principle into my proof. I was thinking of writing something like, "y - x > 1 <==> y > x + 1 <==> x < x + 1 < y. So there is an integer z such that x <= z < x + 1 or x < z <= x + 1." And then show the rest with ceiling and floor... but I'm sure this is incorrect, as we are supposed to use the well ordering principle.

Please let me know if extra clarification is needed.

Any help would be GREATLY appreciated!

Kendra
• Nov 24th 2010, 12:52 AM
emakarov
Thank you for providing all relevant information.

Consider $\displaystyle \{n\in\mathbb{Z}\mid y\le n\}$ (where $\displaystyle \mathbb{Z}$ is the set of integers). If you know that this set is nonempty, then you can apply the well-ordering principle to it. To show that it is nonempty, assume the contrary and consider the supremum of all integers.
• Nov 24th 2010, 06:04 AM
Plato
If you have proved that the floor function exists, then this proof is easy.
Notice that $\displaystyle \left\lfloor x \right\rfloor \leqslant x < \left\lfloor x \right\rfloor + 1 \leqslant x + 1 < y$.

The integer $\displaystyle \left\lfloor x \right\rfloor + 1$ is between $\displaystyle x~\&~y$.
• Nov 24th 2010, 05:20 PM
magic88
Thanks so much for your quick replies!

Plato--Thank you very much. I really wish I could use the floor function in my proof! It's good to know that I was on to something when I thought of using it :)

emakarov--

I don't think I fully understand why to use the set {z $\displaystyle \epsilon$ Z | y <= z}. I did the proof, though:
We will prove that set A = {z $\displaystyle \epsilon$ Z | y <= z} (where y is a real number) is nonempty. Assume to the contrary that A is empty. Then for every z $\displaystyle \epsilon$ Z, z > y. Then y is the supremum of Z. This is a contradiction because Z has no largest element, and thus does not have any upper bounds (or least upper bounds), and so the supremum of Z does not exist. Thus A cannot be empty, so A is nonempty.
• Nov 25th 2010, 01:25 AM
emakarov
Quote:

Then for every z $\displaystyle \epsilon$ Z, z > y.
You mean, z < y.

Quote:

Then y is the supremum of Z.
Strictly speaking, it only follows that y is some upper bound of Z, not necessarily the least upper bound. However, it follows from the axioms of reals that a nonempty set with an upper bound has the least upper bound. (I am not sure whether reals were introduced axiomatically in your course and, if yes, what axioms were used. For example, the fact above is one of the axioms in Wikipedia.)

Quote:

This is a contradiction because Z has no largest element, and thus does not have any upper bounds (or least upper bounds),
If a set does not have the largest element, it does not follow in general that it does not have an upper bound or supremum. For example, $\displaystyle \{1-1/n\mid n\in\mathbb{Z},n>0\}$ does not have a maximum, but its supremum is 1.

You probably could say that the existence of an upper bound of $\displaystyle \mathbb{Z}$ leads to a contradiction without an explanation, but here it is if you need it. Let $\displaystyle y_0$ be the supremum of $\displaystyle \mathbb{Z}$. By the definition of supremum, $\displaystyle y_0-1$ is not an upper bound, so there exists a $\displaystyle z\in\mathbb{Z}$ such that $\displaystyle z>y_0-1$. Integers are closed under addition, so $\displaystyle z+1$ is still an integer. However, $\displaystyle z+1>y_0$, a contradiction.

Quote:

I don't think I fully understand why to use the set {z $\displaystyle \epsilon$ Z | y <= z}.
Let $\displaystyle A=\{z\in\mathbb{Z}\mid y\le z\}$. You must have been shown in class that a nonempty subset of integers bounded from below is well-ordered. Once you prove that A is nonempty, you know it has the least element, say $\displaystyle z_0$. In particular, $\displaystyle z_0 - 1\notin A$, i.e., $\displaystyle z_0 - 1 < y$ and so $\displaystyle z_0 < y + 1$. Thus, $\displaystyle x + 1 < y\le z_0 < y + 1$, so $\displaystyle x < z_0 - 1 < y$.
• Nov 25th 2010, 11:11 AM
magic88
Quote:

Originally Posted by emakarov
You mean, z < y.

Oops, yes. Sorry, I suppose that was a typo.

We will prove that set A = {z $\displaystyle \epsilon$ Z | y <= z} (where y is a real number) is nonempty. Assume to the contrary that A is empty. Then for every z $\displaystyle \epsilon$ Z, z < y. Then y is some upper bound of Z. By Completeness, since Z has an upper bound, Z has a supremum, a contradiction. [Thanks so much for your proof to show Z has no supremum!] Thus, A is nonempty.

Since A is a nonempty subset of integers bounded below by y, we know it has a least element, say $\displaystyle a$. Since $\displaystyle a$ is a least element, $\displaystyle a-1$ is not an element of A, i.e. $\displaystyle a-1<y$ and so $\displaystyle a<y+1$. Thus $\displaystyle x+1<a \le y+1,$ so $\displaystyle x<a-1<y$. Since $\displaystyle a-1$ is an integer, there exists an integer such that $\displaystyle x < n < y$.

Thank you so much for your help. This make so much more sense now!