Exercise 6.6.2

October 21, 2023 Issa Rice Leave a comment

Exercise statement

Can you find two sequences $(a_n)_{n=0}^\infty$ and $(b_n)_{n=0}^\infty$ which are not the same sequence, but such that each is a subsequence of the other?

Hints

None.

How to think about the exercise

In the book, Tao writes “The property of being a subsequence is reflexive and transitive, though not symmetric” (meaning it fails to be an equivalence relation). Using terminology from Definition 8.5.1, this exercise shows that the relation “is a subsequence of” is not anti-symmetric either, and hence is not a partial order. (Contrast this with the relation “is a subset of” for sets, which is anti-symmetric, and also happens to be reflexive and transitive, and so is a partial order.)

You will see in the solution below that in finding a counterexample, we are taking advantage of how the sequence elements repeat. Must all the examples we can find have repeating elements? I think it’s possible to prove this, and I think it’s even possible to prove a slightly stronger claim that all examples must have infinitely repeating elements, so that at least for the class of non-repeating (or non-infinitely repeating) sequences, “is a subsequence of” is a partial order.

Model solution

Consider $(a_n)_{n=0}^\infty = (0,1,0,1,0,1,\ldots)$ defined by

$\displaystyle a_n := \begin{cases}0 & \text{if }n\text{ is even} \\ 1 & \text{if }n\text{ is odd}\end{cases}$

and $(b_n)_{n=0}^\infty = (1,0,1,0,1,0,\ldots)$ defined by

$\displaystyle b_n := \begin{cases}1 & \text{if }n\text{ is even} \\ 0 & \text{if }n\text{ is odd}\end{cases}$

The function $f : \mathbf N \to \mathbf N$ defined by $f(n) := n+1$ is increasing (why?), and we have $b_n = a_{f(n)}$ and $a_n = b_{f(n)}$ for each $n \in \mathbf N$ . So each sequence is a subsequence of the other, as required.

(To show this rigorously we’d need to define “even” and “odd”, prove a version of Euclidean division with uniqueness so we can say that a natural number is exactly one of even or odd, and show that a natural number $n$ is even (respectively odd) iff $f(n)$ is odd (respectively even). But I think this exercise was intended just as an opportunity to quickly come up with a counterexample and move on, not a place to spend a bunch of time proving facts about number theory. But if anyone in the comments wants help making this rigorous, I can maybe do this at some point.)

Solutions

Exercise 6.4.5

October 19, 2023 Issa Rice 2 Comments

Exercise statement

Use Lemma 6.4.13 to prove Corollary 6.4.14.

Corollary 6.4.14 (Squeeze test). Let $(a_n)_{n=m}^\infty$ , $(b_n)_{n=m}^\infty$ , and $(c_n)_{n=m}^\infty$ be sequences of real numbers such that

$a_n \leq b_n \leq c_n$

for all $n \geq m$ . Suppose also that $(a_n)_{n=m}^\infty$ and $(c_n)_{n=m}^\infty$ both converge to the same limit $L$ . Then $(b_n)_{n=m}^\infty$ is also convergent to $L$ .

Hints

You will probably also want to make use of some other results from this section.

How to think about the exercise

This is one of those exercises that you can do purely by pattern matching, without any deep thought. Let me show what I mean by doing the exercise in this way.

We are supposed to use Lemma 6.4.13. Lemma 6.4.13 has a hypothesis that looks like $a_n \leq b_n$ . Here we have $a_n \leq b_n \leq c_n$ instead. That means we get for free:

$\displaystyle \sup(a_n)_{n=m}^\infty \leq \sup(b_n)_{n=m}^\infty \leq \sup(c_n)_{n=m}^\infty$

$\displaystyle \inf(a_n)_{n=m}^\infty \leq \inf(b_n)_{n=m}^\infty \leq \inf(c_n)_{n=m}^\infty$

