September | 2020 | Tao Analysis Solutions

Exercise statement

Propose a definition for limit superior $\limsup_{x\to x_0; x\in E} f(x)$ and limit inferior $\liminf_{x\to x_0; x\in E} f(x)$ , and then propose an analogue of Proposition 9.3.9 for your definition. (For an additional challenge: prove that analogue.)

Hints

None.

How to think about the exercise

Let’s recall how the limit superior was defined for sequences of real numbers. Given a sequence $(a_n)_{n=0}^\infty$ , we first defined the auxiliary sequence $(a^+_N)_{N=0}^\infty$ by $a^+_N := \sup(a_n)_{n=N}^\infty$ , then we took the infimum of the sequence (which is equivalent to taking the limit, since the sequence is monotonic so always converges): $\limsup_{n\to\infty} a_n := \inf(a^+_N)_{N=0}^\infty = \lim_{N \to \infty} a^+_N$ .

So to define a limit superior, we need to take the supremum over something (and this something must be indexed somehow), then take the limit using the index. To help us see the similarities more with the real-valued functions case, let’s rewrite the limit superior for sequences as $\limsup_{n\to\infty} a_n = \lim_{N \to \infty} \sup \{a_n : n \geq N\}$ .

So our goal now is to figure out the set we are taking the supremum over. Which set? This set must get smaller over time, so that the limit is defined (otherwise we wouldn’t have a guarantee that the sequence is monotonic). In other words, we want to “go further” in some relevant sense. In the case of sequences, we “go further” in the limit by taking larger values of $n$ , but in the case of functions we “go further” by taking $x$ values closer to $x_0$ . So the trick is to take a set that shrinks around the point $x_0$ . In particular, we can take $\{f(x) : x \in E \text{ and } |x - x_0| < \delta\}$ . The smaller the value of $\delta$ , the smaller the set. So we can define $\limsup_{x\to x_0; x\in E} f(x) := \lim_{\delta \to 0} \sup\{f(x) : x \in E \text{ and } |x - x_0| < \delta\}$ . Here it is understood that when we take the limit as $\delta \to 0$ only positive values of $\delta$ are considered (we could be clearer about this by writing something like $\lim_{\delta \to 0; \delta > 0}$ ). (TODO: Tao’s book doesn’t actually define divergent limits, so this part does fail in some edge cases, and so we either need to define such limits or use inf/sup. Thanks to crabman for the catch.)

(THIS IS WRONG. I WILL FIX LATER. Thanks to Karim Taha for the catch.) Now how do we state the analogue of Proposition 9.3.9? For part (a), instead of $\lim_{x \to x_0; x\in E} f(x) = L$ we want to say $\limsup_{x\to x_0; x\in E} f(x)$ . For part (b), we can take a sequence $(a_n)_{n=0}^\infty$ converging to $x_0$ , but instead of saying $\lim_{n\to \infty} f(a_n) = L$ , we can use the limit superior for sequences to say $\limsup_{n\to \infty} f(a_n) = L$ .

If you want to think about this topic more, see the first edition of Pugh’s Real Mathematical Analysis, Chapter 3 Exercise 26, which makes the “go further” idea above more rigorous.

Model solution

We define the limit superior $\limsup_{x\to x_0; x\in E} f(x)$ as $\lim_{\delta \to 0; \delta > 0} \sup\{f(x) : x \in E \text{ and } |x - x_0| < \delta\}$ . Alternatively, using infimum instead of a limit we could define it as $\inf\{\sup\{f(x) : x \in E \text{ and } |x - x_0| < \delta\} : \delta > 0\}$ .

(THIS IS WRONG. I WILL FIX LATER.) The analogue of Proposition 9.3.9 is as follows: Let $X$ be a subset of $\mathbf R$ , let $f : X \to \mathbf R$ be a function, let $E$ be a subset of $X$ , let $x_0$ be an adherent point of $E$ , and let $L$ be a real number. Then the following two statements are logically equivalent:

