real_analysis/src/week3.tex

\documentclass[../main_text.tex]{subfiles}
\begin{document}
\setcounter{exercise}{0}

\part{Assignment 3}

\exercise*
\begin{tcolorbox}
    Suppose $x,y \in \R$ and $x < y$. Prove that there exists $i \in \R\backslash\Q$ such that $x < i < y$.
\end{tcolorbox}

If either $x$ or $y$ (or both) are not rational numbers, we can simply take the average like so: $\frac{x+y}{2}$,
in a similar way we did for the rationals. Since $x$ or $y$ isn't rational, the resulting fraction will also not be
a rational and this proves the statement.

Now if $x,y \in \Q$, we cannot use this average trick, because the resulting fraction will be a rational itself and
so it doesn't satisfy the restriction that it must be in $\R\backslash\Q$. So we have to take a different approach.

Let $x,y \in \Q$ with $x < y$ and $m := \frac{x+y}{2}$, so $x < m < y$. Then, let $X = \{a \in \R : x < a < m\}$ and
let $Y = \{b \in \R : m < b < y\}$. Since $x < m$ and $m < y$, these are nonempty and they are bounded, because
of the restrictions $x < a < m$ and $m < b < y$. So, there exists $k \in X$, that is not rational such that
$x < k < m$ and there exists $h \in Y$ that is not rational such that $m < h < y$. Pick either $k$ or $h$ as $i$,
since $x < k < m < h < y$. \qed

\exercise*
\begin{tcolorbox}
    Let $E \subset (0,1)$ be the set of all real numbers with decimal representation using only the digits 1 and 2:
    \begin{equation*}
        E := \{x \in (0,1) : \forall j \in \N, \exists d_j \in \{1,2\} \text{ such that } x = 0.d_1d_2...\}
    \end{equation*}
    Prove that $|E| = |\mathcal{P}(\N)|$.
\end{tcolorbox}

As a hint to this exercise: \textit{Consider the function $f : E \rightarrow \mathcal{P}(\N)$ such that if $x \in E,
x = 0.d_1d_2...$,
\begin{equation*}
    f(x) = \{j \in \N : d_j = 2\}.
\end{equation*}}

In order to prove that 2 sets are of equal cardinality, we need to prove that there is a bijective function between
the 2 sets. In this case, the aforementioned hint function does the trick. Non-formally speaking, it is exactly what
we are looking for: it is a (weird) representation of the power set of natural numbers, in that for every decimal,
represented by a natural number, it is decided if that decimal is a 2 or a 1. This is similar to the actual power set
of the natural numbers, in which for every natural number it is decided whether the number is in a subset or not.

Now for a formal proof. To show that $f$ is bijective, we need to show that it is surjective and injective.
\begin{description}
    \item[Injectivity of $f$] In order to show that $f$ is injective, we have to show that for every $x \in E$, there
        is a unique $y \in \mathcal{P}(\N)$ for the function, by showing that $f(a) = f(b) \implies a = b$.

        So, let's assume that for some $a,b \in E$, $f(a) = f(b)$. So, there two sets of natural numbers
        $\{a_1,a_2,...,a_n\} = \{b_1,b_2,...,b_m\}$. Equality in sets means that every element that is present in the
        one set, is present in the other, and vice versa. No element that is present in either set, is missing in the
        other. So, in this case, both sets will represent the same sequence of digits that are 2. Because the only
        other option for digits is 1, that means the complete digital representation of $a$ and $b$ are known,
        unique and the same. This concludes the proof for injectivity.
    \item[Surjectivity of $f$] To prove surjectivity, we need to prove that for any arbitrary $y \in \mathcal{P}(\N)$,
        there exists a corresponding $x \in E$ such that $f(x) = y$.

        So, take an arbitrary $y = \{y_1, y_2, ... , y_n\}$, where each $y_i \in \N$ and thus $y \in \mathcal{P}(\N)$.
        Then, corresponding $x \in E$ can be constructed easily as follows. Take a decimal number $0.d_1d_2...$ and 
        turn every decimal $d_i$ for which $i \in y$ into a 2, and every other decimal into a 1. Since every decimal
        can only be a 1 or 2, this handles every decimal correctly. Also, $f(x)$ will be in $\mathcal{P}(\N)$.
