Chapter 1 - The Reals

1.1: The Irrationality of $\sqrt{2}$

We start with a familiar theorem:

\sqrt{2}

is irrational

There is no rational number whose square is 2.

\begin{proof}
Assume via contradiction that ${(\frac{p}{q})}^{2} = 2$ . Then $p^{2} = 2 q^{2}$ . Clearly then $p^{2}$ is an even number so then $p$ must be even since an even times an even is even. Then set $p = 2 r$ where $r \in Z$ . Then:

p^{2} = (2 r)^{2} = 4 r^{2} = 2 q^{2} \to 2 r^{2} = q^{2}

so then $q^{2}$ is even and thus $q$ is even. But look! $p, q$ must not share any factors with each other as $p / q$ should already be reduced to simplest form. Hence, then we have a contradiction, so the $p / q$ in question cannot exist.
\end{proof}
Recall that the natural numbers $N$ are:

N = {1, 2, . . .}

then the integers $Z$ :

Z = {. . ., - 3, - 2, - 1, 0, 1, 2, 3, . . .}

then the rationals $Q$ :

Q = {p / q : p, q \in Z, q \neq 0}

We note that $Q$ is a field, where:

Commutative
Associative
Left distributive $a (b + c) = a b + a c$
Additive identity
Additive inverse
Multiplicative Identity
Multiplicative Inverse
are the properties that must hold. Note that $N, Z$ are not fields but ${0, 1, 2, 3, 4}$ is a field considering the addition and multiplication operators are done $mod 5$ .

$Q$ also has:

Natural order, only one is true: $r < s, r = s, r > s$
Is transitive: $r < s \land s < t \to r < t$ .
There's always some rational number $(r + s) / 2$ between two rationals $r, s \in Q$

as such we can do addition, subtraction, multiplication, and division on $Q$ , but again $\sqrt{2} \notin Q$ so then we are missing at least some numbers! Hence, the real numbers $R$ try to solve this incompleteness issue.

1.2: Some Preliminaries

Review of Set Theory

This chapter mainly review set and proof theory:

Sets are a collection of elements
We write $x \in A$ if $x$ is an element of $A$
Union: $A \cup B = {x : x \in A \lor x \in B}$
Intersection: $A \cap B = {x : x \in A \land x \in B}$
Empty Set: $\emptyset$ is the set with no elements: $\emptyset = {}$
Two sets are distoint if $A \cap B = \emptyset$
Subset: $A \subseteq B$ if $x \in A$ implies $x \in B$
Set equivalence: both $A \subseteq B$ and $A \supseteq B$ is the same as $A = B$
$⋃_{i = 1}^{n} A_{i} = A_{1} \cup \dots \cup A_{n}$ and similar for intersection. If $n \to \infty$ then it equals $A_{1} \cup A_{2} \cup \dots$
- $x \in ⋃_{i = 1}^{\infty} A_{i}$ implies that there is some $A_{i}$ where $x \in A_{i}$
- $x \in ⋂_{i = 1}^{\infty} A_{i}$ implies that there for all $A_{i}$ then $x \in A_{i}$
Complement: $A^{c} = {x \in U : x \notin A}$ where $U$ is the universe of discourse. For our sakes usually $U = R$
De Morgan's Laws:
- $(A \cap B)^{c} = A^{c} \cup B^{c}$
- $(A \cup B)^{c} = A^{c} \cap B^{c}$

Functions Review

For functions:

Denote a function $f : A \to B$ as a function that maps elements from $A$ to elements in $B$ .
If $x \in A$ then $f (x) \in B$ is some element associated with $x$
$range (f) = {y \in B : \exists x \in A, y = f (x)}$ . This is also known as the image.
$domain (f) = A$

Okay, some new theorems:

Triangle Inequality

We denote the absolute value function as $| x |$ where:

