$$ \newcommand{\RR}{\mathbb{R}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\CC}{\mathbb{C}} \newcommand{\NN}{\mathbb{N}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\EE}{\mathbb{E}} \newcommand{\HH}{\mathbb{H}} \newcommand{\FF}{\mathbb{F}} \newcommand{\SO}{\operatorname{SO}} \newcommand{\dist}{\operatorname{dist}} \newcommand{\length}{\operatorname{length}} \newcommand{\uppersum}[1]{{\textstyle\sum^+_{#1}}} \newcommand{\lowersum}[1]{{\textstyle\sum^-_{#1}}} \newcommand{\upperint}[1]{{\textstyle\smallint^+_{#1}}} \newcommand{\lowerint}[1]{{\textstyle\smallint^-_{#1}}} \newcommand{\rsum}[1]{{\textstyle\sum_{#1}}} \newcommand{\partitions}[1]{\mathcal{P}_{#1}} \newcommand{\erf}{\operatorname{erf}} \newcommand{\ihat}{\hat{\imath}} \newcommand{\jhat}{\hat{\jmath}} \newcommand{\khat}{\hat{k}} \newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}} \newcommand{\smat}[1]{\left(\begin{smallmatrix}#1\end{smallmatrix}\right)} $$

Assignment 3

Exercise 1 In class we proved that for a complete ordered field the intersection of nonempty nested intervals is nonempty. Here we prove a the stronger statement that we use to justify ancient mathematicians’ techniques of calculating numbers using nested intervals.

Let $I_n=[a_n,b_n]$ be a sequence of nested intervals, and let $A=\{a_1,a_2,\ldots\}$ be the set of lower bounds, $B=\{b_1,b_2,\ldots\}$ be the set of upper bounds. We proved in class that $A$ has a supremum; an analogous proof shows $B$ has an infimum $\beta$.

Prove that if $\alpha = \beta$, then the intersection $\bigcap_n I_n$ contains a single point.

Solution. For $I_n=[a_n,b_n]$ any sequence of nested intervals, let $\alpha = \sup\{a_n\}$ and $\beta = \inf\{b_n\}$. Then for any $x$ in the intersection of all $I$’s, note $x\in I_n$ means $x\geq a_n$ for all $n\in\NN$ so $x$ is an upper bound for the set of all $\{a_n\}$. And, since $\alpha$ is the least upper bound of the $a_n$, it follows that $x\geq \alpha$. Similarly, $x\in[a_n,b_n]$ implies $x\leq b_n$ for all $n$, so $x$ is a lower bound for the $b_n$ and thus $x\leq \beta$, the greatest of all lower bounds.

This tells us that any point $x$ in the intersection satisfies $\alpha\leq x\leq \beta$. So, when $\alpha = \beta$ there is only one point that satisfies this inequality (namely $\alpha=\beta$ itself).

Exercise 2 The proof of the nested interval theorem used the endpoints of the intervals crucially in the proof. One might wonder if the same theorem holds for open intervals (even though the proof would have to change).

Show the analogous theorem for open intervals is false by finding a counter example: can you find a collection of nested open intervals of real numbers whose intersection is empty?

Solution. One such example is to take the intervals $I_n=\left(0,\frac{1}{n}\right)$: these are open for every $n$, and nested as $\frac{1}{n+1}<\frac{1}{n}$ so $I_{n+1}\subset I_n$. However their intersection is empty.

To prove this, assume for the sake of contradiction that there is a real number $x\in \bigcap_{n\geq 1}I_n$. This means that $x\in I_n$ for all $n$, and thus $0<x$ (so $x$ is positive) but $x<\frac{1}{n}$ for all $n$. This implies $x$ is an infinitesimal, but this is a contradiction as $\RR$ does not contain any infinitesimals. Thus no such $x$ can exist, and \[\bigcap_{n\geq 0}I_n=\varnothing\]

Exercise 3 Let $A,B$ be subsets of a complete ordered field with $\sup A<\sup B$.

Prove that there is an element $b\in B$ which is an upper bound for $A$.
Give an example to show this is not necessarily true if we only assume $\sup A\leq \sup B$.

:::{.solution} ## Part 1 Since $\sup A$ is strictly less than $\sup B$ we know the difference $\alpha = \sup B-\sup A$ is positive. According to the epsilon definition of supremum, we know that for every positive $\epsilon$, there exists some element of $B$ greater than $\sup B$ - $\epsilon$. Thus, there is some element of $B$ greater than sup$B$ - $\alpha$ (just substituting this particular $\alpha$ for $\epsilon$): call this element $b$. Since $b > \sup B - \alpha$, we also have that $b > \sup B - (\sup B-\sup A) = \sup A$. So $b > \sup A$, which means that $b$ is an upper bound of $A$. ::: :::{.solution} ## Part 2 Let $A = [0, 2]$ and $B = [0,2)$ be subsets of $\RR$. Notice that both $A$ and $B$ have 2 as their supremum, so $\sup A\leq \sup B$. But no element of $B$ is an upper bound for $A$, as every element of $B$ is strictly less than $2$, wheras $A$ contains $2$. :::

Exercise 4 Let $c>0$ and $A$ be a bounded set with supremum $\sup A$. Define the set $S = \{ca\mid a\in A\}$. Prove that $\sup S$ exists and \[\sup S = c\sup A\]

:::{.solution} Given set $S=\{ca|a\in A\}$, and set $A$ with $\sup A$. We want to first show that $c\sup{A}$ is an upper bound for set $S$, and then that it is the least upper bound. To show it is an upper bound, we can see that because $A$ has a supremum that $a\leq \sup A$ for all $a\in A$. Because $c>0$ we can multiply both sides by $c$ to get \[ ca \leq c\sup A \;\;\; \forall a\in A \] This implies that it is an upper bound.

Then, we will let $u$ be any upper bound for $S$. This means that $u\geq ca$ for all $a\in A$, and then because $c>0$ we can divide both sides by $c$ and get \[ \frac{u}{c} \geq a \;\;\; \forall a \in A \] This means that $\frac{u}{c}$ is an upper bound for $A$. Because we know $\sup A$ is the upper bound, this means that $\sup A\leq \frac{u}{c}$ Then multiplying each side by $c$ we get, \[ c\sup A \leq u \] This means that given any upper bound $u$ of $S$, $c\sup A$ is a smaller upper bound, therefore \[ \sup S = c\sup A. \] :::

Exercise 5 Prove that the supremum of the set $S=\{\frac{n}{n+1}\mid n\in\NN\}$ is $1$.

:::{.solution} Since $n<n+1$, we know that $\frac{n}{n+1}<1$, so $1$ is certainly an upper bound. We need only show that its the least upper bound.

By our $\epsilon$-characterization of the supremum, this is equivalent to the statement that for every positive $\epsilon$, there is some element of our set greater than $1-\epsilon$.

Fix an arbitrary $\epsilon>0$. Since $\epsilon$ is not infinitesimal, there is some $n$ with $\frac{1}{n}<\epsilon$. Thus $1-\frac{1}{n}>1-\epsilon$, but doing some algebra \[1-\frac{1}{n}=\frac{n-1}{n}\] we see this is an element of our set! (Its a fraction, where the numerator is one less than the denominator, and that’s the definition of the set $S$). Thus, for arbitrary $\epsilon$ we found an element of $S$ greater than $1-\epsilon$, so $1$ is indeed the supremum. :::

Exercise 6 (Density of the Irrationals) Use the theorem we proved that the rationals are dense in $\RR$ to prove that the irrationals are also dense in the reals.

Solution. Let $a,b$ be any two real numbers with $a<b$: we seek an irrational number between $a$ and $b$. First, add $\sqrt{2}$ to each of these, to get two new real numbers: by the density of rationals, we can find some $r\in\QQ$ between them \[a+\sqrt{2}<r<b+\sqrt{2}\]

Now, just subtract $\sqrt{2}$ from all terms in the inequality to get \[a<r-\sqrt{2}<b\]

It remains only to show that $r-\sqrt{2}$ is irrational. Assume for the sake of contradiction it is not, and equals some rational number $s$. Then $r-s=\sqrt{2}$, but since $r,s\in \QQ$ we know $r-s$ is rational, which is a contradiction as we’ve proven $\sqrt{2}$ is irrational.

Exercise 7 The dyadic rationals are the subset of $\QQ$ which have denominators that are a power of 2 when written in lowest terms. Prove the dyadic rationals are dense in $\RR$.

Solution. We wish to modify the usual proof of the density of the rationals slightly, just enough to force the denominator to be a power of 2. Let $a,b$ be any two distinct real numbers and without loss of generality assume $a<b$. Then, $b-a>0$, and since infinitesimals do not exist we know there’s some $1/n<b-a$. But $n<2^n$ for all $n$, so $1/2^n<b-a$ as well. Clearing denominators gives

\[1<2^na -2^nb\]

Since the numbers $2^na$ and $2^nb$ are separated by greater than $1$, there must be an integer $m$ between them

\[2^na <m<2^nb\]

Dividing back through by $2^n$ yields exactly what we want: a dyadic rational $m/2^n$ between $a$ and $b$ \[a<\frac{m}{2^n}<b\]

Exercise 8 The sum of two irrational numbers need not be irrational, as the example $\sqrt{2}+(-\sqrt{2})=0$ shows. Prove or disprove: the sum of two positive irrational numbers is irrational.

Solution. This is also false, as we can see by example: the numbers $a=\sqrt{2}$ and $b=2-\sqrt{2}$ are both positive and irrational: we already know the case of $a$, for $b$ we prove it is irrational by contradiction: assuming its rational then so is $b^2= 2^2-4\sqrt{2}+2=6-4\sqrt{2}$, but this implies $\sqrt{2}$ is rational. And, we see that $b$ is positive since $2<4$ implies $\sqrt{2}<\sqrt{4}=2$, and so $2-\sqrt{2}>0$.

But their sum is irrational. \[a+b=\sqrt{2}+(2-\sqrt{2})=2\]