(a) $\limsup_{x\to x_0; x\in E} f(x)=L$
(b) For every sequence $(a_n)_{n=0}^\infty$ which consists entirely of elements of $E$ , which converges to $x_0$ , we have $\limsup_{n\to\infty} f(a_n)=L$ .

The case for limit inferior is very similar: just interchange “superior” and “inferior” everywhere.

Exercise statement

Let $A,B,C$ be sets such that $A \subseteq B \subseteq C$ , and suppose that there is an injection $f : C \to A$ . Define the sets $D_0, D_1, D_2, \ldots$ recursively by setting $D_0 := B\setminus A$ , and then $D_{n+1} := f(D_n)$ for all natural numbers $n$ . Prove that the sets $D_0, D_1, \ldots$ are all disjoint from each other (i.e., $D_n \cap D_m = \emptyset$ whenever $n \ne m$ ). Also show that if $g : A \to B$ is the function defined by setting $g(x) := f^{-1}(x)$ when $x \in \bigcup_{n=1}^\infty D_n$ , and $g(x) := x$ when $x \notin \bigcup_{n=1}^\infty D_n$ , then $g$ does indeed map $A$ to $B$ and is a bijection between the two. In particular, $A$ and $B$ have the same cardinality.

Hints

Draw a picture.
You don’t lose much by taking $C=B$ , and this simplifies the picture.
Beware that Tao’s notation is non-standard here: typically in setting up the Schröder–Bernstein theorem we are given injections $f : A \to B$ and $g : B \to A$ (with no subset relation assumed between $A$ and $B$ ) and are asked to define a bijection $h : A \to B$ . In Tao’s book, the usual $f$ is just the inclusion map $\iota_{A\to B} : A\to B$ (see Exercise 3.3.8 for a definition), the usual $g : B\to A$ is instead called $f: C \to A$ , and the usual bijection $h : A \to B$ is instead called $g : A \to B$ . If you are referring to other expositions as you work on this exercise, you may want to temporarily convert Tao’s notation to match the notation in these other expositions.

How to think about the exercise

This is a pretty tough exercise, if you really want to understand what is going on instead of just bashing out a proof.

To simplify the exposition, let us assume that $C = B$ . At the end of this section we will show how to adjust in the case where we only assume $B \subseteq C$ , and in the model solution below we will revert to only assuming $B \subseteq C$ .

To set the stage, let’s draw a picture of two sets $A, B$ with $A \subseteq B$ :

(Throughout this post, I will be copying from Richard Hammack’s exposition the idea of using suggestive shapes for the two sets as well as the idea generally of visually representing the sets by embedding them within each other.)

We define $D_0 := B \setminus A$ :

We have an injection $f : C \to A$ , i.e. $f : B \to A$ since we assumed $C=B$ . This means that we can put a copy $f(B) \subseteq A$ of the set $B$ inside $A$ :

Notice two things: first the shape of $f(B)$ is the same as the shape of $B$ . This is because we assumed that $f$ is injective, hence it doesn’t “deform” the shape by mapping multiple starting points onto the same point. Second, $f(B)$ does not take up all of $A$ , since we didn’t assume that $f$ is a bijection.

Now we define $D_1 := f(D_0)$ . Since $D_0 \subseteq B$ , we have $f(D_0) \subseteq f(B)$ . Thus we should see a copy of the green stuff within the copy of $B$ that we produced:

We can keep going further with this same process. Our copy of $B$ (namely $f(B)$ ) has a copy of $A$ within it (namely $f(A)$ ) so using $f$ we can place a copy of our copy of $B$ (namely $f(f(B))$ ) inside our copy of $A$ (namely $f(A)$ ):

By the injectivity of $f$ , this “copy of a copy” of $B$ again has a shape similar to that of the original $B$ . The green stuff that is $D_1$ is embedded within $f(B)$ , so it also gets copied inside of $f(f(B))$ . We can define $D_2 := f(D_1)$ and see this as the third layer of green stuff in the picture:

Hopefully by this point you get the idea. As we make more and more copies of $B$ within copies of $A$ within copies of $B$ , we accumulate more and more green stuff. The union of all of the green stuff is $\bigcup_{n=0}^\infty D_n$ , and the white stuff we are left with is the complement, $B \setminus \bigcup_{n=0}^\infty D_n$ .

Having all of these copies within copies is all nice and trippy, but how does this help us define a bijection $g : A \to B$ ? What do we even want, in terms of the picture we have drawn? We want to take each point in $A$ and map it to some point in $B$ in such a way that each point in $B$ corresponds to exactly one point in $A$ . The trick to doing this is the following: each point colored in white can stay put, and each point colored in green can “climb up” one level to hit a green point in an outer level:

In other words, the points in $D_1$ map to $D_0$ via $f^{-1}$ , the points in $D_2$ map to $D_1$ via $f^{-1}$ , and so on (that’s all the green stuff “climbing up”), while the points in the rest of $A$ just stay where they are (that’s all the white stuff). If you look at the picture, I hope you can see that no matter which point in $B$ you pick, there will be exactly one point in $A$ that maps to it.

Now that we have the idea, how do we write down the formal definition of this bijection $g : A \to B$ ? The green stuff is $\bigcup_{n=0}^\infty D_n$ , so you might be tempted to write the following:

$\displaystyle g(x) := \begin{cases}f^{-1}(x) & \text{if } x \in \bigcup_{n=0}^\infty D_n \\ x & \text{otherwise}\end{cases}$

But actually, what is $D_0$ ? We defined $D_0 := B\setminus A$ , so the points in $D_0$ aren’t even in the domain of $g$ ! This means we don’t need to include $D_0$ in the union, so we can instead define:

$\displaystyle g(x) := \begin{cases}f^{-1}(x) & \text{if } x \in \bigcup_{n=1}^\infty D_n \\ x & \text{otherwise}\end{cases}$

with the union index starting at $1$ . In the end, starting the union at $0$ or $1$ does not change the behavior of $g$ : we never encounter the case where $x \in D_0$ because $A \cap D_0$ is empty.

That concludes the intuition for the construction outlined in the exercise statement. Here are a few other points I want to make:

Why do we need to show that the sets $D_0, D_1, D_2, \ldots$ are all disjoint from each other? It is not necessary to show this in order to prove the bijectivity of $g$ . My understanding is that it is just an interesting additional fact one can prove about this setup, and also justifies drawing the separate green parts in a way that looks disjoint.
Why do we assume that $f : C \to A$ is an injection rather than a bijection (as was originally the case in the 1st and 2nd editions of the book)? I haven’t thought about this in detail. I think it makes sense to use the weaker assumption of injectivity if bijectivity is not required, especially since the Schröder–Bernstein theorem only assumes injectivity.
What happens when we only assume $B \subseteq C$ rather than $C = B$ as above? The pictures above change slightly: now there is a bigger set $C$ surrounding both $B$ and $A$ . Otherwise the pictures don’t change. In the proof there is slightly more work since we must verify that when we use $f^{-1}$ in the definition of $g$ , the output lands in $B$ instead of $C$ .
Since $f$ is assumed to be an injection rather than a bijection, what does it even mean to write $f^{-1}(x)$ for some $x \in A$ ? For an injection $f : C \to A$ , the map $\tilde f : C \to f(C)$ is a bijection (why?), so $\tilde f^{-1} : f(C) \to C$ is a (bijective) function. So whenever $x \in f(C)$ we can define $f^{-1}(x) := \tilde f^{-1}(x)$ . If $x \notin f(C)$ we leave $f^{-1}(x)$ undefined. This means that in the model solution below, when we define $g$ , we must verify that if $x \in \bigcup_{n=1}^\infty D_n$ then $x \in f(C)$ .
Why did Tao assume that $A \subseteq B$ instead of allowing $A, B$ to be unrelated sets (like in most expositions of the Schröder–Bernstein theorem)? Assuming $A \subseteq B$ simplifies the drawing: if $A,B$ are unrelated sets, one would need to draw two pictures instead of one (like on this page). By making $A$ a subset of $B$ , there is just one picture, and there is a simple rule for defining the bijection $g$ : if you’re in a white area, stay put, and if you’re in a green area, “climb up” one level to take up a larger amount of space in a bijective way.

