Design a site like this with WordPress.com

# Exercise 3.2.2

## Exercise statement

Use the axiom of regularity (and the singleton set axiom) to show that if $A$ is a set, then $A \notin A$. Furthermore, show that if $A$ and $B$ are two sets, then either $A \notin B$ or $B \notin A$ (or both).

## Hints

1. Think about which set you want to construct using the singleton set axiom.

## How to think about the exercise

We are told to use the singleton set axiom. There is really only one choice of a set we can construct using this axiom, because we are only given the set $A$. So we make the set $\{A\}$.

Now when we use the axiom of regularity, we know of two sets, $A$ and $\{A\}$, so we have the choice of applying the axiom to either set. Let’s take a guess and apply it to $\{A\}$. Since $\{A\}$ is non-empty, the axiom of regularity says that there is at least one element $x \in \{A\}$ which is either not a set or is disjoint from $\{A\}$. But the only element in $\{A\}$ is $A$, so we must have that either $A$ is not a set or $A$ is disjoint from $\{A\}$. Since $A$ is a set, we conclude that $A$ is disjoint from $\{A\}$, i.e. $A \cap \{A\} = \emptyset$. In particular, this means that $A$ cannot be an element of both $A$ and $\{A\}$; since $A \in \{A\}$, we therefore conclude that $A \notin A$.

How should we do the second part of the exercise? A good guess is to repeat the same technique as the first part. But now we have two sets $A$ and $B$, so we can use the pair set axiom instead and consider the set $\{A,B\}$.

We then apply the axiom of regularity to the set $\{A,B\}$: there must be some $x \in \{A,B\}$ which is either not a set or is disjoint from $\{A,B\}$. The only two elements of $\{A,B\}$ are the sets $A$ and $B$, so the axiom of regularity tells us that either $A$ is disjoint from $\{A,B\}$ or $B$ is disjoint from $\{A,B\}$. In the first case, $A \cap \{A,B\} = \emptyset$ so in particular $B \notin A \cap \{A,B\}$; since $B \in \{A,B\}$ this means that $B \notin A$. In the second case, $B \cap \{A,B\} = \emptyset$ so in particular $A \notin B \cap \{A,B\}$; but since $A \in \{A,B\}$ this means $A \notin B$.

As you can see, once you know to use the singleton set axiom (or pair set axiom), each step of the solution is just the next obvious step. So the real insight of this proof is to consider using the singleton set axiom (or pair set axiom) in the first place, or alternatively to think of constructing the sets $\{A\}$ and $\{A,B\}$, which Tao just gave away in the exercise statement itself! How would we have thought of that?

I think the trick is to realize that the axiom of foundation only tells us about the existence of a certain element in a given set. We want to use the axiom of foundation (since this axiom was introduced specifically to rule out Russell’s paradox), but if a set contains a bunch of elements like $1$ or $\emptyset$ then the axiom of foundation will only tell us something we already know. To get some actual value out of the axiom of foundation, we must construct a simple set, the elements of which we want to know more about. So constructing a set consisting only of the supposedly “paradoxical” sets $A$ and $B$ will give us what we need.

One last note: it is easy to write this proof as a proof by contradiction, but notice how it’s not required (or more precisely, we can push the “proof by contradiction” nature to start at the very end of the proof, rather then declaring it at the start). That makes the proof easier to read, in my opinion. It may still help you to discover the proof if you started out by assuming $A\in A$ though (as I actually did when I first started solving this exercise).

## Model solution 1

Consider the set $\{A\}$, which exists by the singleton set axiom. By the axiom of regularity applied to $\{A\}$, there is at least one element $x \in \{A\}$ which is either not a set or is disjoint from $\{A\}$. Since $x \in \{A\}$, we must have $x=A$. Since $x=A$ is a set, this means that it is disjoint from $\{A\}$, i.e. $A\cap \{A\}=\emptyset$. If $A \in A$ then $A$ would be in $A\cap \{A\}$, so we must have $A \notin A$ as required.

Now consider the set $\{A,B\}$, which exists by the pair set axiom. By the axiom of regularity applied to $\{A,B\}$, there is at least one element $x \in \{A,B\}$ which is either not a set or is disjoint from $\{A,B\}$. Since $x \in \{A,B\}$ we must have $x=A$ or $x=B$. If $x=A$ then $A$ is disjoint from $\{A,B\}$ so in particular $B \notin A \cap \{A,B\}$; since $B \in \{A,B\}$ this means that $B \notin A$. On the other hand, if $x=B$ then $B$ is disjoint from $\{A,B\}$ so in particular $A \notin B \cap \{A,B\}$; but since $A \in \{A,B\}$ this means $A \notin B$. So either $B \notin A$ or $A \notin B$, which is what we wanted to show.

## Model solution 2

This version does the second part of the exercise first, exactly as in Model solution 1. Thus we know that if $A$ and $B$ are two sets, then either $A \notin B$ or $B \notin A$ (or both).

Now to show the first part of the exercise, let $A$ be given and take $B := A$. Applying the first part of the exercise, we must have $A \notin B$ or $B \notin A$. In other words, we must have $A \notin A$ or $A \notin A$, i.e. we have $A \notin A$ as desired.

# New page about an independent review

This is just a short announcement that I’ve put up a new page about an independent review/grading of the solutions on this blog.