\end{description}

Since, $f$ is 1-to-1 and onto, $f$ is bijective. Then, because there exists a bijective function from
$E$ to $\mathcal{P}(\N)$, $|E| = |\mathcal{P}(\N)|$. \qed

\exercise*
\begin{tcolorbox}
    \begin{enumerate}[label=\emph{(\alph*)}]
        \item Let $A$ and $B$ be two disjoint, countably infinite sets. Prove that $A \cup B$ is countably infinite.
        \item Prove that the set of irrational numbers, $\R\backslash\Q$, is uncountable. You may use the facts
            discussed in the lectures that $\R\backslash\Q$ is infinite and $\R$ is uncountable without proof.
    \end{enumerate}
\end{tcolorbox}
\begin{enumerate}[label=\emph{(\alph*)}]
    \item So let $A$ and $B$ be two disjoint, countably infinite sets. Since these sets are countably infinite,
        a bijective function to $\N$ exists for both functions separately. It is then straightforward to map both these
        function together to $\Z$ instead, in the following way. Let $f$ be the bijective function such that
        $f : A \rightarrow \N$ and let $g$ be the bijective function such that $g : B \rightarrow \N$. Then, we can
        define a new function $h : A \cup B \rightarrow \Z$ as
        \begin{align*}
            h(x) &= f(x) \text{ if } x \in A \\
                 &= -g(x) \text{ if } x\in B.
        \end{align*}
        Since $A \cap B = \emptyset$, this function is unambiguously defined. Since $\Z$ is countably infinite,
        $A \cup B$ is countably infinite as well. \qed

    \item Because of part (a), we know that if we have two disjoint, countably infinite sets and join them, the result
        is still countably infinite. The opposite must then also be true: if we have a countably infinite set and
        we divide it into two disjoint subsets, both of which are infinite, then they still must be countable.

        So then, for $\R\backslash\Q$, we know that $\R$ is uncountably infinite. So when we split it into rational
        and irrational subsets, from which we know that $\Q$ is countably infinite, $\R\backslash\Q$ must be at least
        and at most uncountably infinite. \qed
\end{enumerate}

\exercise*
\begin{tcolorbox}
    Let $A$ be a subset of $\R$ which is bounded above, and let $a_0$ be an upper bound for $A$. Prove that $a_0 =
    \sup A$ if and only if for every $\epsilon > 0$, there exists $a \in A$ such that $a_0 - \epsilon < a$.
\end{tcolorbox}

Let $A \subset \R$, with $A$ bounded above by $a_0$.
So, we have to prove the implication both ways. First, let's prove that the implication to the right $(\rightarrow)$.

Assume that $a_0 = \sup A$, so for all $a \in A$, $a \leq a_0$. Also, let $\epsilon > 0$. If $a_0 \in A$,
then we pick $a_0$ as $a$ and get $a_0 - \epsilon < a_0$, which holds $\forall \epsilon > 0$. If $a_0 \notin A$,
then we choose $a$ as the average of $a_0$ and $a_0 - \epsilon$, which is definitely smaller than $a_0$. We are
allowed to pick this as $a$, because we assume without loss of generality that $a \geq \inf A$. Then we get
\begin{align*}
    a_0 - \epsilon &< \frac{a_0 + a_0 - \epsilon}{2} \\
                   &< a_0 - \frac{\epsilon}{2} \implies \\
         -\epsilon &< -\frac{\epsilon}{2}.
\end{align*}
Since $\epsilon > 0$, this always holds.

Now for the implication to the left $(\leftarrow)$.

Assume now that the right side is true, i.e. let's assume that $\forall \epsilon > 0$, there exists $a \in A$ such that
$a_0 - \epsilon < a$. Again, let us first investigate the case where $a_0 \in A$. Well certainly still, if $a_0$ is 
an upper bound for $A$ and it is also part of the set itself, it must be the supremum\footnote{Proven in
earlier exercise.}. 

Then, let's assume that $a_0 \notin A$. Now, for all positive $\epsilon$, we know there exists an $a \in A$ 
such that $a \neq a_0$ and $a_0 - \epsilon < a$. Let us assume then that this implies that $a_0 \neq \sup A$ and
try to come to a contradiction. So, then there must be some $b = \sup A$, which has as consequence that
$a < b < a_0$, since $b$ is still an uppoer bound of $A$ (and $a_0 \notin A$). Then, since $b > a$, we can pick
$a = b - \epsilon < b$. So, from our initial assumption we get $b - \epsilon < a_0 - \epsilon < b - \epsilon \implies
b < a_0 < b$, which is a false statement. So, $a_0 = \sup A$.