Finally, I want to consider a particularly simple case of the construction outlined in this exercise: what if the sets $A,B,C$ are all finite? If there is an injection $f:C\to A$ , that means $\#(C) \leq \#(A)$ by Exercise 3.6.7. But since $A \subseteq C$ , we also have $\#(A) \leq \#(C)$ by Proposition 3.6.14(c). Thus $\#(A) = \#(C)$ . If $A \ne C$ then we would have $\#(A) < \#(C)$ by Proposition 3.6.14(c) again, a contradiction. Thus we must have $A = C$ . Similarly we have $\#(A) \leq \#(B)$ and $\#(B) \leq \#(C) = \#(A)$ so $\#(A) = \#(B)$ . Since $A \subseteq B$ , we can use Proposition 3.6.14(c) to conclude again that $A=B$ . Thus in the finite case, all three sets must be the same. So we can try something like $A=B=C=\{1,2,3\}$ . Then $D_0 = B\setminus A = \emptyset$ , and $D_1 = f(D_0) = f(\emptyset) = \emptyset$ , and so on, so that $\bigcup_{n=1}^\infty D_n = \emptyset$ as well. This means that in the definition of $g$ , we only ever encounter the case where $g(x)=x$ . This does indeed give a bijection, since the identity map $\iota_{A\to A}$ is a bijection.

Model solution

First we show that the sets $D_0, D_1, \ldots$ are all disjoint from each other. We do this by showing the following statement: for every natural number $n$ and every positive integer $k$ , the sets $D_n$ and $D_{n+k}$ are disjoint. Once we have proved this, given two distinct natural numbers, we can let $m$ be the larger one so that $m > n$ . Then we can write $m = n + k$ for some positive integer $k$ and see that $D_n$ and $D_m = D_{n+k}$ are disjoint.