# Exercise 6.4.3, part (c)

This post was written by Berke Özgür Arslan, who has generously offered to help Issa complete the blog. It has been edited and converted into the WordPress blog post format by Issa.

## Exercise statement

Prove part (c) of Proposition 6.4.12. (Since this is a long exercise, Issa has decided to split it up across different blog posts.)

Proposition 6.4.12. Let $(a_{n})_{n=m}^{\infty}$ be a sequence of real numbers, let $L^+$ be the limit superior of this sequence, and let $L^-$ be the limit inferior of this sequence (thus both $L^+$ and $L^-$ are extended real numbers).

(a) For every $x > L^+$, there exists an $N \geq m$ such that $a_n < x$ for all $n \geq N$. (In other words, for every $x > L^+$, the elements of the sequence $(a_{n})_{n=m}^{\infty}$ are eventually less than $x$.) Similarly, for every $y < L^-$ there exists an $N \geq m$ such that $a_n > y$ for all $n \geq N$.

(b) For every $x < L^+$, and every $N \geq m$, there exists an $n \geq N$ such that $a_n > x$. (In other words, for every $x < L^+$, the elements of the sequence $(a_{n})_{n=m}^{\infty}$ exceed $x$ infinitely often.) Similarly, for every $y > L^-$ and every $N \geq m$, there exists an $n \geq N$ such that $a_n < y$.

(c) We have $\inf(a_{n})_{n=m}^{\infty} \leq L^- \leq L^+ \leq \sup(a_{n})_{n=m}^{\infty}$.

(d) If $c$ is any limit point of $(a_{n})_{n=m}^{\infty}$, then we have $L^- \leq c \leq L^+$.

(e) If $L^+$ is finite, then it is a limit point of $(a_{n})_{n=m}^{\infty}$. Similarly, if $L^-$ is finite, then it is a limit point of $(a_{n})_{n=m}^{\infty}$.

(f) Let $c$ be a real number. If $(a_{n})_{n=m}^{\infty}$ converges to $c$, then we must have $L^+ = L^- = c$. Conversely, if $L^+ = L^- = c$, then $(a_{n})_{n=m}^{\infty}$ converges to $c$.

## Hints

This is a tricky exercise and there are a few ways to approach it. One way is to split by cases based on whether $L^+$ and $L^-$ are finite, $+\infty$, or $-\infty$ (it should also be possible to split by cases depending on whether the original sequence $(a_n)_{n=m}^\infty$ is bounded or not). For this approach, you may want to decide whether the sequences $(a_N^+)_{N=m}^{\infty}$ and $(a_N^-)_{N=m}^{\infty}$ are increasing or decreasing, then to compare their terms, and then to use Proposition 6.3.8 followed by a version of Corollary 5.4.10 for sequences of real numbers. For the cases in which $L^+$ and $L^-$ may not be finite, use part (a) of the proposition.

## How to think about the exercise

The concepts of limit superior and limit inferior may be difficult to grasp when one encounters their definitions for the first time. A very helpful picture to keep in mind is the piston analogy that Tao gives before the statement of Proposition 6.4.12. As we keep removing elements $a_1$, then $a_2$, and so on, the supremum piston can only slip leftward. This suggests that the sequence $a_1^+, a_2^+, a_3^+, \ldots$ is a decreasing sequence. One of the few results we have so far about decreasing sequences is Proposition 6.3.8 , so it is a good bet that we will want to make use of that result.

So the first thing to try in order to tackle this proof is to treat the sequences $(a_{N}^+)_{N=m}^{\infty}$ and $(a_{N}^-)_{N=m}^{\infty}$ like we would treat any regular sequence. We are dealing here with the infimum and the supremum of these sequences respectively; so it would be nice to use Proposition 6.3.8 and convert the infimum and supremum of these sequences into their limits. But this is only possible when $(a_{N}^+)_{N=m}^{\infty}$ is decreasing and bounded below, and $(a_{N}^-)_{N=m}^{\infty}$ is increasing and bounded above. For the boundedness, luckily, the cases in which these sequences are not bounded correspond to the cases in which $L^+$ and $L^-$ are either $+\infty$ or $-\infty$, so we can treat these cases separately, and it is seen easily that these cases do not violate the proposition.

In order to see whether $(a_{N}^-)_{N=m}^{\infty}$ is increasing or not, we need to refer to its definition. For some number $M$, we know that $a_M^-$ is the infimum of the terms $a_M, a_{M+1}, a_{M+2}, \ldots$ starting with the index $M$. Therefore, informally, we can say that the infimum of a sequence starting from a smaller index, say, 5, cannot be greater than of a sequence starting from a greater index, say, 10. This is because the sequence starting from index 5 contains the sequence starting from index 10, and it is “easier” to find an even smaller infimum when we have more elements to choose from. (If that was difficult to follow, you can also consider a piston moving to the right and slipping rightward.) Then we must conclude that the sequence of infima is an increasing sequence. You should figure out an analogous argument for the sequence of suprema. Then we just use Proposition 6.3.8 to conclude that limsup and liminf are just the limits of these sequences. (This also justifies the notation $\limsup$ and $\liminf$: $\limsup$ is the limit of the suprema, i.e. $\displaystyle \limsup_{n\to\infty} a_n = \lim_{n\to \infty} \sup(a_N)_{N=n}^\infty$, and similarly for $\liminf$.)