Since the implication holds both ways, the equivalence is proven. \qed

\exercise*
\begin{tcolorbox}
    \begin{enumerate}[label=\emph{(\alph*)}]
        \item Let $a,b \in \R$ with $a < b$. Prove that the sets $(-\infty, a), (a,b)$ and $(b, \infty)$ are open.
        \item Let $\Lambda$ be a set (not necessarily a subset of $\R$), and for each $\lambda \in \Lambda$,
            let $U_\lambda \subset \R$. Prove that if $U_\lambda$ is open for all $\lambda \in \Lambda$ then the set
            \begin{equation*}
                \bigcup_{\lambda \in \Lambda} U_\lambda = 
                \{x \in \R : \exists \lambda \in \Lambda \text{ such that } x \in U_\lambda\}
            \end{equation*}
            is open.
        \item Let $n \in \N$, and let $U_1,...,U_n \subset \R$. Prove that if $U_1,...,U_n$ are open then the set
            \begin{equation*}
                \bigcap_{m=1}^n U_m = \{x \in \R : x \in U_m \text{ for all } m = 1,...,n\}
            \end{equation*}
            is open.
        \item Is the set of rationals $\Q \subset \R$ open? Provide a proof to substantiate your claim.
    \end{enumerate}
\end{tcolorbox}