| x | = {\begin{cases} x & x \geq 0 \\ - x & x < 0 \end{cases}

This satisfies:

$| a b | = | a | | b |$
$| a + b | \leq | a | + | b |$

for all $a, b \in R$ . You can prove these just considering the cases when $a, b$ are non-negative or not. Note that $| a - b | = | b - a |$ and we denote this value as the distance between $a, b$ . So the triangle inequality says that the distance from any two points is less than the sum of the distances to their origins respectively, or the distance to some intermediary point $c$ where $d (a, b) + d (b, c) \leq d (a, c)$ .

Logic and Proofs

Proof strategies we know are:

proof by contradiction
direct proof
contrapositive proof (same as proof by contradiction, except the negated conclusion is now in the hypothesis of the theorem)

Example

Two real numbers $a, b$ are equal iff for all $ε > 0$ it follows that $| a - b | < ε$ .

\begin{proof}
We prove the forward direction $\to$ first. Suppose $a = b$ . Then clearly $| a - b | = | a - a | = | 0 | = 0$ so then if we let $ε > 0$ be arbitrary then clearly $ε > 0 = | a - b |$ as required.

Now for the reverse direction $\leftarrow$ . Notice that we get a $\forall$ as a given, which isn't great, so we should try proof by contradiction. Thus, suppose for all $ε > 0$ that $| a - b | < ε$ . Assume for contradiction that $a \neq b$ . Then choose $ε_{o} = | a - b | > 0$ . Then:

| a - b | < ε_{o} \Rightarrow | a - b | < | a - b | \Rightarrow 0 < 0 \Rightarrow\Leftarrow

hence our assumption was incorrect, so then $a = b$ instead.
\end{proof}

Induction

The idea behind induction is to do the following:

Show the base case that $P (0)$ is true
Have an inductive hypothesis that $P (0), . . . ., P (k)$ is true
Prove that, using these hypotheses, that $P (k + 1)$ is true.

Example

Let $x_{1} = 1$ and for all $n \in N$ that $x_{n + 1} = (1 / 2) x_{n} + 1$ . Then $x_{n}$ is non-decreasing, or $x_{n} \leq x_{n + 1}$

\begin{proof}
Let's use induction:

We know $x_{1} = 1$ and calculating the next term $x_{2} = (1 / 2) 1 + 1 = 3 / 2$ so clearly $x_{1} \leq x_{2}$ .
Suppose for our inductive hypothesis that for some $k \in N$ that all $x_{1} \leq \dots \leq x_{k}$ .
Consider if $x_{k} \leq x_{k + 1}$ . We know that $x_{k - 1} \leq x_{k}$ from our inductive hypothesis. Notice that if we start from there:

\begin{aligned} x_{k - 1} & \leq x_{k} \\ \frac{1}{2} x_{k - 1} + 1 & \leq \frac{1}{2} x_{k} + 1 \\ x_{k} & \leq x_{k + 1} \end{aligned}

Hence, via the principle of mathematical induction, $x_{n}$ is a non-decreasing sequence.
\end{proof}

1.3: The Axiom of Completeness

We note that $R$ really is just an extension of $Q$ , filling in the irrational holes like $\sqrt{2}, \sqrt{3}, . . .$ This definition of $R$ really was chosen for this property of completeness, so even though the justification as to why this property is important will have to wait, you'll see why as we use this axiom a ton. Just know that by the 1870s, we had a pretty rigorous way to construct $R$ from $Q$ , which we'll get to see in 8.6.

An Initial Definition of $R$

First $R$ contains $Q$ with the same operations of addition, multiplication:

All elements $x \in R$ has their additive inverse and if $x \neq 0$ then the multiplicative inverse $x^{- 1}$ exists too.
$R$ is a field, giving the properties of:
- Commutativity
- Associativity
- Distributive Property
$R$ also gets the ordering from $Q$ to all of $R$ . So thing like "If $a < b$ and $c > 0$ implies $a c < b c$ " are silently derived from this ordering.
Thus, $R$ is an ordered field, containing $Q$ as a subfield

This brings us to the idea of completeness. We need to say that $R$ doesn't have "any gaps" where the irrationals should go:

The Axiom of Completeness

Every nonempty set of real numbers that is bounded above has a least upper bound

Let's explore what this means...

Least Upper Bounds and Greatest Lower Bounds

Bounds

A set $A \subseteq R$ is bounded above if there exists a number $b \in R$ such that $a \leq b$ for all $a \in A$ . The number $b$ is called an upper bound for $A$ .
Likewise, the set $A$ is bounded below if there exists a lower bound $l \in R$ where $l \leq a$ for every $a \in A$ .

Least Upper Bound

Some $s \in R$ is the least upper bound for a set $A \subseteq R$ if it meets:

$s$ is an upper bound for $A$
if $b$ is any upper bound for $A$ then $s \leq b$

We denote the least upper bound as the supremum, or $sup (A)$ . Sometimes you'll set $s = lub (A)$ but we stick with the former.

The greatest lower bound, called the infimum for $A$ , is defined similarly and is denoted by $inf (A)$ .

Note that $A$ can have many upper bounds, but the supremum, the least upper bound, is unique. This is because using property (2) in the definition, for two suprema $s_{1}, s_{2}$ then individually $s_{1} \leq s_{2}$ and likewise $s_{2} \leq s_{1}$ , so then $s_{1} = s_{2}$ showing uniqueness.

Example

Let:

A = {\frac{1}{n} : n \in N} = {1, \frac{1}{2}, \frac{1}{3}, \dots}

$A$ is bounded above and below. An upper bound could be $3, 2, 3 / 2, . . .$ . Clearly though here $sup (A) = 1$ . We can show this using the definition.

\begin{proof}
Let's prove (i), showing that $1$ is an upper bound on $A$ . Notice that:

1 \geq \frac{1}{n} \to n \geq 1

is true since $n \in N$ , hence showing that it's a valid upper bound.

For (ii), let $b$ be another upper bound for $A$ . Since $1 \in A$ and $b$ is an upper bound for $A$ then we must have it that $1 \leq b$ , showing property (ii) exactly!
\end{proof}
Note that here $sup (A) \in A$ but this isn't always the case:

Maxima and Minima

A real number $a_{0}$ is a maximum of the set $A$ if $a_{0}$ is an element of $A$ and $a_{0} \geq a$ for all $a \in A$ . Similarly, a number $a_{1}$ is a minimum of $A$ if $a_{1} \in A$ and $a_{1} \leq a$ for every $a \in A$ .

Example

Consider the intervals $(0, 2)$ and $[0, 2]$ . Both sets are bounded above and below and have the same least upper bound, namely 2. But for $2$ to be a maximum of the set, we require it being in the set, so then the former set doesn't have it's maximum, while the latter does.

This goes to show that the supremum need not be a maximum, but if a maximum exists, then it is the supremum.

Thus, the axiom of completeness doesn't get a proof, as it's the foundation of how $R$ exists. But let's look at why $Q$ is itself incomplete:

Example

Consider $S = {r \in Q : r^{2} < 2}$ . Clearly $S$ is bounded above, such as by $2$ , or $3 / 2$ or similar. But looking for the least upper bound, we can find rational approximations (ex: $b = 142 / 100$ ) but then we can always find a smaller upper bound (ex: $b = 1415 / 1000$ ). In $Q$ , we lack the axiom of completeness to get this least upper bound into the set.

But in $R$ there is the axiom! The axiom of completeness asy that $α = sup (S)$ which is a real number. We will prove that $α^{2} = 2$ and thus $α = \sqrt{2}$ but we know that $α$ isn't rational from the irrationality of $\sqrt{2}$ , so then for the rationals we can't use this search to find it.

We'll need some properties of $Q, N$ to be able to determine this suprema. So let's get to those:

Example

Let $A \subseteq R$ be nonempty and bounded above, and let $c \in R$ . Define the set $c + A$ by:

c + A = {c + a : a \in A}

Then $sup (c + A) = c + sup (A)$ .

\begin{proof}
For (i), set $s = sup (A)$ . We see that $a \leq s$ for all $a \in A$ consequently, but then $a + c \leq c + s = c + sup (A)$ as required.

For (ii), let $b$ be an arbitrary upper bound for $c + A$ , so then $c + a \leq b$ for all $a \in A$ . Then $a \leq b - c$ for all $a \in A$ . So then $b - c$ is an upper bound for $A$ . Since $s$ is the least upper bound for $A$ , then we have it that $b - c \leq s$ , thus $b \leq c + s = c + sup (A)$ , completing (ii).

Therefore, $sup (c + A) = c + sup (A)$ .
\end{proof}
Note that (i) states that the suprema is an upper bound, and then (ii) further states it's the lowest one. Thus, we can use it as a lemma:

Lemma

Suppose $s \in R$ is an upper bound for a set $A \subseteq R$ . Then $s = sup (A)$ iff, for all $ε > 0$ there is an element $a \in A$ satisfying $s - ε < a$ .

\begin{proof}
This lemma essentially says that given $s$ is an upper bound, then $s$ is the least upper bound iff any number smaller than $s$ is not an upper bound.

( $\Rightarrow$ ). Suppose $s = sup (A)$ . Let $ε > 0$ . Consider $s - ε$ . Since $s - ε < s$ and $s$ is the least upper bound, then $s - ε$ is not an upper bound for $A$ . Hence, there's some other bound $a \in A$ where $s - ε < a$ as otherwise then $s - ε$ is an upper bound for $A$ which is a contradiction.

( $\Leftarrow$ ). Suppose for all $ε > 0$ there is some $a \in A$ where $s - ε < a$ . We are already given that $s$ is an upper bound (you can also consider if $ε = s - b$ to show that $b < a$ which contradicts $b$ being an upper bound), so consider (ii). Let $b$ be some other upper bound for $A$ , so then for all $a \in A$ then $a \leq b$ . Choose $ε = s - b$ . Then from our given then $b < a$ , but $a \leq b$ ! Hence, if $b$ were to be an upper bound then we must have it that $s - b < 0$ so then $s < b$ then $s \leq b$ as required.
\end{proof}

1.1: The Irrationality of 2

1.2: Some Preliminaries

Review of Set Theory

Functions Review

Logic and Proofs

Induction

1.3: The Axiom of Completeness

An Initial Definition of R

Least Upper Bounds and Greatest Lower Bounds

1.1: The Irrationality of $\sqrt{2}$

An Initial Definition of $R$