After this, we need to make another important observation. If we pick yet again any number $M$, then $a_M^-$ is the infimum of the sequence $(a_n)_{n=M}^{\infty}$, and $a_M^+$ is its supremum. Clearly, we have $a_M^- \leq a_M^+$, and by the analogue of Corollary 5.4.10 for real sequences this means that their limits will behave accordingly; and we get the desired result.

While considering the cases where $L^+$ and $L^-$ may not be finite, the following table might help you to keep track of what you need to show. Check marks indicate that their corresponding cases already satisfy the proposition because $+\infty$ is always larger than any extended real number, and $-\infty$ is smaller than any extended real number, so there is nothing to show. In the proof, we show that the cases indicated with a question mark cannot exist. Try to see why the assertions (1) “If $L^+ \in \mathbf{R}$, then $L^- \neq +\infty$”, and (2) “If $L^+ = -\infty$, then $L^- = -\infty$ as well” exclude these cases.

 $L^-$ $L^+$ $\mathbf R$ $+\infty$ $-\infty$ $\mathbf R$ shown ? ✓ $+\infty$ ✓ ✓ ✓ $-\infty$ ? ? ✓

## Model solution 1

Consider first the inequality $L^+ \leq \sup(a_{n})_{n=m}^{\infty}$. Now, $L^+$ is defined to be the infimum of the sequence $(a_{N}^+)_{N=m}^{\infty}$ where $a_{N}^+ := \sup(a_{n})_{n=N}^{\infty}$, so it should be smaller than any particular element of this sequence. Therefore $L^+ \leq a_{N}^+$ for all $N \geq m$, and in particular for $N=m$, we have $L^+ \leq a_{m}^+ = \sup(a_{n})_{n=m}^{\infty}$. A similar argument gives the inequality $\inf(a_{n})_{n=m}^{\infty} \leq L^-$. Thus we only need to show that $L^- \leq L^+$ to finish part (c).

We first assume that both $L^+$ and $L^-$ are real numbers, i.e. neither of them are $+ \infty$ or $- \infty$. In this case, we first want to show that the sequences $(a_N^-)_{N=m}^{\infty}$ and $(a_N^+)_{N=m}^{\infty}$ are sequences of real numbers, i.e. that none of the elements are $+\infty$ or $-\infty$. Consider first the sequence $(a_N^+)_{N=m}^{\infty}$. We show each of the possibilities that an element is $-\infty$ or $+\infty$ leads to a contradiction:

• If some element $a_M^+ = -\infty$, then since $L^+$ is the infimum of this sequence we must have $L^+ \leq a_M^+ = -\infty$, a contradiction of Definition 6.2.3 (a real number cannot be less than or equal to $-\infty$).
• Suppose some element $a_M^+ = +\infty$. We first show that the original sequence $(a_n)_{n=m}^\infty$ is not bounded above. If there were some upper bound $K \in \mathbf R$ for the whole sequence, then this $K$ would also be an upper bound for the sequence $(a_n)_{n=M}^\infty$ starting at $n=M$. Since $a^+_M$ is the least upper bound of this sequence and $K$ is merely an upper bound, we have $+\infty = a^+_M \leq K$, a contradiction of the fact that $K$ is a real number. Thus the original sequence $(a_n)_{n=m}^\infty$ is not bounded above. But this means that $(a^+_N)_{N=m}^\infty = (+\infty, +\infty, +\infty, \ldots)$, so the infimum of this sequence is $L^+ = +\infty$, a contradiction.

A similar argument shows that $(a_N^-)_{N=m}^{\infty}$ is a sequence of real numbers.

Now let us be reminded that if $A$ and $B$ are sets of real numbers such that $A \subseteq B$, then $\sup (A) \leq \sup (B)$, and $\inf (B) \leq \inf (A)$. Now, for some $N \geq m$, by definition, we have $a_N^- = \inf (a_n)_{n=N}^{\infty} := \inf \{ a_n : n \geq N \}$ (and a similar definition for the supremum). Thus if $M \geq N$, then $\{ a_n : n \geq M \} \subseteq \{ a_n : n \geq N \}$, and we must have $a_M^- \geq a_N^-$. Thus the sequence $(a_N^-)_{N=m}^{\infty}$ is an increasing sequence. By a similar argument, we see that $(a_N^+)_{N=m}^{\infty}$ is a decreasing sequence.

Since $L^- = \sup (a_N^-)_{N=m}^{\infty}$ is a real number, the increasing sequence $(a_N^-)_{N=m}^{\infty}$ is bounded above, and since every increasing sequence which is bounded above is convergent by Proposition 6.3.8, we have $\lim \limits_{N \to \infty} a_N^- = \sup (a_N^-)_{N=m}^{\infty} = L^-$. With a similar argument for decreasing sequences which are bounded below we also have $\lim \limits_{N \to \infty} a_N^+ = L^+$. (Note: it is the application of Proposition 6.3.8 that required the sequences $(a_N^-)_{N=m}^{\infty}$ and $(a_N^+)_{N=m}^{\infty}$ to consist solely of real numbers.)

