Math 311 W08 Day 1

1. Intro / Syllabus

2. Reading. Before Wednesday, be sure to read:
o The part of 1.1 on Mathematical Induction
o The part of 1.1 about proposition 1.2
o Section 1.3

3. The two most important results in Chapter 1 are the Archimedean Property
and the Density of the Rational Numbers . Let’s start by understanding these
statements and trying to figure out why they might be true.

4. The Archimedean Property: (There are two equivalent versions of this
theorem)

Version 1: For any positive number c , there is a natural number n such that n > c.
Version 2: For any positive number ε, there is a natural number n such that 1/n < ε.

o Why are these equivalent?

Proof: Suppose Version 1 is true. Now let ε > 0. Choose the c from Version 1 to be
1/ε. Then there is a natural number n such that n > c. So we have n > 1/ε. This
means that 1/n < ε. Thus Version 2 is true.

Now suppose Version 2 is true. (The same kind of trick works, try to work out the
details.)

o Why is Version 1 true?

If Version 1 is not true, then there is a positive number c such that for every natural
number n, c ≥ n. This means that c is an upper bound of N. But everyone knows
the natural numbers are not bounded above! If Version 1 is not true, we get a
horrible contradiction. So the Archimedean Property must be true!

Now we just need to figure out what it means formally for a set to be bounded, and
then PROVE that the natural numbers are not bounded.

5. What does it mean for a set to be bounded above?

A set is bounded above if there is some real number that is bigger than or equal
to everything in the set.

6. Definition: Let S be a non-empty set of real numbers . S is bounded above if
there exists a real number b such that b ≥ s for every s ∈S.

7. What does it mean for a set to be unbounded above?

It means that there is no upper bound. You can try every single real number and
will never find one that works. In other words, for any real number you choose,
you will be able to find at least one larger element from the set.

8. Definition: Let S be a non-empty set of real numbers. S is unbounded above
if for every real number b, there exists an element s ∈S such that s > b.

Notice that if we take the set S to be the natural numbers, and use n for s and c
for b, we see the statement that N is unbounded above is the same as Version 1
of the Archimedean Property!

9. Claim: The natural numbers are unbounded above.

10. So, how do we KNOW that the natural numbers are unbounded above?

Well, they keep going forever and there is at least 1 unit of space between each
of them, so it seems like it would be hard to find an upper bound.

11. How are we going to PROVE that the natural numbers are unbounded
above?

We could try to do it by contradiction. We could assume they were bounded
above. Then if we found a natural number that was very close to a supposed
upper bound, we could probably add 1 or something to it and jump the upper
bound. This would give us a natural number that is bigger than the supposed
upper bound!

The problem is that many of these supposed upper bounds could be way bigger
than all of the natural numbers (remember we are supposing N is bounded
above). So we need to idea of a least upper bound to make this work.

12. Definition: Let S be a set of real numbers. The real number c is the least
upper bound of S if 1) it is an upper bound and 2) if b is any upper bound of
S then c ≤ b.

The least upper bound of a set S (when it exists) is denoted by l.u.b. S. The least
upper bound is also often called the supremum of S and denoted by sup S.

13. Completeness Axiom. Any nonempty set of real numbers that is bounded
above has a least upper bound.

14. Lemma. The natural numbers, N, are unbounded above:

Proof: Suppose that the natural numbers are bounded above…
Clearly N is non-empty. Then by the completeness axiom it has a least upper
bound. Let m = sup N. Now m-1 is less than m so it cannot be an upper bound
(m is the least upper bound). This means that there must be a natural number
bigger than m – 1. Say n∈N is such that n > m – 1. But n + 1 is also a natural
number and adding 1 to each side of this inequality we have n + 1 > m. And
that is just silly since m is an upper bound of the natural numbers. This gives us
a contradiction. This proves that the natural numbers are unbounded above.

15. What do you think it might mean for a subset of the real numbers to be
dense?

This set:

Looks denser than this set:

But if we zoom far enough in the right place, both of these sets will look like:

(What if the points in the first set are 1 million, 2 million, 3 million, etc…? So
they are only really crammed in close together if you back way off and look at
them from a distance)

A truly dense set would still look like:

…no matter how far you zoomed in. Actually it is impossible to draw a dense
subset and actually show the separate dots (If you could, then you could zoom
in between the dots and show it wasn’t really that dense at all!).