\begin{enumerate}[label=\emph{(\alph*)}]
    \item Since $\R$ is open, it is clear that $(-\infty, a)$ and $(b, \infty)$ are open to the left and right
        respectively as well. Also, their respective right and left side are present in $(a,b)$ as well, so we will
        only prove it for this case. The other cases follow logically.

        Let $a,b \in \R$ such that $a < b$. We want to show that for all $x \in (a,b)$ there exists $\epsilon > 0$
        such that $(x - \epsilon, x + \epsilon) \subset (a,b)$. Since for all $y \in (a,b)$ such that 
        $x - \epsilon < y < x + \epsilon$ this statement will recursively hold, we only need to prove that there 
        exists $\epsilon > 0$ such that $a < x - \epsilon$ and $x + \epsilon < b$. Then we can pick a fitting
        $\epsilon$ in the following way, depending if $x$ is closer to $a$ or to $b$, formalized as follows.

        If $x - a = b - x \implies 2x = b + a \implies x = \frac{b+a}{2}$, then $x$ is precisely between $a$ and $b$
        and we can pick $\epsilon$ to be $\frac{b - a}{4}$. Then $x + \epsilon < b$ and $x - \epsilon > a$.

        When $x - a < b - x$, then $x$ will be closer to $a$ then to be and $\epsilon$ is bounded more by $x$'s
        proximity to $a$ than to $b$, i.e. $\epsilon < x - a$. So we can pick $\epsilon = \frac{x-a}{2} < x - a$.
        Then $x - \epsilon = x - \frac{x - a}{2} = \frac{x + a}{2}$. Since $x > a$, $\frac{x + a}{2} > a$. For the
        other side, $x + \epsilon = x + \frac{x - a}{2} < x + \frac{b - x}{2} = \frac{x + b}{2} < b$ since $x < b$.
        So for both sides, we have shown that there exists an $\epsilon$ such that both
        $x - \epsilon, x + \epsilon \in (a,b)$. All elements inbetween $x - \epsilon$ and $x + \epsilon$ will also
        definitely be in $(a,b)$.
        
        The argument when $b - x < x - a$ is very similar and will be left to the reader. Then, for all $x \in (a,b)$,
        the statement is proven. \qed
    \item Non-formally speaking, in this exercise we want to prove that any union of open sets in $\R$ is open itself.
        In order to make this formal, we will assume that $U_\lambda$ is open for all $\lambda \in \Lambda$ and
        follow the definition as presented.

        So, let us assume that $U_\lambda$ is open for all $\lambda \in \Lambda$. This means that for every $x_\lambda
        \in U_\lambda$, there exists an $\epsilon > 0$ such that $(x_\lambda - \epsilon, x_\lambda + \epsilon) \subset
        U_\lambda$. To prove that $\bigcup_{\lambda \in \Lambda} U_\lambda$ is open, we need to show that the same
        property holds for all $y$ in this set. But since the union between some sets is defined as the set that holds
        all the elements that any of these sets hold, this is trivial: for any $y \in \bigcup_{\lambda \in \Lambda}$
        for which we want to know what $\epsilon$ we need to show that the union is open around that $y$, we just pick
        the corresponding $\epsilon$ for the subset $U_\lambda$ which was open. Since all elements in that $U_\lambda$
        are also in the union, this must certainly be the case. \qed
    \item Similarly to the previous exercise, non-formally speaking we want to prove that any intersection of open sets
        in $\R$ is open itself. This is not as trivial as in the previeous exercise however: since every set that is
        added as an intersection poses another restriction, we don't have the immediate guarantee that every $\epsilon$
        from the subsets will also be a well-defined element for the intersection set.

        Now formally. Let $n \in \N$ and let $U_1,...,U_n \subset \R$. We assume that all $U_1,...,U_n$ are open.
        Then we will prove that $\bigcap_{m = 1}^n U_m$ is open by induction over $n$.

        For the base case, let $n = 1$. Then the intersection set is equivalent to $U_1$. Since $U_1$ is open, then
        so is the intersection set.

        For the inductive step, we assume that the intersection set is open for a certain $n = h$, i.e. there exists
        an $\epsilon > 0$ such that $(x - \epsilon, x + \epsilon)$ is open for every $x \in \bigcap_{m = 1}^h U_m$.
        Now, we will add one additional open set to this intersection, $U_{h+1}$, such that $n$ become $h+1$. Note
        that $h + 1 \in \N$. Let the new intersection set be denoted as $\bigcap'$, and the old one as $\bigcap$.
        Then in order to find an $\epsilon > 0$ for every $x \in \bigcap'$ such that $(x - \epsilon, x + \epsilon)$,
        we take the smallest of $\epsilon$'s for that $x$ compared between $\bigcap$ and $U_{h+1}$. Since
        $x \in \bigcap'$, we know that $x \in \bigcap$ and $x \in U_{h+1}$. Then the smallest accomponying $\epsilon$
        always gives a well-defined open set inside of $\bigcap'$ because $|(x + \epsilon_1) - (x - \epsilon_1)| < 
        |(x + \epsilon_2) - (x - \epsilon_2)|$ if $\epsilon_1 < \epsilon_2$, and thus $\bigcap'$ is open itself. \qed
    \item No, $\Q$ is not open in $\R$. This is because we can't find an $\epsilon > 0$ such that for every $q \in \Q$,
        $(q - \epsilon, q + \epsilon) \subset \Q$. We know that $\Q$ is dense in $\R$, but as we have proven in
        exercise 1, the converse is also true. For every real numbers, we can find a real number inbetween that is not
        a rational number. So, we cannot pick an $\epsilon > 0$ such that there is an interval around $x$ that itself
        is completely contained in $\Q$. For every $\epsilon$ we pick, we can always find a real number $r$ such that
        $x < r < x + \epsilon$ and $x - \epsilon < r < x$. So, $\Q$ is not open. \qed
\end{enumerate}

\exercise*
\begin{tcolorbox}
    Prove that
    \begin{equation*}
        \lim_{n \rightarrow \infty} \frac{1}{20n^2 + 20n + 2020} = 0.
    \end{equation*}
\end{tcolorbox}
In order to prove that this limit holds, we need to show that a function $\{x_n\}$ converges to $x$, 
i.e. if for all $\epsilon > 0$, $\exists M \in \N$ such that $\forall n \geq M$ the following inequality holds:
$|x_n = x| < \epsilon$.

Let $\epsilon > 0$. We choose $M \in \N$ such that $\frac{1}{M} < \epsilon$ (Archimedean Property). Then for all
$n \geq M$, $|\frac{1}{20n^2+20n+2020} - 0| = \frac{1}{20n^2 + 20n + 2020} \leq \frac{1}{n^2 + n} \leq
\frac{1}{n} \leq \frac{1}{M} < \epsilon$. \qed

\end{document}