Now let $N \geq m$ be any number. The infimum of $a_N, a_{N+1}, a_{N+2}, \ldots$ is smaller than $a_N$, and the supremum of the same sequence is larger than $a_N$, so we have:

$a_N^- = \inf (a_{n})_{n=N}^{\infty} \leq a_N \leq \sup (a_{n})_{n=N}^{\infty} = a_N^+$

In other words, we have the term-wise comparison $a_N^- \leq a_N^+$. Since this is true for every $N \geq m$, we have by the analogue of Corollary 5.4.10 for real sequences that $\lim_{N\to\infty} a_N^- \leq \lim_{N\to\infty} a_N^+$. To summarize, we have:

$L^- = \liminf \limits_{n \to \infty} a_n = \lim \limits_{N \to \infty} a_N^- \leq \lim \limits_{N \to \infty} a_N^+ = \limsup \limits_{n \to \infty} a_n = L^+$

as desired.

Now, we consider the cases in which $L^+$ and $L^-$ are possibly $+\infty$ or $-\infty$. If $L^+ = +\infty$ or if $L^- = -\infty$, there is nothing to show. Thus we only need to show two things: (1) if $L^+ \in \mathbf{R}$, then $L^- \neq +\infty$, and (2) if $L^+ = -\infty$, then $L^- = -\infty$ as well. For (1), suppose for the sake of contradiction that $L^+ \in \mathbf{R}$, and $L^- = +\infty$. Since $L^- = +\infty$, then by part (a) of the proposition, for every number $y \in \mathbf{R}$, we have that $y < +\infty = L^-$, so there exists an $M \geq m$ such that $a_n > y$ for all $n \geq M$. This means that the sequence $(a_n)_{n=m}^{\infty}$ doesn’t have an upper bound. Then for each $N \geq m$, we must have $a_N^+ = \sup (a_n)_{n=N}^{\infty} = +\infty$. But then we have $\inf(a_N^+)_{N=m}^{\infty} = L^+ = +\infty$, a contradiction. Similarly, for (2), if $L^+ = -\infty$, then again by (a), for every number $x \in \mathbf{R}$, since $x > -\infty = L^+$, there exists an $M \geq m$ such that $a_n < x$ for all $n \geq M$, meaning that the sequence the sequence $(a_n)_{n=m}^{\infty}$ doesn’t have an lower bound, i.e. for each $N \geq m$, we have $a_N^- = \inf (a_n)_{n=N}^{\infty} = -\infty$. And then $\sup(a_N^-)_{N=m}^{\infty} = L^- = -\infty$, as desired.

## Model solution 2

(This section was written by Issa.)

There is another, shorter proof of part (c) that does not require breaking up the proof into cases. This proof is very neat, and I encourage you to check it out, but I also believe it is more difficult for beginners to discover. I may write it up here in detail later, but for now please check out this writeup by Sangchul Lee; it is Exercise 8(iii) on page 5.

# Analogue of Corollary 5.4.10 for real sequences

In this post, I will state an analogue of Corollary 5.4.10 for sequences of real numbers. This result easily follows in the book using Lemma 6.4.13 together with Proposition 6.4.12(f), but having this result is handy for proving parts of Proposition 6.4.12, so in order to avoid circularity/anachronisms, we will prove it here using our bare hands.

## Exercise statement

Lemma. Let $(a_n)_{n=m}^\infty$ and $(b_n)_{n=m}^\infty$ be convergent sequences of real numbers such that $a_n \geq b_n$ for all $n \geq m$. Then $\lim_{n\to\infty} a_n \geq \lim_{n\to\infty} b_n$.

## Model solution 1

Let us write $x:=\lim_{n\to\infty} a_n$ and $y:=\lim_{n\to\infty} b_n$. We are trying to show that $x \geq y$. Suppose for the sake of contradiction that $x < y$. Then $y-x > 0$ so for $\varepsilon := (y-x)/3 > 0$ we can find some $N_1 \geq m$ such that $|a_n - x| \leq \varepsilon$ for all $n \geq N_1$, and some $N_2 \geq m$ such that $|b_n - y| \leq \varepsilon$ for all $n \geq N_2$. Thus if we pick $N := \max(N_1, N_2)$ then since $N \geq N_1$ and $N \geq N_2$ we have both $|a_N - x| \leq \varepsilon$ and $|b_N - y| \leq \varepsilon$. These two inequalities say in particular that $-\varepsilon \leq x-a_N$ and $-\varepsilon \leq b_N - y$. Thus we have

\begin{aligned} b_N - a_N &= (b_N - y) + (y - x) + (x - a_N) \\ &\geq -\varepsilon + 3\varepsilon - \varepsilon \\ & = \varepsilon \\ &> 0\end{aligned}

This means that $b_N > a_N$, which contradicts the fact that $a_n \geq b_n$ for all $n \geq m$. Thus we conclude that $x \geq y$ after all.

## Model solution 2

The following solution is due to Berke Özgür Arslan.

In this proof, we mimic the proof of Corollary 5.4.10 by using the limit laws, in particular Theorem 6.1.19(d). We want to show that $\lim_{n\to\infty} a_n \geq \lim_{n\to\infty} b_n$, but this is the same thing as showing $\lim_{n\to\infty} a_n - \lim_{n\to\infty} b_n \geq 0$. By the limit laws, $\lim_{n\to\infty} a_n - \lim_{n\to\infty} b_n = \lim_{n\to\infty} (a_n - b_n)$, so it suffices to show that $\lim_{n\to\infty} (a_n - b_n) \geq 0$.