$\displaystyle \limsup_{n\to\infty} a_n \leq \limsup_{n\to\infty} b_n \leq \limsup_{n\to\infty} c_n$

$\displaystyle \liminf_{n\to\infty} a_n \leq \liminf_{n\to\infty} b_n \leq \liminf_{n\to\infty} c_n$

Can we do anything useful with these inequalities? Nothing immediately comes to mind. But there’s still some hypotheses we haven’t used yet, namely that both $(a_n)_{n=m}^\infty$ and $(c_n)_{n=m}^\infty$ converge to the same limit $L$ . Is there some previous result we have learned that allows us to connect limits to things like $\sup, \inf, \limsup, \liminf$ ? Flipping backwards in the book, we find Proposition 6.4.12(f), which mentions both $\limsup, \liminf$ and limits. Can we make use of this result? The first part seems relevant. It says that if a limit exists, then both the limit superior and limit inferior are equal to it. So we can update two of the inequalities above:

$L=\displaystyle \limsup_{n\to\infty} a_n \leq \limsup_{n\to\infty} b_n \leq \limsup_{n\to\infty} c_n=L$

$L=\displaystyle \liminf_{n\to\infty} a_n \leq \liminf_{n\to\infty} b_n \leq \liminf_{n\to\infty} c_n=L$

This seems useful. We’ve constrained the values of both $\limsup_{n\to\infty} b_n$ and $\liminf_{n\to\infty} b_n$ . In fact, they both have to be equal to $L$ . At this point, the second part of Proposition 6.4.12(f) becomes useful, and completes the result.

So the general strategy for this sort of exercise is to just flip backwards through the book, trying to look for any result that seems useful (e.g. mentions some of the same kinds of objects we are currently working with), and then see what new facts we can get.

Model solution

Since we have $a_n \leq b_n \leq c_n$ for all $n \geq m$ , Lemma 6.4.13 gives us

$\displaystyle \limsup_{n\to\infty} a_n \leq \limsup_{n\to\infty} b_n \leq \limsup_{n\to\infty} c_n$

and

$\displaystyle \liminf_{n\to\infty} a_n \leq \liminf_{n\to\infty} b_n \leq \liminf_{n\to\infty} c_n$

But since $\lim_{n\to \infty} a_n = L$ , Proposition 6.4.12(f) gives us $\limsup_{n\to\infty} a_n = \liminf_{n\to\infty} a_n = L$ . Similarly, since $\lim_{n\to \infty} c_n = L$ , Proposition 6.4.12(f) gives us $\limsup_{n\to\infty} c_n = \liminf_{n\to\infty} c_n = L$ . Thus the above inequalities become

$\displaystyle L \leq \limsup_{n\to\infty} b_n \leq L$

and

$\displaystyle L \leq \liminf_{n\to\infty} b_n \leq L$

This means that $\limsup_{n\to\infty} b_n = L$ and $\liminf_{n\to\infty} b_n = L$ . So by Proposition 6.4.12(f) again, we have $\lim_{n\to\infty} b_n = L$ as desired.

Solutions

Exercise 8.5.5

October 17, 2023 Issa Rice Leave a comment

Exercise statement

Let $f: X \to Y$ be a function from one set $X$ to another set $Y$ . Suppose that $Y$ is partially ordered with some ordering relation $\leq_Y$ . Define a relation $\leq_X$ on $X$ by defining $x \leq_X x'$ if and only if $f(x) <_Y f(x')$ or $x=x'$ . Show that this relation $\leq_X$ turns $X$ into a partially ordered set. If we know in addition that the relation $\leq_Y$ makes $Y$ totally ordered, does this mean that the relation $\leq_X$ makes $X$ totally ordered also? If not, what additional assumption needs to be made on $f$ in order to ensure that $\leq_X$ makes $X$ totally ordered?

Hints

