| Time | Topic | Presenter(s) (alphabetically) |
|---|---|---|
| 14:10 | The Schroeder-Bernstein Theorem | Sanjay Gollapudi |
| 14:35 | The Cantor Set | David Alcalay |
| 15:00 | The Lebesgue Measure | Rodrigo Palmaka, Kristof Pusztai, Rajit Rajpal, Jacob Yeung |
Homework assignments will be available on this webpage throughout the term. All homework assignments should be submitted via Gradescope before midnight on the day it is due.
Suppose that $f : [a, b] \to \R$ is integrable. Prove that $t \mapsto \max(f(t), 0)$ is integrable. Use this to show that the absolute value of an integrable function is integrable.
(This was the one step we were missing in our proof that \[\abs{\int_a^b f(t)\,dt} \leq \int_a^b \abs{f(t)}\,dt.\] Note as well that since $\max(f(t), g(t)) = \max(f(t)-g(t), 0) + g(t)$ this shows that the maximum of two integrable functions is integrable.)
In this problem, we will make the assumption that sequences are indexed beginning at $0$ rather than at $1$.
Suppose $(h_n)_n$ is a sequence of functions from a set $S$ to a metric space $X$. The sequence is said to be uniformly Cauchy if for every $\epsilon \gt 0$ there is some $N$ so that for any $n, m \gt N$ and any $s \in S$, $\abs{f_n(s)-f_m(s)} \lt \epsilon$. Next week we will see that uniformly convergent sequences of functions are uniformly Cauchy, and that if $X$ is complete, all uniformly Cauchy sequences of functions from $S$ to $X$ converge uniformly.
A function of the form above is called a power series. Since a power series is the uniform limit of polynomials—which are continuous—it is continuous.
Let $C : \R \to [-1, 1]$ be a continuous function with the properties that $C(2k) = 1$ and $C(2k+1) = -1$ for every $k \in \Z$, and that $\abs{C(x)-C(y)} \leq 4\abs{x-y}$ for all $x, y \in \R$.
Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment. They are coloured by approximate difficulty: easy/medium/hard.
Suppose that $X$ is a set and $(f_n)_n$ is a sequence of functions $X \to \R$, so that each $f_n$ is bounded. Suppose further that $(f_n)_n$ converges uniformly to some $f : X \to \R$. Show that $(f_n)_n$ is uniformly bounded: that is, there is some $T \in \R$ so that for all $x \in X$ and all $n \in \N$, \[\abs{f_n(x)} \leq T.\]
For each $n \in \N$, let \begin{align*} f_n : \R &\longrightarrow \R \\ x &\longmapsto \frac{x}{1+nx^2}. \end{align*} Show that the sequence $(f_n)_n$ converges uniformly (on $\R$) to some function $f$, and that $(f_n')_n$ converges to $f'$ pointwise on $\R\setminus\set0$, but not at $0$.
Suppose $S$ is a set, and consider the set of functions from $S$ to $\R$, $\R^S = \set{f : S \to \R}$. Let us say that a metric $d$ on $\R^S$ gives rise to the topology of pointwise convergence if whenever $(f_n)_n$ is a sequence of functions in $\R^S$ we have that $(f_n)_n$ converges to a function $f$ with respect to $d$ if and only if $(f_n)_n$ converges pointwise to $f$.
Show that there is a metric on $\R^S$ giving rise to the topology of pointwise convergence if and only if there is a one-to-one function $\varphi : S \to \N$.
Let $R$ be the set of integrable functions on the interval $[a, b]$. Given $f \in R$, define \[\norm{f}_2 = \paren{\int_a^b\abs{f(t)}^2\,dt}^{\frac12}.\]
The function $d_2(f, g) = \norm{f-g}_2$ on $R\times R$ is a pseudo-metric on $R$: it satisfies the triangle inequality, $d_2(f,f) = 0$, and $d_2(f, g) = d_2(g, f)$, but $d_2(f, g)=0$ does not imply $f = g$. If we define $\sim$ by $f\sim g$ whenever $d_2(f, g) = 0$, then $R/\sim$ becomes a metric space; what we have done is show that (equivalence classes of) polynomials are dense in $R/\sim$.
State precisely what is meant by:
Provide examples to show that these three concepts are different.
Recall that for $x \in \R$, $\floor{x}$ (the floor of $x$) is the greatest integer $k \in \Z$ with $k \leq x$. For $n \in \N$, define \begin{align*} \varphi_n: \R &\longmapsto \R\\ t & \longmapsto 2^{-n}\floor{2^nt}. \end{align*} Finally, let $\mathscr{A}$ be the algebra of functions generated by $(\varphi_n)_n$. That is, $\mathscr{A}$ consists of all functions which are finite sums of scalar multiples of finite products of $\varphi_n$'s.
Let $\overline{\mathscr{A}}$ be the uniform closure $\mathscr{A}$. Show that $\overline{\mathscr{A}}$ is not an algebra. (Hint: $x\mapsto x$ is in $\overline{\mathscr{A}}$, but $x \mapsto x^2$ is not.)
Reflect on what this example says about trying to plot quadratic or linear functions on a pixelated display.
Prove that a power series is differntiable, and its derivative is given by differentiating the sum term-by-term. (This is not immediate and does take work, as in general, uniform limits of differentiable functions need not be differentiable, or may have derivatives unrelated to the derivatives of their approximants.) Conclude that a power series is infinitely differentiable.
Let $f : [0, 1] \to \R$ be continuous.
Show by example that there exists a function $f : \R \to \R$ such that $f$ takes on every real value on every non-empty open set. That is, for any $U \subseteq \R$ open and any $y \in \R$, there is some $x \in U$ with $f(x) = y$. (This isn't really related to this week's material in particular, it's just an interesting problem.)
Suppose you're interested in generating integers uniformly at random from $0$ to $N-1$ by flipping coins. If $N = 2$ and you have a fair coin, this is easy: flip it once, and answer $0$ if it's tails and $1$ if it's heads. If $N = 2^k$ you can similarly do this using $k$ flips of a fair coin, writing down a $k$-bit binary number. If you allow yourself to take an arbitrarily large number of flips, you can make this work for any $N$: for example, to generate something from $0$ to $9$, uniformly generate numbers with $N=16$ using four flips each, and take the first that is less than $10$. This can take a rather long time.
What happens if you are making flips with unfair coins? If you have a coin which lands on heads with probability $1/3$ and a fair coin, you can get a uniform random number from $\set{0,1,2}$ as follows: flip the biased coin, and if you see heads, answer $2$; otherwise, flip the fair coin and return $0$ or $1$ based on its result. If you have $N-1$ biased coins with probabilities $\frac1{N}, \frac1{N-1}, \ldots, \frac12$ of landing heads, you can do a similar trick to get a fair number from $0$ to $N-1$: flip the coins starting from the least fair, and answer the first time you see heads.
Unfortunately, biased coins are somewhat difficult and expensive to manufacture, so we would like to use as few as possible. This leads to the following question: given a natural number $N$, what is the minimum number of biased coins required to generate a number in $\set{0,1,\ldots,N-1}$ uniformly at random, using a number of flips you must fix ahead of time? Does the answer change if you are only allowed to use coins with rational bias?
Suppose that $f : (a, b) \to \R$ is differentiable with $f'(x) \gt 0$ for all $x \in (a, b)$.
Let $f : [0,1] \to \R$ be defined as follows: \[ f(x) = \begin{cases} 0 & \text{ if } x \notin \Q \\ 1 & \text{ if } x = 0 \\ \frac1q & \text{ if } x = \frac{p}{q} \text{ with } p \in \Z, q \in \N, \text{ and } p, q \text{ have no common factor}.\end{cases}\] (For example, $f(0) = f(1) = 1$, $f(1/2) = 1/2$, $f(1/4) = f(3/4) = 1/4$.)
Prove that $f$ is integrable, and find its integral.
Next week, we will prove that linear combinations of integrable functions are integrable, and that when $f, g : [a, b] \to \R$ are integrable and $\lambda \in \R$, we have \[\int_a^b f(x) + \lambda g(x) \,dx = \int_a^b f(x)\,dx + \lambda \int_a^b g(x)\,dx.\] We will also prove that continuous functions are integrable. These facts may come in useful in this problem.
Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment.
Suppose that $f : [a, b] \to \R$ is monotonically increasing, i.e., if $a \leq t \lt s \leq b$ then $f(t) \leq f(s)$. Prove that $f$ is integrable.
Suppose that $f : [0, 1] \times [0, 1] \to \R$ is continuous. Notice that for each $y_0 \in [0, 1]$, we have a function \begin{align*} [0, 1] &\longrightarrow \R \\ x &\longmapsto f(x, y_0). \end{align*} Each of these functions is continuous, and so integrable; this can be checked directly from the definition, or by using the sequential characterisation of continuity.
Suppose that $f : \R \to \R$ is differentiable, and $f'(0) \gt 0$.
Let $f : [0, 1]\times[0, 1] \to \R$.
Suppose that $f : \R \to \R$ is differentiable with bounded derivative. Prove that $f$ is uniformly continuous.
Let $a \lt b$ be real numbers, and suppose $f : [a, b] \to \R$ is bounded.
A tagged partition of $[a, b]$ is a pair $(\cP, \cT)$ where $\cP = \set{x_0 \lt x_1 \lt \cdots \lt x_n}$ is a partition of $[a, b]$, and $\cT = \set{t_1, \ldots, t_n}$ is a finite set so that $t_i \in [x_{i-1}, x_i]$. The Riemann sum of $f$ associated to $(\cP, \cT)$ is the number \[R(f, \cP, \cT) = \sum_{i=1}^n f(t_i) (x_i - x_{i-1}).\]
We say that $f$ is Riemann integrable with Riemann integral $I$ if for any $\epsilon \gt 0$ there is a partition $\cP$ of $[a, b]$ so that for any tagged partition $(\cQ, \cT)$ where $\cQ$ is a refinement of $\cT$, we have \[\abs{R(f, \cQ, \cT) - I} \lt \epsilon.\]
Prove that a function is Riemann integrable if and only if it is integrable (in the sense from class, that $L(f) = U(f)$), and in this case its Riemann integral is $\int_a^b f(t)\,dt$.
A partially ordered set $(\Lambda, \leq)$ is called a directed set if every pair of elements has an upper bound; i.e., if for any $\alpha, \beta \in \Lambda$ there is some $\gamma \in \Lambda$ so that $\alpha \leq \gamma$ and $\beta \leq \gamma$. If $X$ is a set, a net along $\Lambda$ in $X$ is a function $\Lambda \to X$; we will sometimes denote it by writing $(x_\alpha)_{\alpha \in \Lambda}$ for the net defined by $\alpha \mapsto x_\alpha$. Nets should be though of as generalizations of sequences; in particular, $\N$ is a directed set and a sequence in $X$ is just a net in $X$ along $\N$.
Suppose now that $X$ is a metric space, $\Lambda$ is a directed set, and $(x_\alpha)_{\alpha \in \Lambda}$ is a net. If $x \in X$, a neighbourhood of $x$ is an open set $U \subseteq X$ with $x \in U$. We say that the net converges to a limit $x \in X$ if for every neighbourhood $U$ of $x$, there is some $\lambda \in \Lambda$ so that whenever $\alpha \in \Lambda$ with $\alpha \geq \lambda$, we have $x_\alpha \in U$. In this case, we write \[\lim_{\alpha\in\Lambda} x_\alpha = x.\] (It turns out that nets are to arbitrary topological spaces what sequences are to metric spaces; sequences are in a certain sense not rich enough to capture the entire structure of a topology which does not come from a metric, but nets can. For example, its possible for a subset of a topological space to contain the limit of every convergent sequence with terms drawn from that set, but not be closed; such a set will contain the terms of some convergent net but not its limit. Likewise it's possible that a function commutes with the limit of every sequence but is not continuous, because it fails to commute with the limit of some net.)
Suppose $f : (a, b) \to \R$ and $x \in (a, b)$. Show that $f$ is differentiable at $x$ if and only if there is a function $h : (a, b) \to \R$ and a constant $C \in \R$ so that \[\lim_{t\to x}\frac{h(t)}{t-x} = 0 = h({\color{red}x})\] and for all $t \in (a, b)$, \[f(t) = f(x) + C(t-x) + h(t).\] Moreover, show that in this case $C = f'(x)$.
(Another equivalent condition is that there is a function $E : (a, b) \to \R$ and a constant $C \in \R$ so that $E(x) = 0$, $E$ is continuous at $x$, and \[f(t) = f(x) + C(t-x) + E(t)(t-x).\] It's probably worth thinking about why this is also equivalent, but you don't need to prove it.)
Suppose $M$ is a metric space. If $x, y \in M$, a path (in $M$) from $x$ to $y$ is a continuous function $\gamma : [0, 1] \to M$ with $\gamma(0) = x$ and $\gamma(1) = y$.
Define a relation $\sim_p$ on $M$ by $x \sim_p y$ if and only if there is a path from $x$ to $y$ in $M$. As before, set \[ [x]_{\sim_p} = \set{y \in M | x \sim_p y}.\]
The equivalence classes $[x]_{\sim_p} \subseteq M$ are called path components of $M$. If $M$ has exactly one path component, it is called path connected. (Note that $\emptyset$ is not path connected: it has zero path components, not one.)
Suppose that $E \subseteq \R^n$ is open. Show that the path components of $E$ are open (in $\R^n$).
(If you find it useful, you may use without proof the fact that functions of the form \begin{align*}f : \R &\longrightarrow \R^n \\ t &\longmapsto \vec{a} + t\vec{b}\end{align*} are continuous, where $\vec{a}, \vec{b} \in \R^n$.)
It is not true that connected sets are path connected in general. For example, the set \[T = \set{(0, y) \mid -1 \leq y \leq 1} \cup \set{\paren{x, \sin\paren{\frac1x}} \mid x \gt 0} \subseteq \R^2\] can be shown to be connected but not path connected; its path components are the two separate pieces in the presentation above.
Give an example of continuous functions $f, g : \R \to \R$ so that:
Let $S, C : \R \to [-1, 1]$ be differentiable functions with the following properties:
Let \begin{align*} f : \R &\longrightarrow \R \\ t &\longmapsto \begin{cases} 0 & \text{ if } t = 0 \\ t^2S\paren{\frac1t} & \text{ if } t \neq 0.\end{cases} \end{align*}
(Although we have not finished the proofs yet, you may assume that the Chain Rule holds, and that $h : t \mapsto \frac1t$ is differentiable on $\R\setminus\set0$ with derivative $h'(t) = \frac{-1}{t^2}$.)
Suppose $(a_n)_n$ is a sequence in $\R_\infty$. We define the limit superior of $(a_n)_n$ to be the quantity \[\limsup_{n\to\infty} a_n = \inf \set{ \sup\set{ a_k \mid k \gt n } \mid n \in \N } \in \R_\infty.\]
(Due to an error in its statement, this problem will not be graded.)
Suppose $t \in \R_\infty$. Show that $t \gt \limsup_{n\to \infty} a_n$ if and only if there are finitely many $n \in \N$ for which $t \lt a_n$.(Due to an error in its statement, this problem will not be graded.)
Suppose $t \in \R_\infty$. Show that $t \lt \limsup_{n\to \infty} a_n$ if and only if there are infinitely many $n \in \N$ for which $t \lt a_n$.
Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment.
Let \begin{align*}f : \R &\longrightarrow \R \\ x &\longmapsto \begin{cases}0 & \text{ if } x \in \Q \\ x^2 & \text{ otherwise}.\end{cases}\end{align*} Show that $f$ is differentiable at $0$, and find its derivative there. (Notice that $f$ is discontinuous everywhere except at $0$! (That is an exclaimation point, not a factorial; $f$ is discontinuous at $1$.))
Suppose that $f, g : \R \to \R$ are such that $f(0) = g(0)$ and $f'(x) \lt g'(x)$ for all $x \in \R$. Prove that $\abs{f(x)} \leq \abs{g(x)}$ for all $x \in \R$, with equality only when $x = 0$.
Suppose $f : \R \to \R$. Define a function \begin{align*} F : \R^2 \setminus \set{(x, x) \mid x \in \R} &\longrightarrow \R \\ (x, y) &\longmapsto \frac{f(x) - f(y)}{x-y}. \end{align*} Under what conditions does $F$ extend continuously to $\R^2$, in the sense of Assignment 9 Question 1?
(While this certainly seems to have something to do with differentiability, it is a little subtle. Notice, for example, that taking a derivative corresponds to holding one variable fixed and letting the other tend to it, or approaching the missing diagonal horizontally or vertically only; meanwhile continuity requires everything in an open ball to be close to the correct value, not just along the two axes. (It just now occurs to me how "axis" and "axe" both have the plural "axes".))
Let us say that a function $f : \R \to \R$ has the "intermediate value property" if and only if for any $a \lt b$ in $\R$, and any $y$ between $f(a)$ and $f(b)$, there is $c \in (a, b)$ so that $f(c) = y$. The Intermediate Value Theorem tells us that continuous functions have the intermediate value property.
Again, suppose that $E \subseteq X$ is dense, and suppose that $f : E \to Y$ is uniformly continuous on $E$. Suppose also that $Y$ is complete.
Let $M$ be a metric space.
Let us define a relation $\sim$ on $M$ as follows: given $x, y \in M$, $x \sim y$ if and only if there is a connected set $A \subseteq M$ with $x, y \in A$. Let us also write \[ [x]_\sim = \set{y \in M \mid x \sim y}.\]
The equivalence classes $[x]_\sim \subseteq M$ are called the connected components of $M$; they are in a loose sense the "largest connected pieces" of $M$. Notice that \[M = \bigcup_{x \in M} [x]_\sim,\] that is, $M$ is the union of its connected components. Also, since $[x]_\sim = [y]_\sim$ whenever $x \sim y$, the connected components of $M$ are disjoint. Since every point of $M$ is in some connected component, it follows that a non-empty space $M$ is connected if and only if it has precisely one connected component.
To give a few examples, the connected components of $\Z$ are the sets $\set{k}$ for each $k \in \Z$, and the connected components of $\Q$ are the sets $\set{q}$ for each $q \in \Q$. The connected components of $[0, 1) \cup \set{4} \cup (6, 9)$ are $[0, 1)$, $\set4$, and $(6,9)$. The circle $\set{(x, y) \in \R^2 \mid x^2 + y^2 = 1}$ has one connected component, itself; the same is true of any connected set. The empty set has no connected components (since in our definition, the empty set is not connected; we defined it this way so that we could unambiguously list the connected components of a set).
Suppose that $(M, d)$ is a metric space.
Suppose that $E \subseteq M$ and $p$ is a limit point of $E$. Suppose further that $f, g, h : E \to \R$ are functions, and that for some $\delta \gt 0$ and all $x \in E$ with $0 \lt d(x, p) \lt \delta$ we have \[f(x) \leq g(x) \leq h(x).\] Finally, suppose that \[\lim_{x\to p} f(x) = L = \lim_{y \to p} h(y).\] Prove that \[\lim_{t\to p} g(t) = L.\]
Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment. They are coloured by approximate difficulty: easy/medium/hard.
Let $M$ be a metric space and $E \subseteq M$. Show that the following are equivalent:
Show that there are two points on opposite sides of the equator with the same temperature as each other.
What assumptions are needed to make this true? Are they physically reasonable?
Suppose that you climb a mountain one day, and descend it the next. Show that there must be some time when your elevation was the same on both days.
Suppose that $p \in \R$, and that $E \subseteq \R$ has the property that $p \in E' \cap (E^c)'$. Suppose further that $f, g : \R \to \R$. Define \begin{align*} \varphi : \R &\longrightarrow \R \\ t &\longmapsto \begin{cases} f(t) &\text{ if } t \in E \\ g(t) &\text{ if } t \in E^c.\end{cases} \end{align*} Prove that $\varphi$ is differentiable at $p$ if and only if $f$ and $g$ both are, $f'(p) = g'(p)$, and $f(p) = g(p)$.
Suppose $(M, d)$ is a metric space, $E \subseteq M$, $f, g : E \to \R$, and $p$ is a cluster limit point of $E$.
Suppose further that for some $r \gt 0$, the set $f(E\cap B_r(p)) = \set{f(x) \mid x \in E\cap B_r(p)} \subseteq \R$ is bounded, and that \[\lim_{x\to p}g(x) = 0.\]
Show that \[\lim_{x\to p} f(x)g(x) = 0.\]
(Note: you should not assume that $f$ has a limit at $p$, unless you prove it from these hypotheses.)
Suppose that $(M, d)$ and $(X, d_X)$ are metric spaces, $E \subseteq M$, $f : E \to X$, and $p$ is a cluster limit point of $E$.
Suppose that $X, Y, Z$ are metric spaces, that $f : X \to Y$ and $g : Y\to Z$, that $x_0 \in X$, and that $f$ is continuous at $x_0$ while $g$ is continuous at $f(x_0)$. Verify that $g\circ f$ is continuous at $x_0$.
(You should not assume that $f$ or $g$ are continuous anywhere else. If you use the open set chracterisation mentioned in extra problems below, you should prove it, although I don't think that is the easiest way forward for this problem.)
Within this question, we will equip $\R^n$ with the Euclidean distance $d_2$ given by \[d_2(\vec x, \vec y) = \sqrt{\sum_{i=1}^n \abs{x_i-y_i}^2}.\]
Let $f : \R \to \R^n$ and for each $i$ define $f_i = \pi_i \circ f : \R \to \R$. Prove that if each $f_i$ is continuous, then so is $f$.
(In fact, $f$ is continuous if and only if each $f_i$ is; the other direction follows immediately from part A and a statement we will prove soon, that the composition of continuous functions is continuous.)
Let $f : [0,1] \to \R$ be defined as follows: \[ f(x) = \begin{cases} 0 & \text{ if } x \notin \Q \\ 1 & \text{ if } x = 0 \\ \frac1q & \text{ if } x = \frac{p}{q} \text{ with } p \in \Z, q \in \N, \text{ and } p, q \text{ have no common factor}.\end{cases}\] (For example, $f(0) = f(1) = 1$, $f(1/2) = 1/2$, $f(1/4) = f(3/4) = 1/4$.)
Prove that $f$ is continuous at every irrational number, but discontinuous at every rational number.
Suppose that $f, g : X \to Y$ are continuous, and $E \subseteq X$ is dense; recall that by definition this means $\overline E = X$.
(This time you may use the additional characterisations of density given below, but if you do you should convince yourself that you can prove them.)
Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment.
Suppose that $(M, d)$ is a metric space and $X \subseteq M$. Prove that the following are equivalent:
I'm not sure if I proved these useful facts in lecture or not. Prove them now, without looking things up in the notes or the text.
Suppose that $(M, d)$ is a metric space.
Suppose that $X, Y$ are metric spaces, $f : X \to Y$, and $x_0 \in X$. Show that $f$ is continuous at $x_0$ if and only if whenever $U \subseteq Y$ is open with $f(x_0) \in Y$, there is an open set $V \subseteq X$ with $x \in V \subseteq f^{-1}(U)$.
This is unfortunately not as nice as the case for functions that are continuous on all of $X$.
Suppose that $K \subseteq M$ is compact and $F \subseteq M$ is closed and bounded. Prove that there are $x \in K, y \in F$ so that \[d(x, y) = \inf\set{d(s, t) \mid s \in J, t \in K},\] or show by example that this may not be the case.
Let $(M, d)$ be a metric space, and $X \subseteq M$. Define $\iota$ to be the inclusion $\iota : X \hookrightarrow M$ defined by $x \mapsto x$. Ponder the relation between Assignment 4, Problem 3 and the continuity of $\iota$.
Recall that a set $S$ is said to be countable if there is an injective function $S \hookrightarrow \N$. A metric space $(M, d)$ is said to be separable if it has a countable dense subset.
Suppose that $(X, d_X)$ and $(Y, d_Y)$ are non-empty metric spaces.
Let $(q_n)_n$ be a sequence in $\Q_{\geq0}$ defined as follows: \[q_n = \begin{cases} \frac{a}{b} & \text{ if } n = 2^a3^b \text{ for some }a, b \in \N \\ 0 & \text{otherwise} \end{cases}.\] Show that for any $x \in \R_{\geq0}$ there is a subsequence of $(q_n)$ converging to $x$. (Hint: first show that every positive rational number occurs infinitely often in $(q_n)_n$, and recall that $\Q$ is dense in $\R$.)
Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment. They are coloured by approximate difficulty: easy/medium/hard.
(The hardest part of this problem is understanding the definitions.)
A pseudometric on a set $M$ is a function $p : M\times M \to \R_{\geq0}$ such that:
An equivalence relation on a set $X$ is a relation which is reflexive, symmetric, and transitive. That is, a relation $\sim$ such that:
As an example, fix $k \in \N$ and define a relation $\sim$ on $\Z$ by $n \sim m$ if and only if $k$ divides $n - m$. Then, for example, $k \sim 15k \sim -2k$, and \[{\Z/\!\sim} = \set{[0]_\sim, [1]_\sim, \ldots, [k-1]_\sim}\] contains precisely $k$ distinct equivalence classes. It is possible to do arithmetic on these classes: we can define $[n]_\sim + [m]_\sim = [n+m]_\sim$ and $[n]_\sim[m]_\sim = [nm]_\sim$, and the definition does not depend on the choice of representatives $n \in [n]_\sim$, $m \in [m]_\sim$. This is the beginning of modular arithmetic.
Recall that in a metric space $(M, d)$, a sequence $(a_n)_n$ converges to a point $a$ if and only if for every open set $U \subseteq M$ with $a \in U$, there is some $N \in \N$ so that for every $n \gt N$, $a_n \in U$.
Suppose that $M$ is a set, and let $\mathscr{F}$ be a set of pseudometrics on $M$. Let us call a subset $G \subseteq M$ open if for every $x \in M$, there are finitely many $p_1, \ldots, p_k \in \mathscr{F}$ and some $r \gt 0$ so that \[\set{y \in M \mid p_i(x, y) \lt r \text{ for each } i = 1, \ldots, k} \subseteq G.\]
We say a sequence $(a_n)_n$ in $M$ converges to $a \in M$ if for every open set $U \subseteq M$ with $a \in U$ there is some $N \in \N$ so that for every $n \gt N$, $a_n \in U$.
Let $(M, d)$ be a compact metric space.
Suppose $(X, d_X)$ and $(Y, d_Y)$ are non-empty metric spaces. Prove directly, without appealing to Problem 1 above, that $(X\times Y, d_\infty)$ is sequentially compact if and only if $X$ and $Y$ both are.
Let $(M, d)$ be a metric space.
Let $a_1 = 1$ and for $n \in \N$, define $a_{n+1} = \sqrt{3+2a_n}$.
Suppose that $(a_n)_n$ is a sequence in a metric space $(M, d)$ which converges to a limit $a$. Prove that $\set{a_n\mid n \in \N} \cup \set a$ is compact.
Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment.
Suppose that $(a_n)_n$, $(b_n)_n$ are sequences in a metric space $(M, d)$ so that \[\limni d(a_n, b_n) = 0.\] Prove that both sequences converge to the same limit, or provide a counterexample.
A topological space is a pair $(X, \mathscr{T})$ where $X$ is a set, and $\mathscr{T}$ is a collection of subsets of $X$ so that $\emptyset, X \in \mathscr{T}$, and $\mathscr{T}$ is closed under finite intersections and arbitrary unions (that is to say, if $G_1, \ldots, G_n \in \mathscr{T}$ then $G_1\cap\cdots\cap G_n \in \mathscr{T}$, and if $(G_\alpha)_\alpha$ is a collection of elements of $\mathscr{T}$ then $\bigcup_\alpha G_\alpha \in \mathscr{T}$). The elements of $\mathscr{T}$ are said to be open, and a set $F \subseteq X$ is said to be closed if $F^c \in \mathscr{T}$. We refer to $\mathscr{T}$ as a topology on $X$.
Notice that if $(M, d)$ is a metric space, then $\mathscr{T}_d = \set{U \subseteq M \mid U \text{ is open with respect to } d}$ is a topology on $M$. We say that the topology $\mathscr{T}_d$ is induced by the metric $d$.
A topological space $(X, \mathscr{T})$ is said to be metrizable if there is a metric on $X$ which induces $\mathscr{T}$. Note that this metric need not be unique!
A sequence $(x_n)_n$ in a topological space $(X, \mathscr{T})$ is said to converge to $x \in X$ if for every open set $G \in \mathscr{T}$ with $x \in G$, there are only finitely many $n \in \N$ for which $x_n \notin G$. (Remember that we proved this was equivalent to our definition of convergence in metric spaces.)
We showed in lecture that if $\set{K_\alpha}$ is a collection of compact subsets of $M$ so that the interesction of every finite subcollection is non-empty, then the intersection of all the $K_\alpha$ is non-empty.
Let $S = \set{q \in \Q \mid q^2 \lt 2}$. Show that $S$ is closed and bounded as a subset of the metric space $\Q$, but is not compact. Also, determine if $S$ is open as a subset of $\Q$.
Recall that if $(S, d_S)$ and $(T, d_T)$ are metric spaces, then the functions \begin{align*} d_1(\mathbf{x}, \mathbf y) &= d_S(x_1, y_1) + d_T(x_2, y_2) \\ d_2(\mathbf{x}, \mathbf{y}) &= \sqrt{d_S(x_1, y_1)^2 + d_T(x_2{\color{red},}y_2)^2}, \text{ and}\\ d_\infty(\mathbf x, \mathbf y) &= \max(d_S(x_1, y_1), d_T(x_2, y_2)) \end{align*} are all metrics on $S\times T$.
Let $r \gt 0$ and $\mathbf x \in \color{red}{S\times T}$.
(Note that there is no reason to find the best $s$ for a given $r$, just any one that works. It may be interesting to think about what the best is, though. Consider also what this says about drawing diamonds inside circles inside squares. Also note that this applies to $\R^2$, and so by induction, to $\R^n$.)
A metric space $(M, d)$ is called totally bounded if for every $\epsilon \gt 0$ there is a finite list of points $x_1, \ldots, x_n \in M$ so that every $y \in M$ is within $\epsilon$ of at least one $x_i$.
Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment.
Find an example that shows the statement in problem 1 may fail if the $K_\alpha$ are closed and bounded, but not necessarily compact. (Hint: for this, you will need to work in a metric space other than $\R^n$.)
(Note that there is no reason to find the best $s \gt 0$ for a given $r$, just any one that works. It may be interesting to think about what the best is, though. Consider what this says about drawing diamonds inside circles inside squares.)
Let $(M, d)$ be a metric space, and suppose that $E \subseteq M$ is not bounded. Prove that $E$ has an infinite subset with no limit points in $M$. Use this to show that compact sets are bounded.
Note that this gives another way to prove that compact sets are bounded.
Suppose that $K$ is a subset of a metric space $(M, d)$ with the property that whenever $\mathscr{U}$ is an open cover of $K$ with the property that every set in $\mathscr{U}$ is a ball, it follows that $\mathscr{U}$ has a finite subcover. Is this enough to guarantee that $K$ is compact?
Recall that a set $S$ is called countable if there is an injective (i.e., one-to-one) function $S \hookrightarrow \N$.
Let $S \subseteq \R$, and consider the collection $\mathscr{S}$ of subsets of $\R$ which can be formed by applying some sequence of complements and closures to $S$. For example, if $S = (0, 1)$, then $\mathscr{S} = \set{(0, 1), [0, 1], \R\setminus(0, 1), \R \setminus[0,1]}$; taking further complements or closures of these sets produces no new sets.
Determine whether or not $\mathscr{S}$ can be infinite. If it must be finite, determine if it can be arbitrarily large.
Provide either a set $S$ so that $\mathscr{S}$ is infinite, a sequence of sets $S_n$ so that the corresponding $\mathscr{S}_n$ has size at least $n$, or a set $S$ so that $\mathscr{S}$ is as large as possible.
Use Zorn's Lemma to show that 4C is true in any metric space, not merely compact ones.
Suppose $(M, d)$ is a metric space so that $\R \subseteq M$ and for any $x, y \in \R$, $d(x, y) = \abs{y-x}$. Prove that $\R$ is closed as a subset of $M$.
Let $(M, d)$ be a metric space, $E \subseteq M$, and $E'$ be the set of limit cluster points of $E$.
Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment.
Determine if each of the following statements is true or false.
Show that if $U \subseteq M$ is an open set, then there is a set of balls whose union is $U$.
Let $(M, d)$ be a metric space, $E \subseteq M$, and $E'$ be the set of cluster points of $E$.
Suppose that $M_1 \subseteq M_2$ and moreover that $d_1(x, y) = d_2(x, y)$ for all $x, y \in M_1$; that is, $M_1$ is a sub-metric space of $M_2$. Show that the inclusion function $\iota : M_1 \to M_2$ given by $\iota(x) = x$ is nepo.
(Note that the metric space in which a set is considered is important here! The goal is to show that open subsets of $M_2$ have preimages in $M_1$ which are open as subsets of $M_1$. You may find it useful to first show that $\iota^{-1}(U) = U \cap M_2$.)
Prove the following useful fact, which you may use later on this assignment. You do not need to submit this problem.
Suppose that $M$ is a set and $f : M \times M \to \R_{\geq0}$ is such that for all $x, y \in M$, $f(x, y) = 0$ if and only if $x = y$, and $f(x, y) = f(y, x)$. Prove that if $x, y \in M$, we have \begin{align*} f(x, x) &\leq f(x, y) + f(y, x) \\ f(x, y) &\leq f(x, y) + f(y, y) \\ f(x, y) &\leq f(x, x) + f(x, y) \\ f(x, x) &\leq f(x, x) + f(x, x). \end{align*} Consequently, to show $f$ is a metric, it suffices to check that the triangle inequality holds for triples of distinct points.
For each of the following, determine (with proof) if the given function is a metric on the given set.
Recall that a function $f : X \to M$ is said to be injective or one-to-one if for every $x, y \in X$, $f(x) = f(y)$ implies $x = y$.
Suppose $(M, d)$ is a metric space, $X$ is a set, and $f : X \to M$. Define \begin{align*} d_f : X\times X &\longrightarrow \R_{\geq0} \\ (x, y) &\longmapsto d(f(x), f(y)). \end{align*} Prove that $d_f$ is a metric on $X$ if and only if $f$ is injective.
Suppose that $S$ and $T$ are metric spaces with metrics $d_S$ and $d_T$ respectively. Recall $S \times T = \set{(s, t) : s \in S, t \in T}$. Prove that \begin{align*} d_2 : (S\times T) \times (S\times T) &\longrightarrow \R_{\geq0} \\ ((x_1, x_2), (y_1, y_2)) &\longmapsto \sqrt{d_S(x_1, y_1)^2 + d_T(x_2, y_2)^2}. \end{align*} is a metric on $S \times T$.
(Note that, as a consequence, the Euclidean metric is a metric on $\R^2$; induction will show that it is also a metric on $\R^n$ for any $n \in \N$.)
Suppose $(M, d)$ is a metric space.
Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment.
Let $M$ be a set. Given a subset $E \subseteq M$, we denote by $E^c$ the complement of $E$ in $M$: $E^c = M \setminus E = \set{x \in M \mid x \notin E}$. Note that this notation only makes sense when $M$ is clear.
Verify the following identities, where $(E_\alpha)$ is a collection of subsets of $M$.
Let $S$ be a set. Call a function $d : S\times S \to \R_{\geq0}$ an anti-metric if for every $x, y, z \in S$:
Show that if $d$ is an anti-metric on $S$, then $S$ contains at most one element.
Suppose $M$ and $X$ are metric spaces. We say $X$ embeds into $M$ (and write $X \hookrightarrow M$) if there is a function $f : X \to M$ which preserves distance: that is, if for all $x, y \in X$ we have $d_X(x, y) = d_M(f(x), f(y))$. Such a function $f$ is said to be an isometry. Notice that the function $f$ in Problem 2 is an isometry from $(X, d_f)$ to $(M, d)$. Also notice that an isometry is necessarily injective.
Let $n \in \N$, and let $p : \R^n \to \R$ be any polynomial function in $n$ variables. Let $T \in \R$. Prove that the set \[\set{ x \in \R^n \mid p(x) \lt T }\] is open (in $\R^n$ with respect to the Euclidean distance $d_2$).
(Later in the course, once we have the right tools, this will be much easier statement to prove. Without any technology, though, it's fairly challenging.)
Using only technology available 2000 years ago, how would you...
Useful fact: a lot of the content of this website is rendered with a Javascript plugin called MathJax. If you right-click on any displayed math, one of the options is "Show Math As > TeX Commands", which will show you what $\LaTeX$ I used to generate it. However, I've defined a few custom commands that are not standard $\LaTeX$, so you can't *quite* copy-paste directly into a document. Nonetheless, if you're wondering how to typeset something, that's a way to find out.
Suppose that $(F, \preceq)$ is an ordered field, that $H \subseteq F$, and that $a \in F$. Suppose further that $\sup H = t \in F$. Finally, let $H+a = \set{x + a \mid x \in H} \subseteq F$. Prove that $H+a$ has a supremum in $F$, and that $\sup(H+a) = \sup(H)+a$.
Prove the following useful facts.
Suppose that $\emptyset \subsetneq E_1 \subseteq E_2 \subseteq \R$. If $E_2$ is bounded above, then $\sup E_1$ exists (in $\R$) and $\sup E_1 \leq \sup E_2$.
(Note: the symbol "$\subsetneq$" means "is a proper subset of", so $A \subsetneq B$ means $A \subseteq B$ and $A \neq B$. Thus $\emptyset \subsetneq E_1$ means "$E_1$ is non-empty". In contrast, the symbol $\nsubseteq$ means "is not a subset of". The symbol "$\subset$" is inconsistently used, usually meaning $\subsetneq$ but sometimes meaning $\subseteq$, depending on the author.)
If $x, y \in \R$ with $0 \leq x \leq y$ then $x^2 \leq y^2$. Moreover, assuming that $x^{1/2}, y^{1/2}$ exist in $\R$ with $0 \leq x^{1/2}, y^{1/2}$, prove that $x^{1/2}\leq y^{1/2}$.
Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment. They are coloured by approximate difficulty: easy/medium/hard.
Suppose that $\F$ is a field. If $p \in \N$ is such that \[0_\F = \sum_{i=1}^p 1_\F = \underbrace{1_\F + 1_\F + \ldots + 1_\F}_{p \text{ times}},\] and $p$ is minimal with this property, then $\F$ is said to be "of characteristic $p$". If $\F$ is not of characteristic $p$ for any $p \in \N$, we say that $\F$ is of characteristic zero.
Now, let us suppose that $(\F, \preceq)$ is an ordered field.
Let $F = \Q[X] / \paren{X^2-2}$; this is the field of polynomials with rational coefficients in a single indeterminate $X$, modulo the ideal generated by $X^2-2$. Every element of $F$ is of the form $s + tX$, with addition defined component-wise and multiplication defined by \[(s_1+t_1X)\cdot_F(s_2+t_2X) = (s_1s_2+2t_1t_2) + (s_1t_2+t_1s_2)X.\]
With this, and all future assignments, you should expect to have all necessary material to complete the assignment by the end of the week when it is posted.
Suppose that $(S, \preceq)$ is a partially ordered set; recall that for $a, b \in S$ we write $a \prec b$ if $a\preceq b$ and $a\neq b$. Let $\not\prec$ be the relation on $S$ defined by setting $a \not\prec b$ if and only if $a \prec b$ is false.
Suppose $(S, \preceq)$ is an ordered set.
Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment. They are coloured by approximate difficulty: easy/medium/hard.
Suppose that $\mathcal{N}$ is a set with the following properties:
The set $\mathcal{N}$ is a model of the natural numbers proposed by von Neumann (cf. Wikipedia). That is to say, $\mathcal{N}$ satisfies the Peano axioms for arithmetic, but can be defined directly from the axioms of set theory without needing to introduce any new objects.
Let $\mathcal{P}$ be the set of polynomial functions from $\Q \to \Q$. Define a relation on $\mathcal{P}$ by $p \sqsubseteq q$ if and only if $p(10) \leq q(10)$. Is $\sqsubseteq$ a partial order? Is it a total order?
A (total) order $\preceq$ on a set $S$ is said to be a well-order if every $T \subseteq S$ contains a minimum element.
Recall that for $a, b \in \N$ we write $a \mid b$ if $a$ divides $b$, i.e., if there is some $k \in \N$ so that $b = ak$.
Prove that any partial order may be extended to a total order, regardless of whether or not the underlying set is finite. To prove this, you may assume the following:
Zorn's Lemma. Suppose that $Z$ is a set and $\preceq$ is a partial order on $Z$ with the property that every totally-ordered subset of $Z$ is bounded above in $Z$. Then $Z$ contains a maximal element. (A subset $W \subseteq Z$ is totally ordered if $\preceq$ restricted to $W$ is an order, i.e., if whenever $x, y \in W$ we have either $x \preceq y$ or $y \preceq x$. An element $x \in Z$ is maximal if whenever $y \in Z$ with $x \preceq y$, we have $y = x$.)
You may wish to type your homework; for example, this makes it much easier for others to read, and makes it easier to edit and produce a coherent final argument. Most modern mathematics papers are typeset using a system called \(\mathrm{\LaTeX}\) (pronounced "lah-tech" or "lay-tech"; see the Wikipedia entry on Pronouncing and writing "LaTeX"). Although it has a steep learning curve, it is extremely useful for typesetting complicated mathematical expressions. There are many resources available online, such as this reference by Oetiker, Partl, Hyna, and Schlegl. I have also made available an assignment template here, which produces this output when compiled correctly.