Thus our goal now is to consider the sequence $(a_n - b_n)_{n=m}^\infty$, and show that its limit is non-negative. To simplify the exposition, let us define $c_n := a_n - b_n$. Then since $a_n \geq b_n$ for each $n \geq m$, we have that $c_n = a_n - b_n \geq 0$ for each $n \geq m$.

Using our new notation of $c_n$, our goal is the following: we want to show that if $(c_n)_{n=m}^\infty$ is a sequence such that $c_n \geq 0$ for all $n\geq m$, then $\lim_{n\to\infty} c_n \geq 0$.

To show this we prove by contradiction. We suppose $L := \lim_{n\to\infty} c_n < 0$. Then by the definition of sequence convergence, for any $\varepsilon > 0$, there exists $N \geq m$ such that  $L - \varepsilon \leq c_n \leq L + \varepsilon$ for each $n \geq N$. But if we let $\varepsilon := - L / 2 > 0$, then we could find some $n$ such that $3L / 2 \leq c_n \leq L / 2 < 0$. But since $c_n \geq 0$ for all $n \geq m$, this is a contradiction. Thus we have $\lim_{n\to\infty} c_n \geq 0$.

# Announcing Tao Analysis Flashcards

Hello everyone, today I am announcing a sister-project to this blog that I have been working on for a while:

Tao Analysis Flashcards is a website which hosts question-and-answer flashcards on the content in Analysis I. Each set of flashcards is associated with a section from the book, and is meant to be completed after you finish reading the section. The idea is that instead of a “read the section” → “do the exercises” loop, we make it a “read the section” → “check understanding of reading by doing flashcards” → “do the exercises” loop. I’m hoping the extra step will do some combination of making you pay more attention to the reading, clarifying some points not raised in the reading, and checking your understanding so you feel more confident you understood each section.

Learning mathematics is hard. Even harder is to learn mathematics on your own, which I believe most readers of my blog are doing when they work through Analysis I. But even harder still is to learn mathematics and actually retain it over the long term. So many times I’ve thought I understood a topic, only to realize several months later that I couldn’t recall most of what I had learned! And that brings us to another aspect of these flashcards: they are spaced repetition flashcards, which means you will get email reminders to review the cards over time, allowing you to efficiently retain the knowledge even as months or years pass.

Please let me know in comments your thoughts, especially if a card seems confusing or too difficult.

# Exercise 3.1.11

## Exercise statement

Show that the axiom of replacement implies the axiom of specification.

None.

## How to think about the exercise

What does it mean for one axiom to imply another? In this case, both axioms are about constructing sets, so we just want to show that any set that we can construct using the axiom of specification can be constructed using the axiom of replacement instead. The axiom of specification allows us to construct sets of the form $\{x \in A : P(x) \text{ is true}\}$. So our goal is, given some set $A$ and some property (predicate) $P$, to construct the set $\{x \in A : P(x) \text{ is true}\}$ using the axiom of replacement.

To use the axiom of replacement, we must feed it a two-place property and a set. The set can just be $A$: we want to produce some subset of $A$, so it makes sense that we start with $A$ and do some “replacement” on its elements somehow. So that leaves us to determine what the two-place property will be. Let’s call that property $Q$, since the variable $P$ is already taken. Once we define what $Q$ is, the axiom of replacement allows us to construct the set $\{y : Q(x,y) \text{ is true for some }x \in A\}$.

How do we decide what $Q$ to use? Well, we want to keep only those elements $x$ of $A$ such that $P(x)$ is true. So it makes sense to require $P(x)$ as part of $Q(x,y)$. And the elements of this new set should be the same elements from $A$, so we don’t want to apply any transformation to get the $y$s. So we can just let $y = x$. In other words, we can define $Q(x,y)$ to be “$y=x$ and $P(x)$” (it’s fine to say “$y=x$ and $P(y)$” as well). Thus we have the set $\{y : y=x\text{ and }P(x)\text{ for some }x \in A\}$.

There is another way to look at this exercise, assuming you are comfortable with functions. The axiom of replacement basically says that if $A$ is a set and $f$ is an operation on elements of $A$, then $\{f(x) : x \in A\}$ is a set. Here the operation $f$ may return an undefined result (because for each $x$, the statement $P(x,y)$ is true for at most one $y$ rather than exactly one $y$). So to construct the set $\{x \in A : P(x) \text{ is true}\}$, we can define $f(x)$ to be $x$ if $P(x)$ is true, and leave $f(x)$ undefined if $P(x)$ is false.

If you feel uncomfortable about $f$ having undefined values, see Exercise 3.4.7, and also note that we can do everything with functions also: we split into cases depending on whether the resulting set will be empty. If $A$ is empty or $P(x)$ is false for all $x\in A$ then the resulting set will be empty so we don’t need to do anything to construct it. Otherwise, since $A$ is non-empty and $P(x)$ is true for at least one $x \in A$, we can pick some element $x_0 \in A$ for which $P(x_0)$ is true and let this element be the default output of $f$ for inputs we want to exclude. In other words, $f : A \to A$ is the function defined by:

$\displaystyle f(x) := \begin{cases}x & \text{if }P(x)\text{ is true} \\ x_0 & \text{otherwise}\end{cases}$

But the discussion involving $f$ is a bit informal, as we have not introduced functions at this point in the book. But nevertheless this way of looking at this problem provides good intuition.

## Model solution

Let $A$ be a set, and let $P(x)$ be a statement pertaining to objects $x \in A$. To show that the axiom of replacement implies the axiom of specification, we will construct the set $\{x \in A : P(x) \text{ is true}\}$ using just the axiom of replacement. Let $Q(x,y)$ be the statement “$y=x$ and $P(x)$”. To use the axiom of replacement, we must verify that for each $x \in A$, the statement $Q(x,y)$ is true for at most one $y$. But for each $x\in A$, there is exactly one $y$ such that $y=x$, so it follows that for the full statement of $Q(x,y)$ there is at most one $y$ satisfying the statement. The axiom of replacement thus allows us to construct the set $\{y : y=x\text{ and }P(x)\text{ for some }x \in A\}$. We claim that this is the same set as $\{x \in A : P(x) \text{ is true}\}$. We show the inclusion both ways:

• Suppose $z \in \{x \in A : P(x) \text{ is true}\}$. Thus $z \in A$ and $P(z)$ is true. But this means that $z=x$ and $P(x)$ for some $x \in A$; specifically, there is $z \in A$ such that $z=z$ and $P(z)$. Thus $z \in \{y : y=x\text{ and }P(x)\text{ for some }x \in A\}$.
• Suppose $z \in \{y : y=x\text{ and }P(x)\text{ for some }x \in A\}$. This means that for some $x \in A$, we have $z=x$ and $P(x)$. Since $z=x$ this means we have $P(z)$ and $z\in A$ as well. Thus $z \in \{x \in A : P(x) \text{ is true}\}$.

Since both directions of the inclusion hold, this means that the two sets are equal.

# Exercise 8.3.5

## Exercise statement

Show that no power set (i.e., a set of the form $2^X$ for some set $X$) can be countably infinite.

## Hints

1. You do not need the axiom of choice for this exercise (though of course if you have read Section 8.4 you may use it).

## How to think about the exercise

I think the proof below is pretty straightforward, and I don’t have too much to say beyond that.

## Model solution

We have three cases depending on the cardinality of $X$. If $X$ is finite, then by Exercise 8.3.1 the power set $2^X$ has finite cardinality, so we are done. If $X$ is countably infinite, then by Cantor’s theorem (Theorem 8.3.1) we see that $2^X$ cannot be countably infinite, so we are done. Thus it remains to show the result when $X$ is uncountable, so let $X$ be an uncountable set.

Let us introduce some notation. We write $|A| \leq |B|$ to mean that there is an injection from $A$ to $B$. The intuition for this notation comes from Exercise 8.3.3. The relation $\leq$ has the transitivity property that if $|A| \leq |B|$ and $|B| \leq |C|$, then $|A| \leq |C|$: if $f : A \to B$ is an injection and $g : B \to C$ is an injection, then $g \circ f : A \to C$ is an injection by Exercise 3.3.2. (The relation $\leq$ is anti-symmetric thanks to Exercise 8.3.3, and it is also reflexive because the identity map $\mathrm{id} : A \to A$ is injective, so it is a reflexive, anti-symmetric, and transitive relation, i.e. a partial order. Thus we are justified in using the suggestive notation $\leq$.)

We have $|X| \leq |2^X|$ because $f : X \to 2^X$ defined by $f(x) := \{x\}$ is an injection.

Now suppose for sake of contradiction that $2^X$ is countably infinite. Then there is a bijection between $2^X$ and $\mathbf N$, so in particular we have $|2^X| \leq |\mathbf N|$. We also showed above that $|X| \leq |2^X|$. So by transitivity of $\leq$, we have $|X| \leq |\mathbf N|$. Thus there is some injection $g : X \to \mathbf N$. Now consider the image $g(X)$, which is a subset of $\mathbf N$. By Corollary 8.1.6, $g(X)$ is at most countable. Define the function $h : X \to g(X)$ by $h(x) := g(x)$. This is a bijection: it is injective because $g$ is injective, and it is surjective because $g(X) = \{g(x) : x \in X\}$ is exactly the set of elements that $g$ maps to. The bijection $h$ shows that $X$ has equal cardinality to $g(X)$, which is at most countable. So $X$ is at most countable, which contradicts the assumption that $X$ is uncountable. This contradiction shows that $2^X$ cannot be countably infinite, which completes the proof.

# Exercise 10.1.1

## Exercise statement

Suppose that $X$ is a subset of $\mathbf R$, $x_0$ is a limit point of $X$, and $f : X \to \mathbf R$ is a function which is differentiable at $x_0$. Let $Y \subseteq X$ be such that $x_0 \in Y$, and $x_0$ is also a limit point of $Y$. Prove that the restricted function $f|_Y : Y \to \mathbf R$ is also differentiable at $x_0$, and has the same derivative as $f$ at $x_0$. Explain why this does not contradict the discussion in Remark 10.1.2.

## Hints

1. Use Definition 9.3.6.

## How to think about the exercise