So the idea behind the definition of a dense subset of the reals is that no matter
where you zoom in and no matter how far you zoom in you can still see points
of the set.

16. Definition: A subset, S, of real numbers is said to be dense in R if for any
interval (a, b), there is an element s∈S such that s ∈ (a, b).

Notation. (a, b) is the set of all real numbers between a and b, where a and b are
real numbers and a < b.

17. Theorem (1.9) The set of rational numbers is dense in R.

Why this is true: Well if we consider an interval (a, b) where a and b are both
positive

We know from Version 2 of the Archimedean Property that we can find a 1/n
(where n is a natural number) that is smaller than the interval (a, b).

Unfortunately we can’t just add 1/n to a to get the rational number we want
because we don’t know that a is a rational number

But if we keep adding 1/n to itself, it seems like one of these multiples ought to
land inside of (a, b). These multiples keep going forever and they can’t jump clear
over the interval (a, b) because they are only 1/n apart (and 1/n is less than b – a).
Which multiple will it be? Well, it will be the last one that is less than b.

Let’s work this idea out formally!

Proof (Theorem 1.9): Suppose a and b are real numbers with 0≤ a < b. Clearly b -
a is a positive real number, so by the A.P. choose n s.t. 1/n < b-a. Let S = {m in N
s.t. m/n <b}.

Note that S is nonempty (1 is in S since 1/n < b-a ≤ b-0 = b). Since S is nonempty
and clearly bounded above (by nb), we know that S has a least upper bound (by the
Completeness Axiom).

[It would be really nice if the least upper bound of S was actually an element of S,
because then it would give us a fraction that was less than b and (if we are lucky)
bigger than a.

Well it turns out that if you have a nonempty set of integers that is bounded above,
it actually has a maximum (that is, the least upper bound of the set is actually an
element of the set). Let’s finish off the proof assuming that this is true (then we
will go back and prove it). ]

Let k be the supremum of S. Since S is a set of integers, the supremum is actually
an element of S, (it is the maximum element).

Claim that k/n (which is a rational number) is contained in (a, b).

Since k is in S, we have k/n < b. Recall that 1/n < b – a. This means a < b – 1/n.
Now note that since k the maximum element of S, k + 1 is not in S. This means that
(k+1)/n > b. Subtracting 1/n from each side of this inequality gives us k/n > b –
1/n. But since b – 1/n > a, we have k/n >a. So k/n is in (a, b). √

So, as long as a and b are both non- negative we know that there is a rational
number between them.

If a is negative and b is positive, then 0 is a rational number in (a, b). So the only
case we have to worry about still is: a < b ≤ 0. But in this case, we have 0≤ -b < -
a. So we know there is a rational number q such that q is in (-b, -a). Then –q is a
rational number in (a, b)! √

17. The final detail:

Theorem. Let S be a non-empty sets of integers that is bounded above. Then the
least upper bound of S is an element of S (in other words, the set has a
maximum element).

Proof: Let m = sup S. have a max. Then m – 1 is not an upper bound of S, so
there must be an element k in S that is bigger than m – 1. We will show that k is
the maximum element of S (we just need to show it is the least upper bound).

Thus k + 1 is bigger than m. This means that k + 1 is an upper bound of S (it is
bigger than the least upper bound). This means that S is a subset of (-∞, k + 1).

But no integers exist in (k, k+ 1). (k and k +1 are consecutive integers and (k,
k+1) is just the space between them.)

Since there are no integers in (k, k + 1) and all the elements of S are integers, no
elements of S are in (k, k + 1). So we know that S is a subset of (-∞, k ]. This
means that k is an upper bound of S. Since k is an element of S, there can’t be a
smaller upper bound. Thus k is the least upper bound. So S has a maximum
element (namely k).

18. Final note: Saying that a set of integers has a maximum is equivalent to
saying that the least upper bound of the set is an integer. Why?

Suppose the least upper bound, say k, of a set of integers is an integer. Then it
has to be an element of the set because if it is not, then k -1/2 is bigger than the
next smaller integer (and thus bigger than all of S). This would contradict k
being the least upper bound.

And of course if a set of integers has a maximum, this maximum element must
be the least upper bound. Thus the least upper bound would be an integer.