Why did Tao define $\leq_X$ by the condition $f(x) <_Y f(x')$ or $x=x'$ rather than simply the condition $f(x) \leq_Y f(x')$ ?

How to think about the exercise

The first part of the exercise, where you must show that $\leq_X$ is partially ordered, is straightforward so I won’t comment on it. The latter parts of the exercise are more interesting and may be tricky, so I will discuss how I thought through the exercise.

As you might have guessed, when Tao asks you whether something is true rather than just telling you to prove a fact, it typically means the statement in question is not true. Let’s try to see why. I’m going to make use of two heuristics here, which I will call “try a simple example” and “try to prove the false statement and see what goes wrong”.

Try a simple example

One way to solve problems that pretty reliably works is to just to try scribbling down some simple concrete examples. I started out by drawing some dots to represent the sets $X$ and $Y$ , with order signs to indicate that $Y$ is totally ordered:

And then I just drew some arrows to represent the function $f$ :

I tried to not make the function too nice, so that it would appear to be a “random” function. In particular, I chose a function that was neither injective nor surjective. Now, can we totally order $X$ ? Notice that the rightmost dot in $X$ is clearly larger than either of the dots on the left, but among the first and second dots, there’s no clear ordering between them.

Because the lack of total ordering happened at exactly the spot where $f$ failed to be injective (we have two points in $X$ both mapping to the same point in $Y$ ), our first guess should be that injectivity is the additional assumption we need to force $\leq_X$ to be a total order. And sure enough, drawing a few more examples should convince you this is the case.

Try to prove the false statement and see what goes wrong

Another good strategy when trying to figure out what assumptions are needed to show something is to just try proving the thing, and seeing what goes wrong and what extra thing you need. In this case, we assume $\leq_Y$ is a total order, and then we try to prove that $\leq_X$ is also a total order. To do this, let $x, x' \in X$ . We want to show that $x \leq_X x'$ or $x' \leq_X x$ . In other words, we want to show that $f(x) <_Y f(x')$ or $f(x') <_Y f(x)$ or $x=x'$ . The case $x=x'$ is easy; maybe we just got lucky and happened to pick the same element out of $X$ both times. So suppose $x\ne x'$ . Can we always show that $f(x) <_Y f(x')$ or $f(x') <_Y f(x)$ ? Since we assumed that $\leq_Y$ is a total order, we know that $f(x) \leq_Y f(x')$ or $f(x') \leq_Y f(x)$ . Maybe we can show that when $f(x) \leq_Y f(x')$ we actually have $f(x) <_Y f(x')$ so that $x \leq_X x'$ and similarly when $f(x') \leq_Y f(x)$ we’ll have $x' \leq_X x$ ? In either case, the important thing we must show in order to prove strict inequality is $f(x) \ne f(x')$ . And here we see the problem: we have only assumed $x\ne x'$ , and now we’re trying to show $f(x) \ne f(x')$ . This is the defining property of an injection.