This is a simple exercise and is a matter of putting together the right definitions.

## Model solution

We want to show that

$\displaystyle \lim_{y \to x_0; y \in Y\setminus\{x_0\}} \frac{f|_Y(y) - f|_Y(x_0)}{y-x_0} = f'(x_0)$

To do this, we will return to the definition of a limit, Definition 9.3.6. To show the limit exists, we must first verify that $x_0$ is an adherent point of $Y\setminus\{x_0\}$. But this is the case since $x_0$ is a limit point of $Y$. Now  let $\varepsilon > 0$. We want to find some $\delta > 0$ such that for all $y \in Y\setminus\{x_0\}$, if $|y-x_0| < \delta$ then $\left|\frac{f|_Y(y) - f|_Y(x_0)}{y-x_0} - f'(x_0)\right| \leq \varepsilon$.

How can we find such a $\delta$? The only information we are given from which we could find a $\delta$ is the fact that $f$ is differentiable at $x_0$. Since $f$ is differentiable at $x_0$, we know that for our $\varepsilon > 0$ in particular, there exists some $\delta > 0$ such that for all $x \in X \setminus \{x_0\}$, if $|x-x_0| < \delta$ then $\left|\frac{f(x) - f(x_0)}{x-x_0} - f'(x_0)\right| \leq \varepsilon$.

So let’s use this $\delta > 0$. Now that we have a $\delta$, we must show that all $y \in Y\setminus\{x_0\}$, if $|y-x_0| < \delta$ then $\left|\frac{f|_Y(y) - f|_Y(x_0)}{y-x_0} - f'(x_0)\right| \leq \varepsilon$. So let $y \in Y\setminus\{x_0\}$, and suppose $|y-x_0| < \delta$. We must show that $\left|\frac{f|_Y(y) - f|_Y(x_0)}{y-x_0} - f'(x_0)\right| \leq \varepsilon$.

Now $Y \subseteq X$, so this means $Y \setminus \{x_0\} \subseteq X \setminus \{x_0\}$. Thus we have $y \in X\setminus \{x_0\}$.

We know from the differentiability condition for $f$ at $x_0$ that for all $x \in X \setminus \{x_0\}$, if $|x-x_0| < \delta$ then $\left|\frac{f(x) - f(x_0)}{x-x_0} - f'(x_0)\right| \leq \varepsilon$. Since our $y$ satisfies these conditions, we have $\left|\frac{f(y) - f(x_0)}{y-x_0} - f'(x_0)\right| \leq \varepsilon$.