To prove the statement from above, let $k$ be a positive integer. We will induct on $n$ . For the base case, $n=0$ , we must show that $D_0$ and $D_k$ are disjoint. But $D_0 = B \setminus A$ and $D_k = f^k(D_0)\subseteq A$ so these two sets are disjoint: if $x \in D_0 \cap D_k$ we would have $x \notin A$ and $x \in A$ , a contradiction. Now suppose inductively that $D_n$ and $D_{n+k}$ are disjoint. We need to show that $D_{n+1}$ and $D_{n+1+k}$ are disjoint. Suppose for sake of contradiction that there is some $x \in D_{n+1} \cap D_{n+1+k}$ . Then since $D_{n+1} = f(D_n)$ and $D_{n+1+k} = D_{n+k+1} = f(D_{n+k})$ there exist $z \in D_n$ and $z' \in D_{n+k}$ such that $x = f(z)$ and $x = f(z')$ . But $f$ is injective so $f(z) = x = f(z')$ implies $z=z'$ . Since $D_n$ and $D_{n+k}$ are disjoint, this is impossible. This closes the induction.

Now define $g : A \to B$ as in the exercise statement:

$\displaystyle g(x) := \begin{cases}f^{-1}(x) & \text{if } x \in \bigcup_{n=1}^\infty D_n \\ x & \text{otherwise}\end{cases}$

We first verify that $g$ maps from $A$ to $B$ . The things to check are:

$f^{-1}(x)$ is defined for each $x \in \bigcup_{n=1}^\infty D_n$ : the value $f^{-1}(x)$ is only defined when $x \in f(C)$ , so we must verify that if $x \in \bigcup_{n=1}^\infty D_n$ then $x \in f(C)$ . So suppose $x \in \bigcup_{n=1}^\infty D_n$ . Then $x \in D_{n+1}$ for some natural number $n$ , so we have $x \in D_{n+1} = f(D_n) \subseteq f(C)$ as required.
If $x \in \bigcup_{n=1}^\infty D_n$ then $g(x) := f^{-1}(x)$ lands in $B$ : We have $x \in f(D_n)$ for some natural number $n$ , so $x = f(z)$ for some $z \in D_n$ . Thus $f^{-1}(x) = f^{-1}(f(z)) = z \in D_n$ . But $D_0 = B\setminus A \subseteq B$ and $D_m \subseteq A \subseteq B$ for each positive $m$ , so in any case we have $z \in B$ as required.
If $x \notin \bigcup_{n=1}^\infty D_n$ then $g(x) := x$ lands in $B$ : In this case, we still have $x \in A$ since $x$ is in the domain of $g$ , which means $x \in B$ since $A \subseteq B$ .

Thus $g$ maps from $A$ to $B$ .

Now we show that $g$ is injective. Let $x, y \in A$ . We must show that $g(x) = g(y)$ implies $x=y$ . So suppose $g(x) = g(y)$ . We have three cases:

Both $x$ and $y$ are in $\bigcup_{n=1}^\infty D_n$ : We have $f^{-1}(x) = f^{-1}(y)$ . Since $f$ is injective, $f^{-1} : f(C) \to C$ is a bijection. Thus whenever $f^{-1}$ is defined, we can assume it acts bijectively. We thus have $x=y$ .
Neither $x$ nor $y$ is in $\bigcup_{n=1}^\infty D_n$ : By definition of $g$ we have $g(x)=x$ and $g(y)=y$ so $g(x)=g(y)$ means $x=y$ .
Exactly one of the two elements is in $\bigcup_{n=1}^\infty D_n$ : We can suppose $x \in \bigcup_{n=1}^\infty D_n$ and $y \notin \bigcup_{n=1}^\infty D_n$ (we can relabel $x$ and $y$ and repeat the same steps if it is the other way around). We have $g(x) = f^{-1}(x)$ and $g(y)=y$ so $f^{-1}(x) = y$ . But $x \in D_{n+1}$ for some natural number $n$ , so $x \in f^{n+1}(B\setminus A)$ . Thus $f^{-1}(x) \in f^n(B \setminus A)$ . This means $f^{-1}(x)$ is either in $B\setminus A$ or is in $\bigcup_{n=1}^\infty D_n$ . But $y$ is in $A$ (as it is in the domain of $g$ ) so it can’t be in $B\setminus A$ , and $y \notin \bigcup_{n=1}^\infty D_n$ by hypothesis of this case, so we have a contradiction. This means that this case actually isn’t possible so we don’t need to worry about it.

Now we show that $g$ is surjective. To do this, let $y \in B$ . We must find some $x \in A$ such that $g(x) = y$ . We have two cases, $y \in \bigcup_{n=0}^\infty D_n$ or $y \notin \bigcup_{n=0}^\infty D_n$ .

If $y \in \bigcup_{n=0}^\infty D_n$ then $y \in D_n$ for some natural number $n$ so $f(y) \in f(D_n)$ , which means that $f(y) \in \bigcup_{n=1}^\infty D_n$ . Thus if we let $x := f(y)$ then we have $g(x) = g(f(y)) = f^{-1}(f(y)) = y$ .
On the other hand, if $y \notin \bigcup_{n=0}^\infty D_n$ then $y$ is also not in the smaller sets $D_0$ and $\bigcup_{n=1}^\infty D_n$ . From $y\notin D_0 = B\setminus A$ we see that $y \in A$ , so $g(y)$ is defined. And from $y\notin\bigcup_{n=1}^\infty D_n$ we see that $g(y) = y$ . Thus for $x := y$ we have $g(x) = g(y) = y$ .