Another way to see the problem is that we know $f(x) <_Y f(x')$ or $f(x') <_Y f(x)$ , but we might have both $f(x) \leq_Y f(x')$ and $f(x') \leq_Y f(x)$ , in which case anti-symmetry of $\leq_Y$ gives us that $f(x) = f(x')$ . In other words, we’ll end up with $x\ne x'$ such that $f(x) = f(x')$ , which you might notice is precisely a failure of $f$ to be injective.

Model solution

We first show that the relation $\leq_X$ is a partial ordering of $X$ . To do this, we must show that $\leq_X$ satisfies reflexivity, anti-symmetry, and transitivity. We will go through each property one by one:

Reflexivity: Let $x \in X$ . We must show that $x \leq_X x$ . But $x=x$ , so by definition of $\leq_X$ we have $x \leq_X x$ .
Anti-symmetry: Let $x,x' \in X$ and suppose we have both $x \leq_X x'$ and $x' \leq_X x$ . To show that $\leq_X$ is anti-symmetric, we must now show that $x=x'$ . Suppose for the sake of contradiction that $x\ne x'$ . Since $x \leq_X x'$ , this means that $f(x) <_Y f(x')$ (because we’ve ruled out the possibility that $x=x'$ ), and since $x' \leq_X x$ this means that $f(x') <_Y f(x)$ . Since $\leq_Y$ is a partial order, this means that we have both $f(x) = f(x')$ (via anti-symmetry of $\leq_Y$ ) as well as $f(x) \ne f(x')$ (by definition of $<_Y$ ). This contradiction shows that we have $x=x'$ after all, and thus $\leq_X$ is anti-symmetric.
Transitivity: Let $x, x', x'' \in X$ and suppose we have both $x \leq_X x'$ and $x' \leq_X x''$ . To show transitivity, we must now prove that $x \leq_X x''$ . If $x=x'$ or $x'=x''$ then we automatically have transitivity; for instance if $x=x'$ then $x' \leq_X x''$ can be written as $x \leq_X x''$ , and similarly for the other case. Thus we only need to consider the case where $x\ne x'$ and $x'\ne x''$ . In this case, we have both $f(x) <_Y f(x')$ and $f(x') <_Y f(x'')$ . Now by transitivity of $\leq_Y$ we have $f(x) \leq_Y f(x'')$ . But not only that: if $f(x)=f(x'')$ we would have $f(x'') \leq_Y f(x)$ which combined with $f(x) <_Y f(x')$ would (by transitivity) show that $f(x'') \leq_Y f(x')$ . So we would have both $f(x'') \leq_Y f(x')$ and $f(x') <_Y f(x'')$ , so by anti-symmetry we would have $f(x'')=f(x')$ , a contradiction of $f(x') <_Y f(x'')$ . So we must have $f(x)\ne f(x'')$ after all, which combined with $f(x) \leq_Y f(x'')$ means $f(x) <_Y f(x'')$ . Thus $x \leq_X x''$ .

Now suppose that $\leq_Y$ is a total order. We will show that this does not necessarily mean $\leq_X$ is a total order. Any non-injective function $f$ will do, but for concreteness, let $X := \{1,2\}$ , let $Y := \mathbf Z$ , and let $\leq_Y$ be the usual ordering relation $\leq$ on the integers. Define $f : X \to Y$ by $f(x) := 0$ for all $x \in X$ . Now $\leq_X$ cannot order $1$ and $2$ because all three of the statements $f(1) < f(2)$ , $f(2) < f(1)$ , and $1=2$ are false. This shows that $\leq_X$ is not a total order. In fact, this happens anytime $f$ is not injective, as we will presently show.

The additional assumption that $f$ is injective is both necessary and sufficient to ensure that $\leq_X$ makes $X$ totally ordered. First suppose that $f$ is injective. We want to show that $\leq_X$ is a total ordering of $X$ . So let $x,x' \in X$ . We want to show that $x \leq_X x'$ or $x' \leq_X x$ . In other words, we must show that $f(x) <_Y f(x')$ or $f(x') <_Y f(x)$ or $x=x'$ . If $x=x'$ are done, so suppose $x\ne x'$ . Since $f$ is injective, this means $f(x) \ne f(x')$ . But now by the assumption that $\leq_Y$ is a total order, we must have $f(x) \leq_Y f(x')$ or $f(x') \leq_Y f(x)$ . Since the option $f(x)=f(x')$ is not available, this means that $f(x) <_Y f(x')$ or $f(x') <_Y f(x)$ . This completes the first direction.

Now suppose that $f$ is not injective. Then there must be elements $x,x' \in X$ such that $x\ne x'$ and $f(x)=f(x')$ . Our goal is to show that $\leq_X$ is not a total order. We cannot have $x \leq_X x'$ since this would mean $f(x) <_Y f(x')$ (remember, $f(x)=f(x')$ ) or $x=x'$ , and we know both are false. We also cannot have $x' \leq_X x$ for similar reasons.

Solutions

Exercise 3.3.6

October 14, 2023 Issa Rice Leave a comment

Exercise statement

Let $f : X \to Y$ be a bijective function, and let $f^{-1} : Y \to X$ be its inverse. Verify the cancellation laws $f^{-1}(f(x)) = x$ for all $x \in X$ and $f(f^{-1}(y)) = y$ for all $y \in Y$ . Conclude that $f^{-1}$ is also invertible, and has $f$ as its inverse (thus $(f^{-1})^{-1} = f$ ).

Hints

None.

How to think about the exercise

On one hand, this is a pretty obvious exercise and all of the results shown in it should make sense to you. On the other hand, I think it can be tricky to stick to just the definitions and what we know about bijective functions, and be vigilant so as to not smuggle in any extra “obvious” facts about bijective functions. But as long as you are extra careful, you should just be able to straightforwardly do the exercise.

Model solution

Let $x \in X$ be arbitrary. Now $f(x) \in Y$ . We can define the variable $y := f(x)$ . Since $f$ is bijective, for this $y \in Y$ , there is exactly one $x' \in X$ such that $f(x') = y$ , and we denote this $x'$ by $f^{-1}(y)$ . But clearly this $x'$ must be the same as our $x$ . If that’s not clear to you, you can start with $f(x') = y = f(x)$ and use the injectivity of $f$ to conclude $x'=x$ . So now just simply chasing down the equalities we know about, we see that $x=x'=f^{-1}(y)=f^{-1}(f(x))$ (in the last equality, we’re using the substitution axiom of equality). But that’s just what we wanted to show. So we’re done with the first claim. Note that we didn’t really need the variable $y$ at all in this part, but I think using the extra variable makes things a bit clearer.

Now let $y \in Y$ be arbitrary (this is a new variable we are declaring, and may not have anything to do with the $y$ in the previous paragraph). Since $f$ is bijective, for our given $y$ there is exactly one $x \in X$ such that $f(x) = y$ , and we denote this $x$ by $f^{-1}(y)$ . In other words, $x = f^{-1}(y)$ . Now what happens if we just apply $f$ to both sides of that equation? We get $f(x) = f(f^{-1}(y))$ . But we also know that $f(x)=y$ , so we have $y=f(x) = f(f^{-1}(y))$ , which is exactly what we wanted to show, so we’re done with the second cancellation law.

Now we have to show that $f^{-1}$ is invertible. First we show that it is injective. Let $y,y' \in Y$ , and suppose $f^{-1}(y) = f^{-1}(y')$ . Using the second cancellation law, we apply $f$ to both sides and get $y=y'$ . So $f^{-1}$ is injective as required. Now we show it’s also surjective. Let $x \in X$ . We need to find some $y \in Y$ such that $f^{-1}(y)=x$ . Why don’t we just take $f(x) \in Y$ as our $y$ ? (Since all we have to work with are $x$ , $f$ , and $f^{-1}$ , we don’t really have much choice in constructing an element of $Y$ .) Indeed, applying the first cancellation law, we get $f^{-1}(f(x))=x$ , so $f^{-1}$ is surjective.

Finally, we need to show that $f^{-1}$ has $f$ as its inverse. Since $f^{-1}$ is bijective, for every $x \in X$ there is exactly one $y \in Y$ such that $f^{-1}(y)=x$ . By the textbook, this value of $y$ is denoted $(f^{-1})^{-1}(x)$ . If we can show that this $(f^{-1})^{-1}(x)$ is the same as $f(x)$ , we will have shown that $(f^{-1})^{-1}=f$ . To do this, we simply take the equation $f^{-1}(y)=x$ and apply $f$ to both sides, to get $f(f^{-1}(y))=f(x)$ . By the second cancellation law, this becomes $y=f(x)$ . But we already know that $y = (f^{-1})^{-1}(x)$ , so this means $(f^{-1})^{-1}(x)=f(x)$ , and now we are done.