To complete the proof, recall how $f|_Y$ is defined. If $y' \in Y$, then $f|_Y(y') := f(y')$. Since $y,x_0 \in Y$, we have $f|_Y(y) = f(y)$ and $f|_Y(x_0) = f(x_0)$. Thus we have $\left|\frac{f|_Y(y) - f|_Y(x_0)}{y-x_0} - f'(x_0)\right|=\left|\frac{f(y) - f(x_0)}{y-x_0} - f'(x_0)\right| \leq \varepsilon$.

This does not contradict the discussion in Remark 10.1.2 because in the example there, $3$ was not an adherent point of $[1,2]$, so the limit was undefined. In contrast for this exercise we assumed that $x_0$ was an adherent point of $Y \setminus \{x_0\}$ (i.e. a limit point of $Y$). And so if we used the example in Remark 10.1.2, the proof above would fail at the point where we tried to verify that $x_0$ is an adherent point of $Y\setminus\{x_0\}$.

The important point is that if $x_0$ were not a limit point of $Y$, then we could always pick $\delta > 0$ small enough so that the expression $\frac{f|_Y(y) - f|_Y(x_0)}{y-x_0}$ is undefined when $y$ is further restricted to the set $\{y \in Y \setminus \{x_0\} : |y - x_0| < \delta\}$. This would mean that the limit is always defined no matter what $L$ we use (since the implication in the definition of limit would be vacuous), so that in effect the derivative would equal any number possible. This would make the notation $f|_Y'(x_0)$ ambiguous, and this concept is useless anyway, which is why we choose to not define the limit in this case.

# Exercise 11.1.1

## Exercise statement

Prove Lemma 11.1.4.

Lemma 11.1.4. Let $X$ be a subset of the real line. Then the following two statements are logically equivalent:

(a) $X$ is bounded and connected.
(b) $X$ is a bounded interval.

## Hints

1. In order to show that (a) implies (b) in the case when $X$ is non-empty, consider the supremum and infimum of $X$.

## How to think about the exercise

This exercise is pretty straightforward, but one must be careful to stick to the definitions instead of using one’s intuitive notion of intervals; the whole point of the exercise is to make sure our formalization of ideas like “bounded” and “connected” and “interval” is correct. An example of what I mean: it seems like Tao defines “bounded interval” and then later on defines “bounded set”. Even though “bounded interval” contains the word “bounded”, the book doesn’t seem to show that bounded intervals are indeed bounded in the sense of bounded set. So part of the point of this exercise is to demonstrate this, and to see that nothing unexpected has happened.

## Model solution

We first show that (b) implies (a). Suppose that $X$ is a bounded interval (see Examples 9.1.3 for definition). Thus $X$ is of the form $(a,b)$, $[a,b]$, $(a,b]$, or $[a,b)$ for real numbers $a,b \in \mathbf R$. We will just do one of the cases, namely the case $X=[a,b)$, as the proof in the other cases is very similar. We first show that $X$ is bounded. We claim that $M := \max(|a|, |b|) + 1$ is a bound (the $+1$ is a technicality, since Definition 9.1.22 requires $M > 0$ for some odd reason). Indeed, if $x \in X$ then we have $a \leq x < b$ by definition of the interval notation. Thus we have

$-M < -\max(|a|, |b|) \leq -|a| \leq a \leq x < b \leq |b| \leq \max(|a|, |b|) < M$

Thus we have $x \in [-M,M]$. Since $x \in X$ was arbitrary, this shows that $X \subseteq [-M, M]$ as required, so $X$ is bounded.

Next we show that $X$ is connected. Let $x,y$ be elements of $X$ such that $x < y$. We must show that $[x,y]$ is a subset of $X$. Let $z$ be a number such that $x \leq z \leq y$. We must show that $z \in X$. But since $x \in X$ we have $a \leq x$, and since $y \in X$ we have $y < b$. Thus by transitivity of inequalities we have $a \leq x \leq z \leq y < b$, so $z \in [a, b) = X$. This proves that $X$ is connected.

Now we show that (a) implies (b). Suppose $X$ is bounded and connected. We have two cases. Suppose first that $X$ is empty. Then $X$ is equal to an empty bounded interval such as $(1,1)$.

Now suppose $X$ is non-empty. Then define $a := \inf(X)$ and $b := \sup(X)$. Since $X$ is a bounded and non-empty set, by Theorem 5.5.9 both $a$ and $b$ are real numbers. We have four cases depending on whether $a \in X$ and $b \in X$. Since the proof is similar in each case, we will just show the case when $a \in X$ and $b \notin X$. In this case, we will show that $X$ equals the bounded interval $[a, b)$. To do this, we will show that $[a,b) \subseteq X$ and $X \subseteq [a,b)$. We first show that $[a,b) \subseteq X$. Let $x \in [a,b)$. Since $x < b$ and $b$ is the least upper bound for $X$, there exists some $y \in X$ such that $x < y$ (otherwise $x$ would be a smaller upper bound for $X$). Now we have $a,y \in X$ such that $a \leq x < y$; since $X$ is connected, this means that $x \in X$ as desired.

Now we show that $X \subseteq [a, b)$. Let $x \in X$. Since $a$ is the infimum of $X$ and $b$ is the supremum of $X$, we know that $a \leq x \leq b$. Thus to show that $x \in [a,b)$ we just need to show that $x \ne b$. But this is easy, since we assumed that $b \notin X$.

# Exercise 6.5.2

## Exercise statement

Prove Lemma 6.5.2.

Lemma 6.5.2. Let $x$ be a real number. Then the limit $\lim_{n\to\infty} x^n$ exists and is equal to zero when $|x| < 1$, exists and is equal to $1$ when $x=1$, and diverges when $x=-1$ or when $|x| > 1$.

## Hints

1. Use Proposition 6.3.10, Exercise 6.3.4, and the squeeze test.

## How to think about the exercise

This is a straightforward exercise, but it requires some care in two respects:

• It can be a little notationally confusing dealing with all of the absolute value signs so it is easy to think one has proved something when there is in fact a slight flaw in the proof.
• If one wants to write up the proof in the shortest way possible, thinking of which cases to use can be tricky.

## Model solution

First suppose $0 < |x| < 1$. Since we have $-|x|^n = -|x^n| \leq x^n \leq |x^n| = |x|^n$ for each $n$, we can use the squeeze test: by Proposition 6.3.10 we know that $\lim_{n\to\infty} |x|^n = 0$, so by the limit laws we have $\lim_{n\to\infty} -|x|^n = 0$ as well. This means that the sequence $(x^n)_{n=1}^\infty$ must also converge to zero.

Next suppose $x=1$. Then we have $x^n = 1^n = 1$ for all $n$, so $(x^n)_{n=1}^\infty$ is the constant sequence, which converges to $1$. A similar proof can be given when $x=0$; in this case $(x^n)_{n=1}^\infty$ is constantly zero, so converges to zero.

If $x=-1$, the limit $\lim_{n\to\infty} (-1)^n$ does not exist as the sequence $((-1)^n)_{n=1}^\infty = (-1,1,-1,1,-1,\ldots)$ oscillates between $-1$ and $1$. To prove that $\lim_{n\to\infty} (-1)^n$ does not exist, let $\varepsilon := 1$. Then no matter how big $N \geq 1$ is, we can pick $j := N$ and $k:=N+1$. We have $|(-1)^j - (-1)^k| = 2 > \varepsilon$. Thus the sequence is not Cauchy, so by Theorem 6.4.18 it is not convergent.

Finally suppose $|x| > 1$. Suppose for sake of contradiction that $(x^n)_{n=1}^\infty$ converges to some limit $L \in \mathbf R$. Then by the limit laws, $\lim_{n\to\infty} |x^n| = \lim_{n\to\infty} \max(x^n, -x^n) = \max(L,-L) = |L|$. But $|x^n| = |x|^n$, so this means that $(|x|^n)_{n=1}^\infty$ converges to $|L|$. This contradicts Exercise 6.3.4.