Bears and Cats

(David here.) In my analysis set from 2020, I had an overly ambitious section titled "Bears and Cats". Four years later, I've finally decided to compile my solutions somewhere and to record the intention behind this set.

This post will assume some familiarity with closed/open sets and continuous functions.

Completeness of the reals

The starting point is the following fact:

If I have an infinite sequence of nested closed intervals in $\mathbb R$: $$ [a_1,b_1] \supseteq [a_2, b_2] \supseteq \cdots $$ then I can find a single real number contained in all the closed intervals (i.e. their the intersection is nonempty).

In some sense, there is no way to prove this because this is an axiom in the definition for real numbers. (You can check that this is false for rational numbers, for instance.)

The idea that one could define a number via nested intervals is already sufficient to solve some (fairly difficult!) problems. (There is, in fact, an entire MOP problem set about this!) For instance:

(USAMO 1997/6) Suppose the sequence of nonnegative integers $a_1,...,a_N$ satisfies $$ a_i + a_j \leq a_{i+j} \leq a_i + a_j + 1 $$ for all $i,j \geq 1, i+j \le N$. Show that there exists a real number $x$ such that $a_n = \lfloor nx \rfloor$ (the greatest integer $\leq nx$) for $n=1,2,...,N$.

Well, the idea here is to consider the interval of validity of $x$: the fact that $a_n = \lfloor nx \rfloor$ can be rephrase equivalently as $\frac {a_n} n \le x < \frac {a_n+1} n$, so it sufices to show that these intervals overlap.

Another way to write this is that $\frac {a_n + 1} n > \frac {a_m} m$ for any two indices $m,n$. This is somewhat easy to prove by induction: if $n>m$, then we can write $n = qm + r$, and then $$\frac{a_n + 1}n - \frac{a_m}m \ge \frac {qa_m + a_r + 1} n - \frac{a_m}{m} = \frac{r}{n}\left(\frac{a_r+1}{r} - \frac{a_m}{m}\right) \overset ? > 0.$$ If instead $m > n$, then we can write $m = qn + r$ and then $$\frac{a_m}m - \frac{a_n + 1}n \le \frac {q(a_n + 1) + a_r} m - \frac{a_n + 1}n = \frac{r}{m}\left(\frac{a_r}{r} - \frac{a_n+1}{n}\right) \overset ? < 0.$$ In either case, the desired conclusion follows from the assumed truth of smaller cases.

Another interesting application is Mills' theorem, which says that

(Mills) There exists a real number $\alpha$ such that $\lfloor \alpha^{3^n} \rfloor$ is a prime number for all $n$.

Of course, this is less about primes and more about certain intervals nesting/overlapping.

The Bear Cat Theorem

Once we add some complexity, this fact quickly becomes counterintuitive. But first, a strange construction:

(classical) Give an example of a uncountable closed subset of $\mathbb R$ that contains no interval.

The Cantor set suffices. One can think of this set as the set of numbers between 0 and 1 (inclusive) that contain only 0 and 2 in ternary, so it is clearly uncountable and closed.

(Bear Cat Theorem) Suppose the union of closed sets $E_1,E_2,...$ cover an interval. Then some $E_n$ for some $n$ contains an interval.

Of course, "Bear Cat Theorem" is really the Baire Category Theorem. However, I promise not to say "Baire" or "Category" again, so as not to scare my readers away.

Somewhat shockingly, this is actually a straightforward consequence of completeness. Suppose that $[a_0, b_0]$ is our interval. Then $(a_0, b_0)\setminus E_1$ is non-empty (otherwise $E_1$ contains $I_0$ and we are done) and open, so it must contain an interval $(a_1, b_1)$. We can construct $(a_2, b_2), (a_3,b_3),...$ analogously, but note that they must also be nested (and so must their closed analogues be): $$[a_0, b_0] \supseteq [a_1, b_1] \supseteq [a_n, b_n] \supseteq \cdots$$ By completeness, there is a point common to all of them. But this would be a point in $[a_0, b_0]$ and not in any of the closed sets!

---

With these two problems, we are left to mentally reconcile the following:

• It's possible for a closed set to contain no interval.
• Yet, if you chop an interval up into countably many closed sets, one of them must contain an interval.

This is even less believable if your closed sets are nested (i.e. $E_1 \subseteq E_2\subseteq E_3 \subseteq ...$) - while there's nothing preventing each set from having no interval, if every point in an interval eventually lands in the set then one such set will contain an interval! Isn't that kind of crazy?

Shorthand. In such cases where $E_1 \subseteq E_2\subseteq E_3 \subseteq ...$ and $\cup_i E_i = F$, we often write $E_n \uparrow F$ for convenience.

Problems

Cue the brain pain.

Is every function from $[0, 1]$ to $\mathbb R$ the pointwise limit of a sequence of continuous functions?

Turns out that the answer is no. This is because such pointwise limits must be bounded on some interval. If we define $$E_{i,n}= \{x: |f_i(x)| \le n \}$$ then these are closed sets. However, $E_{n,n}\uparrow \mathbb R$, since for each $x$, $f_i(x) \to f(x)$ and so is eventually bounded. Thus, one of them contains an interval. This contradicts the fact that there are functions which are unbounded on any interval.

Remark. Interestingly, this can also be done via a cardinality argument:

• Every continuous function $[0,1]\to\mathbb R$ is a unique extension of a Cauchy function $[0,1]\cap \mathbb Q \to \mathbb R$. (We can recover the original function uniquely at irrational points by taking limits.)
• Every Cauchy function $[0,1]\cap \mathbb Q \to \mathbb R$ can be uniformly approximated by a Cauchy function $[0,1]\cap \mathbb Q\to \mathbb Q$ - simply use a piecewise linear function and uniform convergence.
• The cardinality of Cauchy functions $[0,1]\cap \mathbb Q\to \mathbb Q$ is $|\mathbb Q^\mathbb Q| = |\mathbb R|$, so the cardinality of the limit points is at most $|\mathbb R^\mathbb Q| = |\mathbb R|$. However, the cardinality of functions $[0,1]\to \mathbb R$ has size $|\mathbb R^\mathbb R|$, which is strictly larger than $\mathbb R$ by diagonalization.

Let $f:\mathbb{R}_{\geq 0}\to\mathbb{R}$ be continuous. Suppose for every real number $r>0$, the sequence $f(r),f(2r),f(3r),\ldots$ converges to 0. Must $f(x)\to 0$ as $x\to\infty$?

Fix $\epsilon > 0$, and define $$E_n = \{x: |f(mx)| \le \epsilon \ \forall m\ge n\}.$$ That is, this is the set of $x$ for which all values beyond the $m$-th multiple are actually within the band $[-\epsilon, +\epsilon]$. Clearly, all $x$ eventually qualify, so $E_n \uparrow \R$. This means that one of them contains an interval $I$. However, now we consider the intervals $nI, (n+1)I, (n+2)I, ...$ (where if $I=[a,b]$, $nI = [na,nb]$), and note that eventually the intervals cover the entire real line, which happens if $a\le N(b-a)$. Thus, all sufficiently large $x$ satisfy $|f(x)| \le \epsilon$, so we're done.

(Mathematics Education, Vol 24) Given a sequence $a_1,a_2,...$ and for all $\gamma > 1$, $a_{\lfloor \gamma^n\rfloor} \rightarrow 0$. Must $a_n \rightarrow 0$?

This is essentially the same problem but in log space. Consider $$E_n = \{\gamma>1: |a_{\lfloor \gamma^m \rfloor}| \le \epsilon \ \forall m\ge n\}.$$

So eventually, $E_n \uparrow \R$. This means that one of them contains an interval $I=[a,b]$. This means that $|a_M| \le \epsilon$ for all $\gamma^{ma}

(Bollobás?) Let $f$ be an infinitely-differentiable function from $\mathbb R$ to $\mathbb R$, such that for every $x$ there is an $n$ with all the derivatives $f^{(n)}(x),f^{(n+1)}(x),f^{(n+2)}(x),\cdots$ being zero. Must $f$ be a polynomial?

Recall that the preimage of $f$ of a closed set must be closed. Since each $f^{(n)}$ is differentiable, they are also continuous. Thus $$E_n = \{x: f^{(n)}(x)=f^{(n+1)}(x)=f^{(n+2)}(x)=\cdots = 0 \}$$ are closed sets (since they are the intersection of closed sets).

Since $E_n \uparrow \mathbb R$, one such set $E_n$ must contain an interval. This is unfortunately insufficient to finish the problem - maybe we vaguely know that if all the derivatives vanish then the function is a polynomial, but the issue is that we only have it for this interval.

Let's first formalize our intuition. If we have $f^{(n)} = 0$ on an entire open interval $(a,b)$, then for any point $x\in (a,b)$ we must have $$f^{(n-1)}(x) = \int_{x_0}^x f^{(n)}(x) dx$$ for some fixed $x_0 \in (a,b)$. So inductively, we can get that $f^{(n-1)}$ is a constant, $f^{(n-2)}$ is a linear function and so on to get that $f$ is a polynomial of degree at most $(n-1)$.

How do we get past the problem that we only know some interval is a polynomial? The key lies in the analysis of the set $$X = \{x: \text{$f$ is not a polynomial on any neighborhood of $x$}\}.$$ Let's consider the structure of its' complement $X^c = \mathbb R - X$. Suppose that $f$ was a polynomial on two open intervals $(a,b)$ and $(c,d)$ with $b\le c$. - Clearly $X^c$ is open (since if $x$ is contained in $X^c$, then so must some neighborhood of it). - If these intervals overlap (i.e. $b>c$), then these polynomials match on infinitely many inputs (the entire interval $(c,b)$), so they must be equal. - If these intervals are bordering (i.e. $b=c$), then we argue by continuity: pick $n$ such that $f^{(n)}=0$ on both $(a,b)$ and $(b,d)$, then since $f^{(n)}$ is continuous we have that $f^{(n)} = 0$ on all of $(a,d)$. By our earlier argument, this means that $f$ is a polynomial on $(a,d)$. Thus, we conclude that $X^c$ must be the union of open intervals which are not bordering, and furthermore on each open interval $f$ must be a polynomial. (I'm handwaving slightly here, but see if you can fill in the details.) Now we try running the argument again. If there is indeed an interval $(a,b)$ contained in $X$, then $E_n \cap [a,b] \uparrow [a,b]$, so for some $n$, $E_n\cap [a,b]$ contains an interval $(a',b')$. But by the above logic, because this interval is in $E_n$, $f$ must be a polynomial on $(a',b')$, so $(a',b')\in X^c$, a contradiction. Thus $X$ contains no intervals. Due to the structure of $X^c$, this means that $X = \varnothing$, and $f$ is the same polynomial for all of $\mathbb R$.

Epilogue

Time for some opinions!

There was probably no chance that anyone in the training team could have solved that last problem, or possibly even have a reasonable attempt at it. However, I don't think we should necessarily leave these problems out - these "bonus sections" often cater to not just the most advanced students, but also to the same students in the future. To some extent, when we design problem sets for these special topics, we should also aim to impress and bedazzle.

So, if you're someone who's writing problem sets, write bonus sections, appendices, include fun historical facts or comments that are too deep to be perceived immediately. Don't be afraid to include some problems and immediately spoil them if it helps to provide the right context. Use flavor text to your advantage. Because someday this will make sense to someone who is revisiting it!