Category Archives: Solutions

Exercise 6.2.2

June 27, 2020 Issa Rice 3 Comments

Exercise statement

Prove Theorem 6.2.11.

Theorem 6.2.11. Let $E$ be a subset of $\mathbf R^*$ . Then the following statements are true.

(a) For every $x \in E$ we have $x \leq \sup(E)$ and $x \geq \inf(E)$ .
(b) Suppose that $M \in \mathbf R^*$ is an upper bound for $E$ , i.e., $x \leq M$ for all $x \in E$ . Then we have $\sup(E) \leq M$ .
(c) Suppose that $M \in \mathbf R^*$ is a lower bound for $E$ , i.e., $x \geq M$ for all $x \in E$ . Then we have $\inf(E) \geq M$ .

Hints

You may need to break into cases depending on whether $+\infty$ or $-\infty$ belongs to $E$ .
You can of course use Definition 5.5.10, provided that $E$ consists only of real numbers.
When proving the parts about the infimum, you don’t need to split into cases.

How to think about the exercise

The geometric picture, in terms of the real number line with special points at infinity, should feel intuitive to you. The point of this exercise is just to verify that our formal definition really does work the way we intuitively expect.

This exercise is a little tricky if you want to do the least amount of work. (Doing the exercise by splitting everything into cases is fine, but that’s no fun.)

Model solution

(a) We first show that $x \leq \sup(E)$ for all $x \in E$ . Let $x \in E$ . We have three cases:

If $E$ is contained in $\mathbf R$ , then $x$ is a real number, and by Definition 5.5.10 we have $x \leq \sup(E)$ : if $E$ is empty, then the result is vacuous; if $E$ is non-empty and bounded above, then the result follows because $\sup(E)$ is the least upper bound; and if $E$ is non-empty and not bounded above, then $\sup(E) = +\infty$ so the result follows by Definition 6.2.3(b).
If $E$ contains $+\infty$ , then $x \leq +\infty = \sup(E)$ by Definition 6.2.3(b) and Definition 6.2.6(b).
If $E$ does not contain $+\infty$ but does contain $-\infty$ , then we have two cases. If $x$ is real, then $x \in E \setminus \{-\infty\}$ so $x \leq \sup(E \setminus \{-\infty\}) = \sup(E)$ by Definition 5.5.10 and Definition 6.2.6(c). On the other hand, if $x = -\infty$ then $x \leq \sup(E)$ by Definition 6.2.3(c); the value of $x$ is so small that we don’t even care what $\sup(E)$ is.

Next we show that $x \geq \inf(E)$ for all $x \in E$ . Let $x \in E$ . Then $-x \in -E$ so by what we just showed, we have $-x \leq \sup(-E)$ . Thus by Proposition 6.2.5(d) we have $x \geq -\sup(-E) = \inf(E)$ as required.

(b) We have three cases:

If $E$ is contained in $\mathbf R$ , then the result follows by Definition 5.5.10: if $E$ is empty, then $\sup(E) = -\infty \leq M$ ; if $E$ is non-empty and is bounded above, then $\sup(E)$ is the least upper bound while $M$ is an upper bound, so $\sup(E) \leq M$ ; if $E$ is non-empty and has no real upper bound, then $M$ must be $+\infty$ (otherwise we could find a real number in $E$ that is larger than $M$ ), so $\sup(E) \leq +\infty = M$ .
If $E$ contains $+\infty$ , then we must have $+\infty \leq M$ since $M$ is an upper bound for $E$ . Thus we have $\sup(E) = +\infty \leq M$ as required.
If $E$ does not contain $+\infty$ but does contain $-\infty$ , then $\sup(E) = \sup(E \setminus \{-\infty\})$ . We also have $x \leq M$ for all $x \in E \setminus \{-\infty\}$ , since $E \setminus \{-\infty\}$ is a subset of $E$ . Thus by the first case we have $\sup(E \setminus \{-\infty\}) \leq M$ , from which the result follows.

(c) Let $y \in -E$ . Then $y=-x$ for some $x \in E$ . Since $x \in E$ and $M$ is a lower bound for $E$ , we have $x \geq M$ , which means $y=-x \leq -M$ . Since $y \in -E$ was arbitrary, this means that $-M$ is an upper bound for $-E$ . By part (b), we thus have $\sup(-E) \leq -M$ , which means $\inf(E) = -\sup(-E) \geq M$ as desired.

Solutions

Exercise 6.3.1

June 27, 2020 Issa Rice Leave a comment

Exercise statement

Verify the claim in Example 6.3.4.

Let $a_n := 1/n$ ; thus $(a_n)_{n=1}^\infty$ is the sequence $1, 1/2, 1/3, \ldots$ . Then $\sup(a_n)_{n=1}^\infty = 1$ and $\inf(a_n)_{n=1}^\infty = 0$ .

Hints

You might want to use Exercise 5.4.4.

How to think about the exercise

This is a straightforward exercise so I don’t have anything to say. I’ll just leave this picture:

Model solution

First we show that $1$ is the supremum of the sequence. Let $1/n$ be an element of the sequence. Then $n \geq 1$ so $1/n \leq 1$ , which shows that $1$ is an upper bound for the sequence. Let $M$ be any upper bound for the sequence, so that $1/n \leq M$ for all $n \geq 1$ . Then in particular for $n=1$ we have $1/1 \leq M$ as required. Thus $1$ is the least upper bound (supremum) as required.

Next we show that $0$ is the infimum of the sequence. Each $n \geq 1$ is positive, so by Definition 4.2.6 we see that $1/n$ is positive, i.e. $1/n > 0$ . Thus $0$ is a lower bound for the sequence. Let $L$ be any lower bound for the sequence, so that $1/n \geq L$ for all $n \geq 1$ . We want to show that $L \leq 0$ . Suppose for sake of contradiction that $L > 0$ . Then by Exercise 5.4.4 there exists a positive integer $N \geq 1$ such that $L > 1/N > 0$ . But $1/N$ is an element of the sequence, so this contradicts the fact that $L$ is a lower bound for the sequence. Hence we must have $L \leq 0$ , which shows that $0$ is the greatest lower bound (infimum) as required.

Solutions

Exercise 9.7.2

June 20, 2020 Issa Rice 2 Comments

Exercise statement

Let $f : [0,1] \to [0,1]$ be a continuous function. Show that there exists a real number $x$ in $[0,1]$ such that $f(x) = x$ . This point $x$ is known as a fixed point of $f$ , and this result is a basic example of a fixed point theorem, which play an important rôle in certain types of analysis.

Hints

Apply the intermediate value theorem to the function $f(x) - x$ .

How to think about the exercise

This result just says that if a function starts from the left end of the square and ends up on the right end of the square, then it must intersect the diagonal at some point.

Model solution

Define the function $g : [0,1] \to \mathbf R$ by $g(x) := f(x) - x$ . Then $g(0) = f(0) \in [0,1]$ and $g(1) = f(1)-1$ . Since $0\leq f(1) \leq 1$ we have $-1 \leq f(1) - 1 \leq 0$ , thus $g(1) \in [-1, 0]$ . Thus we have $g(1) \leq 0 \leq g(0)$ . We also know that $g$ is continuous because $f$ is continuous by assumption, the identity function $x \mapsto x$ is continuous by Example 9.4.3, and by Proposition 9.4.9. Hence we can apply the intermediate value theorem to find an $x \in [0,1]$ such that $g(x) = 0$ . For this value of $x$ , we have $f(x) - x = g(x) = 0$ , i.e. $f(x)=x$ as desired.

Solutions

Exercise 3.4.7

June 19, 2020 Issa Rice 12 Comments

Exercise statement

Let $X, Y$ be sets. Define a partial function from $X$ to $Y$ to be any function $f : X' \to Y'$ whose domain $X'$ is a subset of $X$ , and whose range $Y'$ is a subset of $Y$ . Show that the collection of all partial functions from $X$ to $Y$ is itself a set.

Hints

Use Exercise 3.4.6, the power set axiom, the replacement axiom, and the union axiom.

How to think about the exercise

If $X' \subseteq X$ and $Y' \subseteq Y$ , then we can form the set $(Y')^{X'}$ using the power set axiom; this gives us all of the partial functions with domain $X'$ and range $Y'$ . Now we just want to “loop over” all combinations of $X', Y'$ , and take the union to “flatten” the result. In other words, we want the set

$\displaystyle \bigcup\{ (Y')^{X'} : X' \subseteq X\text{ and }Y'\subseteq Y\}$

But we are not yet done, because we must justify all of the steps using the axioms and results we have so far.

First of all, to use the replacement axiom, we need the “looping over” construct to use the “is an element” relation rather than the “is a subset” relation, i.e. to be in the form $\{f(x) : x \in A\}$ rather than $\{f(x) : x \subseteq A\}$ as above. This is easy to fix: by Lemma 3.4.9, the sets $2^X$ and $2^Y$ exist, so the set we want is

$\displaystyle \bigcup\{ (Y')^{X'} : X' \in 2^X\text{ and }Y'\in 2^Y\}$

Now we run into the problem that the replacement axiom only allows us to “loop over” a single set, so we can’t be looping over the sets $2^X$ and $2^Y$ simultaneously. To turn this double loop into a single loop, we can use the notion of ordered pairs and the Cartesian product; but it turns out that in this book, these ideas are only introduced in section 3.5, the next section! If we cheat a little and use these ideas, then the set $2^X \times 2^Y = \{(X', Y') : X' \in 2^X\text{ and }Y' \in 2^Y\}$ exists. Now we can use the replacement axiom to replace each ordered pair $(X', Y')$ by the set $(Y')^{X'}$ . In other words, we have the set

$\displaystyle \bigcup\{ (Y')^{X'} : (X', Y') \in 2^X \times 2^Y\}$

I consider this an entirely acceptable solution to this exercise: it is the natural, obvious thing one comes up with. Alternatively, if this solution isn’t acceptable, then I consider this exercise to be pretty unfair! With that complaint out of the way, let’s see if we can find a different solution that does not require Cartesian products.

So, we can only loop over one set at a time, and we aren’t allowed to take the Cartesian product to compress the double loop into a single loop. What to do? If you are familiar with computer programming, you might at this point have an idea.

In Python, given a list X = [1,2,3] and another list Y = [4,5], how can we print all of the ordered pairs (x, y) where x is in X and y is in Y? One idea is to use the Cartesian product functionality that is provided by the language:

from itertools import product
for p in product(X, Y):
    print(p)
# prints the following:
# (1, 4)
# (1, 5)
# (2, 4)
# (2, 5)
# (3, 4)
# (3, 5)

But more obvious idea is to just use a nested loop:

for x in X:
    for y in Y:
        print((x, y))
# prints the following:
# (1, 4)
# (1, 5)
# (2, 4)
# (2, 5)
# (3, 4)
# (3, 5)

(Aside for people who know Haskell: You can think of [(x,y) | x <- [1,2,3], y <- [4,5]] versus [[(x,y) | y <- [4,5]] | x <- [1,2,3]]; the latter must be flattened using concat, analogously to how we must apply union twice below. Consider also currying, e.g. the difference between add :: (Int, Int) -> Int; add (x,y) = x+y and add' :: Int -> (Int -> Int); add' = \x -> (\y -> x+y). The former eats both arguments at once while the latter eats one argument, spitting out a function which can eat an argument. This gives us a way to define functions which can essentially take multiple arguments, without actually taking multiple arguments, analogously to how here we want to simulate taking from multiple sets without actually taking from multiple sets at once.)

The benefit of the nested loop, for our purposes, is that we are only looping over a single list or set at a time, so the axiom of replacement can be applied. How will this work? First, fix a set $X' \subseteq X$ . Then we can form the set $\{(Y')^{X'} : Y' \in 2^Y\}$ using the replacement axiom. This gives us all of the partial functions with domain $X'$ . Now we just need to loop over all of the possible domains, by forming the set $\{\{(Y')^{X'} : Y' \in 2^Y\} : X' \in 2^X\}$ . But since we formed these sets in stages, we must now take the union twice (instead of once, as we did in our first solution above) to “flatten” this set, so our final answer is $\bigcup\bigcup\{\{(Y')^{X'} : Y' \in 2^Y\} : X' \in 2^X\}$ .

Let’s take an example to make sure this actually works. Let $X = \{1\}$ and $Y = \{2,3\}$ . Then we have $2^X = \{\emptyset, \{1\}\}$ and $2^Y = \{\emptyset, \{2\}, \{3\}, \{2,3\}\}$ . The partial functions from $X$ to $Y$ are the following:

$f_1$ : Domain $\emptyset$ and range $\emptyset$ , which is an empty function.
$f_2$ : Domain $\emptyset$ and range $\{2\}$ , which is an empty function.
$f_3$ : Domain $\emptyset$ and range $\{3\}$ , which is an empty function.
$f_4$ : Domain $\emptyset$ and range $\{2,3\}$ , which is an empty function.
$f_5$ : Domain $\{1\}$ and range $\{2\}$ , which maps $1 \mapsto 2$ .
$f_6$ : Domain $\{1\}$ and range $\{3\}$ , which maps $1 \mapsto 3$ .
$f_7$ : Domain $\{1\}$ and range $\{2,3\}$ , which maps $1 \mapsto 2$ .
$f_8$ : Domain $\{1\}$ and range $\{2,3\}$ , which maps $1 \mapsto 3$ .

Let’s first check the sets $\{(Y')^{X'} : Y' \in 2^Y\}$ for a fixed $X'$ . The subsets of $X$ are $\emptyset$ and $\{1\}$ so we have

$\begin{aligned}\{(Y')^{\emptyset} : Y' \in 2^Y\} &= \{\emptyset^\emptyset, \{2\}^\emptyset, \{3\}^\emptyset, \{2,3\}^\emptyset\} \\ &= \{\{f_1\}, \{f_2\}, \{f_3\}, \{f_4\}\}\end{aligned}$

and

$\begin{aligned}\{(Y')^{\{1\}} : Y' \in 2^Y\} &= \{\emptyset^{\{1\}}, \{2\}^{\{1\}}, \{3\}^{\{1\}}, \{2,3\}^{\{1\}}\} \\ &= \{\emptyset, \{f_5\}, \{f_6\}, \{f_7, f_8\}\}\end{aligned}$

Now, the set $\{\{(Y')^{X'} : Y' \in 2^Y\} : X' \in 2^X\}$ is equal to $\{\{(Y')^{\emptyset} : Y' \in 2^Y\}, \{(Y')^{\{1\}} : Y' \in 2^Y\}\}$ , which by the above computation is just $\{\{\{f_1\}, \{f_2\}, \{f_3\}, \{f_4\}\}, \{\emptyset, \{f_5\}, \{f_6\}, \{f_7, f_8\}\}\}$ . Taking the union once gives us $\{\{f_1\}, \{f_2\}, \{f_3\}, \{f_4\}, \emptyset, \{f_5\}, \{f_6\}, \{f_7, f_8\}\}$ , and taking the union again gives us $\{f_1,f_2,f_3,f_4,f_5,f_6,f_7, f_8\}$ , which is precisely what we wanted.

You’ve probably noticed that we could have taken the union at an intermediate stage: $\bigcup\{(Y')^{\emptyset} : Y' \in 2^Y\} = \{f_1,f_2,f_3,f_4\}$ and $\bigcup \{(Y')^{\{1\}} : Y' \in 2^Y\} = \{f_5,f_6,f_7, f_8\}$ . So we can form the set $\left\{ \bigcup\{(Y')^{X'} : Y' \in 2^Y\} : X' \in 2^X\right\}$ , which equals $\{\{f_1,f_2,f_3,f_4\},\{f_5,f_6,f_7, f_8\}\}$ ; taking the union again then gives us the same answer. In the solution below we will use this latter expression.

This is one of those exercises where it can be difficult to tell when one is done (alternatively, the difficulty depends a lot on where one decides one is “off the hook”). I can easily imagine people skipping the proof that the resulting set is actually the set of all partial functions, for example.

Model solution

By Lemma 3.4.9, the sets $2^X$ and $2^Y$ exist. Fix some subset $X'$ of $X$ . Then the set $\{(Y')^{X'} : Y' \in 2^Y\}$ exists by the power set axiom and replacement axiom. (Formally, we can proceed as follows. Let $P(a,b)$ be the predicate $b = a^{X'}$ , pertaining to sets $a,b$ . If $a$ is a set, then $a^{X'}$ exists by the power set axiom. Thus for each $a$ there is exactly one (hence at most one) $b$ such that $P(a,b)$ . Thus by the replacement axiom the set $\{b : b = a^{X'}\text{ is true for some }a \in 2^Y\}$ exists.)

By the union axiom, the set $\bigcup \{(Y')^{X'} : Y' \in 2^Y\}$ exists. By the replacement axiom again, the set $\left\{\bigcup \{(Y')^{X'} : Y' \in 2^Y\} : X' \in 2^X\right\}$ exists. (Formally, we can define the predicate $Q(a,b)$ by $b = \bigcup \{(Y')^{a} : Y' \in 2^Y\}$ so that the set $\{b : b = \bigcup \{(Y')^{a} : Y' \in 2^Y\}\text{ is true for some }a \in 2^X\}$ exists. We are applying the replacement axiom to the set $2^X$ .)

By the union axiom again, the set $\bigcup \left\{\bigcup \{(Y')^{X'} : Y' \in 2^Y\} : X' \in 2^X\right\}$ exists. It remains to show that this set is the set of all partial functions from $X$ to $Y$ . Let $f$ be an element of this set. Then by the union axiom, this means $f \in S$ for some $S \in \left\{\bigcup \{(Y')^{X'} : Y' \in 2^Y\} : X' \in 2^X\right\}$ . By the replacement axiom, $S = \bigcup \{(Y')^{X'} : Y' \in 2^Y\}$ for some $X' \subseteq X$ . Thus $f \in \bigcup \{(Y')^{X'} : Y' \in 2^Y\}$ for some $X' \subseteq X$ . By the union axiom, this means $f \in S'$ for some $S' \in \{(Y')^{X'} : Y' \in 2^Y\}$ . By the replacement axiom, $S' = (Y')^{X'}$ for some $Y' \subseteq Y$ . Thus $f \in (Y')^{X'}$ for some $Y' \subseteq Y$ and $X' \subseteq X$ . This means $f$ is a function from $X'$ to $Y'$ , which means it is a partial function from $X$ to $Y$ . This shows that every element of $\bigcup \left\{\bigcup \{(Y')^{X'} : Y' \in 2^Y\} : X' \in 2^X\right\}$ is a partial function from $X$ to $Y$ .

Conversely, we now show that every partial function from $X$ to $Y$ is in the set $\bigcup \left\{\bigcup \{(Y')^{X'} : Y' \in 2^Y\} : X' \in 2^X\right\}$ . Let $f : X'' \to Y''$ be a function, where $X'' \subseteq X$ and $Y'' \subseteq Y$ . Then $f \in (Y'')^{X''}$ . Thus $f \in (Y')^{X''}$ for some $Y' \in 2^Y$ , since $Y'' \in 2^Y$ . If we define $S' := (Y'')^{X''}$ , then $S' \in \{(Y')^{X''} : Y' \in 2^Y\}$ . Thus we have $f \in S'$ for some $S' \in \{(Y')^{X''} : Y' \in 2^Y\}$ , which means that $f \in \bigcup\{(Y')^{X''} : Y' \in 2^Y\}$ . Since $X'' \in 2^X$ , we thus see that $f \in \bigcup\{(Y')^{X'} : Y' \in 2^Y\}$ for some $X' \in 2^X$ . If we define $S := \bigcup \{(Y')^{X''} : Y' \in 2^Y\}$ , then $S \in \left\{\bigcup \{(Y')^{X'} : Y' \in 2^Y\} : X' \in 2^X\right\}$ . Thus we have $f \in S$ for some $S \in \left\{\bigcup \{(Y')^{X'} : Y' \in 2^Y\} : X' \in 2^X\right\}$ , which means that $f \in \bigcup \left\{\bigcup \{(Y')^{X'} : Y' \in 2^Y\} : X' \in 2^X\right\}$ . This is what we wanted to show, so we are done.

Solutions

Exercise 6.2.1

June 15, 2020 Issa Rice 1 Comment

Exercise statement

Prove Proposition 6.2.5.

Proposition 6.2.5. Let $x, y, z$ be extended real numbers. Then the following statements are true:

(a) (Reflexivity) We have $x \leq x$ .
(b) (Trichotomy) Exactly one of the statements $x < y$ , $x=y$ , or $x > y$ is true.
(c) (Transitivity) If $x \leq y$ and $y \leq z$ , then $x \leq z$ .
(d) (Negation reverses order) If $x \leq y$ , then $-y \leq -x$ .

Hints

You may need Proposition 5.4.7.

How to think about the exercise

This is one of those exercises where you just keep splitting into a bunch of cases. Naively, each variable has the real case, the $+\infty$ case, and the $-\infty$ case, so if a statement makes use of one variable that’s three cases; if a statement makes use of two variables that’s $3^2 = 9$ cases; and if a statement makes use of three variables that’s $3^3 = 27$ cases. Can we do better?

It turns out that yes, we can, sort of. Instead of splitting into 27 cases all at the beginning, we can pick one of the variables and split into three cases. In each branch, we might need to split into three more cases again, but sometimes we can get away with fewer cases because the assumption we made on the first variable simplifies the situtation. You can see this dynamic in the solution below for part (c), where even though we have three variables, we actually only have 5 cases instead of 27.

Another trick, which we use in part (d), is to split not on the value of the variables, but rather based on the cases given in Definition 6.2.3. Thus in part (d) we have only 3 cases instead of 9.

In the solution below, I tried to show some variety in how one can split into cases (e.g. part (b) does the naive split into 9 cases, which is horrible but straightforward).

For part (c), the transitivity of order given here uses non-strict inequality, but the transitivity in Proposition 4.2.9 uses strict inequality. So actually we have to first derive the non-strict version of transitivity from the strict version. This is slightly annoying but not difficult. Suppose $x \leq y$ and $y \leq z$ ; we want to show $x \leq z$ . If $x \ne y$ and $y\ne z$ , then we have $x < y$ and $y < z$ so by the strict version of transitivity we have $x < z$ , which means $x \leq z$ as required. If $x = y$ and $y=z$ , then $x=z$ by transitivity of equality, so $x \leq z$ as required. If $x = y$ and $y\ne z$ , then we have $x=y \leq z$ as required. Finally, if $x \ne y$ and $y = z$ , then we have $x \leq y = z$ as required. In all cases we have shown that $x \leq z$ .

Model solution

Proposition 5.4.7 allows us to cite the properties listed in Proposition 4.2.9.

(a) We have three cases. If $x$ is a real number, then $x=x$ so $x \leq x$ by Definition 5.4.6. If $x$ is equal to $+\infty$ , then $x \leq x$ by Definition 6.2.3(b). If $x$ is equal to $-\infty$ , then $x \leq x$ by Definition 6.2.3(c).

(b) We have several cases:

$x$ is real, $y$ is real: Exactly one of the statements is true by Proposition 4.2.9(a).
$x$ is real, $y=+\infty$ : We have $x \leq y$ by Definition 6.2.3(b). Also $x \ne y$ since $+\infty$ is distinct from every real number. Thus we have $x < y$ , which shows that at least one of the three statements is true. We already know $x \ne y$ , so we just need to show that $x > y$ is false. Suppose for sake of contradiction that $x > y$ . This means $y < x$ so in particular $y \leq x$ . But this fits none of the cases listed in Definition 6.2.3 ( $y$ is not real, so case (a) is false; the right hand side object is not $+\infty$ , so case (b) is false; the left hand side object is not $-\infty$ , so case (c) is false), so this is a contradiction.
$x$ is real, $y=-\infty$ : We have $y \leq x$ by Definition 6.2.3(c). Also $x \ne y$ since $-\infty$ is distinct from every real number. Thus $y < x$ , i.e. $x > y$ . We already know $x \ne y$ , so we just need to show that $x < y$ is false. Suppose for sake of contradiction that $x < y$ . This means in particular that $x \leq y$ . But this fits none of the cases listed in Definition 6.2.3, so this is a contradiction.
$x=+\infty$ , $y$ is real: We have $y \leq x$ by Definition 6.2.3(b). Since $x\ne y$ , this means $y < x$ , i.e. $x > y$ . We already have $x \ne y$ so we just need to show $x < y$ is false. But if $x <y$ is true that would imply $x \leq y$ , and this can’t be true since it fits none of the cases listed in Definition 6.2.3. Thus $x < y$ is false.
$x=+\infty$ , $y=+\infty$ : We have $x=y$ so at least one of the statements is true. We just need to show that $x < y$ and $x > y$ are both false. If $x < y$ , then we would have $x \ne y$ , a contradiction. Similarly $x > y$ implies $x \ne y$ , a contradiction. Thus at most one of the statements is true.
$x=+\infty$ , $y=-\infty$ : We have $x > y$ since $x \geq y$ and $x \ne y$ . We can’t have $x < y$ since this would imply $x \leq y$ , which fits none of the cases in Definition 6.2.3.
$x = -\infty$ , $y$ is real: We have $x < y$ since $x \leq y$ and $x \ne y$ . We can’t have $x > y$ since this would imply $x \geq y$ , which fits none of the cases in Definition 6.2.3.
$x=-\infty$ , $y=+\infty$ : We have $x < y$ since $x \leq y$ and $x \ne y$ . We can’t have $x > y$ since this implies $x \geq y$ , which fits none of the cases in Definition 6.2.3.
$x=-\infty$ , $y=-\infty$ : We have $x=y$ so at least one of the statements is true. We just need to show that $x < y$ and $x > y$ are both false. If $x < y$ , then we would have $x \ne y$ , a contradiction. Similarly $x > y$ implies $x \ne y$ , a contradiction. Thus at most one of the statements is true.

(c) Suppose $x \leq y$ and $y \leq z$ . We must show that $x \leq z$ . We split into cases depending on the value of $z$ :

If $z = +\infty$ , then $x \leq z$ by Definition 6.2.3(b) so we are done. (Remember, to show the implication $p \implies q$ , it suffices to show that $q$ is true.)
If $z = -\infty$ then since $y \leq z$ we must have $y = -\infty$ . Also since $x \leq y$ we must have $x = -\infty$ . Thus we have $x \leq z$ as required.
If is real, then since we know that either or is real. Thus we have two cases:
- If $y=-\infty$ then since $x \leq y$ we must have $x=-\infty$ , which means $x \leq z$ as required.
- If $y$ is real, then $x \leq y$ so either $x = -\infty$ or $x$ is real. In the former case, we have $x \leq z$ as required. In the latter case, all three extended real numbers $x,y,z$ are real, so we have $x \leq z$ by transitivity of order for real numbers.

(d) Suppose $x \leq y$ . We want to show that $-y \leq -x$ . By Definition 6.2.3 we have three cases.

If $x$ and $y$ are real, then we can add $-x-y$ to both sides to obtain $-y \leq -x$ as required.
If $y = +\infty$ , then we have $-y = -\infty$ so $-y \leq -x$ by Definition 6.2.3(c).
If $x=-\infty$ then we have $-x = +\infty$ so $-y \leq -x$ by Definition 6.2.3(b).

Solutions

Exercise 6.1.10

June 14, 2020 Issa Rice Leave a comment

Exercise statement

Show that the concept of equivalent Cauchy sequence, as defined in Definition 5.2.6, does not change if $\varepsilon$ is required to be positive real instead of positive rational. More precisely, if $(a_n)_{n=0}^\infty$ and $(b_n)_{n=0}^\infty$ are sequences of reals, show that $(a_n)_{n=0}^\infty$ and $(b_n)_{n=0}^\infty$ are eventually $\varepsilon$ -close for every rational $\varepsilon > 0$ if and only if they are eventually $\varepsilon$ -close for every real $\varepsilon > 0$ .

Hints

Modify the proof of Proposition 6.1.4.

How to think about the exercise

The exercise statement talks about Cauchy sequences, but we don’t require the sequences to be Cauchy; we wanted the rational sequences to be Cauchy before for constructing the real numbers, but in general we can drop this requirement as it is not relevant (i.e. the result of this exercise follows without this requirement).

Model solution

Suppose first that $(a_n)_{n=0}^\infty$ and $(b_n)_{n=0}^\infty$ are eventually $\varepsilon$ -close for every real $\varepsilon > 0$ . Then in particular, they are eventually $\varepsilon$ -close for every rational $\varepsilon > 0$ , since the rationals are a subset of the reals.

Now suppose that $(a_n)_{n=0}^\infty$ and $(b_n)_{n=0}^\infty$ are eventually $\varepsilon$ -close for every rational $\varepsilon > 0$ . Let $\varepsilon > 0$ be a real number. Then by Proposition 5.4.12 or Proposition 5.4.14, we can find a positive rational number $\varepsilon'$ such that $\varepsilon' \leq \varepsilon$ . Since $\varepsilon'$ is rational, we know that $(a_n)_{n=0}^\infty$ and $(b_n)_{n=0}^\infty$ are eventually $\varepsilon'$ -close, i.e. there is an $N\geq0$ such that $|a_n - b_n| \leq \varepsilon'$ for all $n \geq N$ . For this same $N$ , we have $|a_n - b_n| \leq \varepsilon' \leq \varepsilon$ for all $n \geq N$ , so these two sequences are eventually $\varepsilon$ -close as required.

Solutions

Exercise 6.1.9

June 13, 2020 Issa Rice 2 Comments

Exercise statement

Explain why Theorem 6.1.19(f) fails when the limit of the denominator is $0$ . (To repair that problem requires L’Hôpital’s rule, see Section 10.5.)

Hints

None.

How to think about the exercise

This is a straightforward exercise, so I don’t have anything to say.

Model solution

The limit of the denominator is $y$ . If $y=0$ , then $x/y$ is not defined, so it doesn’t make sense to say that $(a_n/b_n)_{n=m}^\infty$ converges to $x/y$ .

Could $(a_n/b_n)_{n=m}^\infty$ still converge to something? In other words, does the limit $\lim_{n\to\infty} (a_n/b_n)$ exist? It can sometimes exist. For instance, if we have $a_n := 1/n$ and $b_n := 1/n$ , then $b_n \to 0$ as $n\to \infty$ . But also $a_n/b_n = 1$ for all $n$ , so $a_n/b_n \to 1$ as $n \to \infty$ , so the limit exists. In this case $x/y = 0/0$ which is not defined. If instead we have $a_n := 1$ for all $n$ , then $a_n/b_n = n$ so the sequence diverges. Thus $(a_n/b_n)_{n=m}^\infty$ does not always converge either.

Solutions

Exercise 6.1.8

June 11, 2020 Issa Rice 16 Comments

Exercise statement

Prove Theorem 6.1.19.

Theorem 6.1.19 (Limit Laws). Let $(a_n)_{n=m}^\infty$ and $(b_n)_{n=m}^\infty$ be convergent sequences of real numbers, and let $x,y$ be real numbers $x := \lim_{n\to\infty} a_n$ and $y := \lim_{n\to\infty} b_n$ .

(a) The sequence $(a_n + b_n)_{n=m}^\infty$ converges to $x+y$ ; in other words,

$\displaystyle \lim_{n\to\infty} (a_n+b_n) = \lim_{n\to\infty} a_n + \lim_{n\to\infty} b_n$ .

(b) The sequence $(a_n b_n)_{n=m}^\infty$ converges to $xy$ ; in other words,

$\displaystyle \lim_{n\to\infty} (a_n b_n) = \left( \lim_{n\to\infty} a_n\right) \left(\lim_{n\to\infty} b_n\right)$ .

$\displaystyle \lim_{n\to\infty} (ca_n) = c \lim_{n\to\infty} a_n$ .

(d) The sequence $(a_n - b_n)_{n=m}^\infty$ converges to $x-y$ ; in other words,

$\displaystyle \lim_{n\to\infty} (a_n-b_n) = \lim_{n\to\infty} a_n - \lim_{n\to\infty} b_n$ .

(e) Suppose that $y\ne0$ , and that $b_n\ne0$ for all $n \geq m$ . Then the sequence $(b_n^{-1})_{n=m}^\infty$ converges to $y^{-1}$ ; in other words,

$\displaystyle \lim_{n\to\infty} b_n^{-1} = \left(\lim_{n\to\infty} b_n\right)^{-1}$ .

(f) Suppose that $y\ne0$ , and that $b_n\ne0$ for all $n \geq m$ . Then the sequence $(a_n/b_n)_{n=m}^\infty$ converges to $x/y$ ; in other words,

$\displaystyle \lim_{n\to\infty} \frac{a_n}{b_n} = \frac{\lim_{n\to\infty} a_n}{\lim_{n\to\infty} b_n}$ .

(g) The sequence $(\max(a_n, b_n))_{n=m}^\infty$ converges to $\max(x,y)$ ; in other words,

$\displaystyle \lim_{n\to\infty} \max(a_n,b_n) = \max\left(\lim_{n\to\infty} a_n, \lim_{n\to\infty} b_n\right)$ .

(h) The sequence $(\min(a_n, b_n))_{n=m}^\infty$ converges to $\min(x,y)$ ; in other words,

$\displaystyle \lim_{n\to\infty} \min(a_n,b_n) = \min\left(\lim_{n\to\infty} a_n, \lim_{n\to\infty} b_n\right)$ .

Hints

You can use some parts of the theorem to prove others, e.g., (b) can be used to prove (c); (a), (c) can be used to prove (d); and (b), (e) can be used to prove (f).
The proofs are similar to those of Lemma 5.3.6, Proposition 5.3.10, and Lemma 5.3.15.
For (e), you may need to first prove the auxiliary result that any sequence whose elements are non-zero, and which converges to a non-zero limit, is bounded away from zero.

How to think about the exercise

I feel like I should talk about where some of the bounds are coming from in the proofs below. It’s pretty similar to the proof of Proposition 5.3.10, so I’m not entirely sure how much I should explain (i.e. it’s not clear to me how comfortable students typically are with epsilonics by the time they reach this point in the book, so I’m not sure if I’m explaining too quickly or too slowly—I’d appreciate any feedback about this in the comments). Since writing this post has already taken a lot of time, and I do want to keep to a regular schedule of about one post per day, so I’ll lean toward under-explaining for now, and may come back later to explain this better.

In part (e), the hint talks about showing that any sequence whose elements are non-zero, and which converges to a non-zero limit, is bounded away from zero. In other words, $(b_n)_{n=m}^\infty$ consists of non-zero elements and converges to $y \ne 0$ , so we must have some constant $c > 0$ such that $|b_n| \geq c$ for all $n \geq m$ . But I prefer to think of this as showing that $(1/b_n)_{n=m}^\infty$ is bounded. These are actually equivalent statements, which we can show: suppose $(b_n)_{n=m}^\infty$ is bounded away from zero. Then there is some $c > 0$ such that $|b_n| \geq c$ for all $n \geq m$ . But this means $|1/b_n| \leq 1/c$ for all $n \geq m$ , so $(1/b_n)_{n=m}^\infty$ is bounded. Conversely, suppose $(1/b_n)_{n=m}^\infty$ is bounded by some constant $M > 0$ . This means $|1/b_n| \leq M$ for all $n \geq m$ . But this means $|b_n| \geq 1/M$ for all $n \geq m$ , so $(b_n)_{n=m}^\infty$ is bounded away from zero by the constant $1/M > 0$ . As I said, I prefer to think of this in terms of showing that $(1/b_n)_{n=m}^\infty$ is bounded, so I will phrase the proof of part (e) in those terms, but it really is the same thing as what the hint is talking about.

I don’t think $\max$ and $\min$ have been defined at this point in the book, so here is the definition we will use. Let $x,y$ be real numbers. Then $\max(x,y)$ is defined to be

$y$ if $x < y$ ,
$x=y$ if $x=y$ , and
$x$ if $y < x$ .

This definition makes sense thanks to order trichotomy. We can define $\min(x,y)$ similarly.

We shall prove a few simple properties of $\max$ to simplify the proof of part (g).

Fact 1. Let $x,y,M$ be real numbers. Then we have the following.

$x \leq \max(x,y)$
$y \leq \max(x,y)$
If $x \leq M$ and $y \leq M$ then $\max(x,y) \leq M$ .

Proof. We have three cases. If $x < y$ then $\max(x,y) = y$ so we have both $x \leq y=\max(x,y)$ and $y \leq y=\max(x,y)$ . Also, since $y \leq M$ we have $\max(x,y) = y \leq M$ .

If $x=y$ then we have $x \leq x = \max(x,y)$ and $y \leq y = \max(x,y)$ . Also we have $\max(x,y) = x \leq M$ .

If $y < x$ then we have $x \leq x = \max(x,y)$ and $y \leq x = \max(x,y)$ . Also we have $\max(x,y) = x \leq M$ . $\Box$

Model solution

(a) We want to show that $(a_n + b_n)_{n=m}^\infty$ converges to $x+y$ , so let $\varepsilon > 0$ be a real number. Since $(a_n)_{n=m}^\infty$ converges to $x$ , there is an integer $N_1 \geq m$ such that $|a_n - x| \leq \varepsilon/2$ for all $n \geq N_1$ . Also, since $(b_n)_{n=m}^\infty$ converges to $y$ , there is an integer $N_2 \geq m$ such that $|b_n - y| \leq \varepsilon/2$ for all $n \geq N_2$ . Choose $N := N_1 + N_2$ . Then if $n \geq N$ , we have both $n \geq N_1$ and $n \geq N_2$ , so $|a_n - x|\leq\varepsilon/2$ and $|b_n-y|\leq \varepsilon/2$ . By the triangle inequality we thus have

$\begin{aligned}|(a_n+b_n) - (x+y)| &= |(a_n-x) + (b_n-y)| \\ &\leq |a_n-x| + |b_n-y| \\ &\leq \varepsilon\end{aligned}$

for all $n \geq N$ , so the limit exists as required.

(b) We want to show that $(a_n b_n)_{n=m}^\infty$ converges to $xy$ , so let $\varepsilon > 0$ be a real number. Since $(a_n)_{n=m}^\infty$ is a convergent sequence, by Corollary 6.1.17 it is bounded by some constant $M > 0$ . Also, since $(a_n)_{n=m}^\infty$ converges to $x$ , there is an integer $N_1 \geq m$ such that $|a_n - x| \leq \frac{\varepsilon}{2(|y| + 1)}$ for all $n \geq N_1$ ; and since $(b_n)_{n=m}^\infty$ converges to $y$ , there is an integer $N_2 \geq m$ such that $|b_n - y| \leq \frac{\varepsilon}{2M}$ for all $n \geq N_2$ . Choose $N := N_1 + N_2$ . Then if $n \geq N$ , we have both $n \geq N_1$ and $n \geq N_2$ , so $|a_n - x|\leq \frac{\varepsilon}{2(|y| + 1)}$ and $|b_n-y|\leq \frac{\varepsilon}{2M}$ . By the triangle inequality and Proposition 4.3.3(d) we thus have

$\displaystyle \begin{aligned}|a_n b_n - xy| &= |a_n b_n - a_n y + a_n y - xy| \\ &\leq |a_n b_n - a_n y| + |a_n y - xy| \\ &= |a_n| |b_n - y| + |y||a_n - x| \\ &\leq M \cdot \frac{\varepsilon}{2M} + |y| \cdot \frac{\varepsilon}{2(|y| + 1)} \\ &\leq \varepsilon/2 + \varepsilon/2 \\ &= \varepsilon\end{aligned}$

for all $n \geq N$ , so the limit exists as required.

(c) The constant sequence $(c)_{n=m}^\infty = (c,c,c,\ldots)$ converges to $c$ because for each $\varepsilon >0$ we have $|c-c| = 0 \leq \varepsilon$ for all $n \geq m$ . Thus by part (b) we have $\lim_{n\to\infty} (ca_n) = \left(\lim_{n\to\infty} c\right) \left(\lim_{n\to\infty} a_n\right) = c\lim_{n\to\infty} a_n$ .

(d) By part (c), we have $\lim_{n\to\infty} ((-1)b_n) = (-1)\lim_{n\to\infty} b_n$ . By part (a) we have $\lim_{n\to\infty} (a_n + (-1)b_n) = \lim_{n\to\infty} a_n + \lim_{n\to\infty} (-1)b_n$ . Thus we have

$\displaystyle \begin{aligned}\lim_{n\to\infty} (a_n - b_n) &= \lim_{n\to\infty} (a_n + (-1)b_n) \\ &= \lim_{n\to\infty} a_n + \lim_{n\to\infty} (-1)b_n \\ &= \lim_{n\to\infty} a_n + (-1)\lim_{n\to\infty} b_n \\ &= \lim_{n\to\infty} a_n - \lim_{n\to\infty} b_n\end{aligned}$

as required.

(e) We first show that the sequence $(1/b_n)_{n=m}^\infty$ is bounded. The sequence $(b_n)_{n=m}^\infty$ is Cauchy and $|y|/2$ is positive since $y\ne0$ , so there exists an $N \geq m$ such that $|b_n - y| \leq |y|/2$ for all $n \geq N$ . By the triangle inequality we have $|(y-b_n) + b_n| \leq |y - b_n| + |b_n|$ , i.e. $|y| - |b_n| \leq |b_n - y|$ . Thus we have $|y| - |b_n| \leq |y|/2$ , which means $|y|/2 \leq |b_n|$ . Since both sides are positive, we have $1/|b_n| \leq 2/|y|$ , which holds for all $n \geq N$ . By Lemma 5.1.14, the finite sequence $1/|b_1|, \ldots, 1/|b_N|$ is bounded by some constant $M_0 > 0$ . Now if we let $M:=2/|y| + M_0$ then we have $1/|b_n| \leq M$ for all $n \geq m$ .

Now we start the actual proof. Let $\varepsilon > 0$ be a real number. We want to show that there is some $N \geq m$ such that $|b_n^{-1} - y^{-1}| \leq \varepsilon$ for all $n \geq N$ . Since $(b_n)_{n=m}^\infty$ converges to $y$ , there is $N \geq m$ such that $|b_n - y| \leq \varepsilon|y|/M$ for all $n \geq N$ . Choose this $N$ . Then if $n \geq N$ we have

$\displaystyle \begin{aligned}|b_n^{-1} - y^{-1}| &= \left|\frac{1}{b_n} - \frac{1}{y}\right| \\ &= \left|\frac{y-b_n}{b_n y}\right| \\ &= \frac{1}{|b_n|} \cdot \frac{1}{|y|} \cdot |b_n - y| \\ &\leq M \cdot \frac1{|y|} \cdot \frac{\varepsilon|y|}{M} \\ &= \varepsilon\end{aligned}$

as required.

(f) By parts (b) and (e) we have

$\displaystyle \begin{aligned}\lim_{n\to\infty} \frac{a_n}{b_n} &= \lim_{n\to\infty} (a_n b_n^{-1}) \\ &=_{(\text b)} \left(\lim_{n\to\infty} a_n\right) \left(\lim_{n\to\infty} b_n^{-1}\right) \\ &=_{(\text e)} \left(\lim_{n\to\infty} a_n\right) \left(\lim_{n\to\infty} b_n\right)^{-1} \\ &= \frac{\lim_{n\to\infty} a_n}{\lim_{n\to\infty} b_n}\end{aligned}$

(g) We have two cases, $x \geq y$ or $x < y$ . Suppose first that $x \geq y$ . In this case, $\max(x,y) = x$ . We thus want to show that $\max(a_n, b_n) \to x$ as $n \to \infty$ . Let $\varepsilon > 0$ be a real number. Since $(a_n)_{n=m}^\infty$ converges to $x$ , there is an integer $N_1 \geq m$ such that $|a_n - x| \leq \varepsilon$ for all $n \geq N_1$ . Also since $(b_n)_{n=m}^\infty$ converges to $y$ , there is an integer $N_2 \geq m$ such that $|b_n - x| \leq \varepsilon$ for all $n \geq N_2$ . Now choose $N:=N_1+N_2$ . Then if $n \geq N$ , we have both $n \geq N_1$ and $n \geq N_2$ , so we have both $|a_n - x| \leq \varepsilon$ and $|b_n - y| \leq \varepsilon$ . Using Exercise 5.4.6, we can rewrite these inequalities as $x-\varepsilon \leq a_n \leq x+\varepsilon$ and $y-\varepsilon \leq b_n \leq y+\varepsilon$ . Since $x \geq y$ in this case, we have $y+\varepsilon \leq x+\varepsilon$ . We have both $a_n \leq x+\varepsilon$ and $b_n \leq y+\varepsilon \leq x+\varepsilon$ , so by Fact 1 we have $\max(a_n,b_n) \leq x+\varepsilon$ . Also by Fact 1, we have $a_n \leq \max(a_n,b_n)$ . Thus we have $x-\varepsilon \leq a_n \leq \max(a_n,b_n) \leq x+\varepsilon$ . Using Exercise 5.4.6 again, we can rewrite this as $|\max(a_n,b_n) - x| \leq \varepsilon$ . Since $x = \max(x,y)$ in this case, this means we have $|\max(a_n,b_n) - \max(x,y)| \leq \varepsilon$ for all $n \geq N$ . Thus the sequence converges in this case.

Now suppose $x < y$ . In this case, $\max(x,y) = y$ . The proof is the same up to where we have $x-\varepsilon \leq a_n \leq x+\varepsilon$ and $y-\varepsilon \leq b_n \leq y+\varepsilon$ . In this case, we have $x+\varepsilon < y+\varepsilon$ so we have both $a_n \leq x+\varepsilon < y+\varepsilon$ and $b_n \leq y+\varepsilon$ , which means $\max(a_n,b_n) \leq y + \varepsilon$ by Fact 1. Also, $b_n \leq \max(a_n,b_n)$ by Fact 1 so we have $y-\varepsilon \leq b_n \leq \max(a_n,b_n)$ . Thus we have $y-\varepsilon \leq \max(a_n,b_n) \leq y+\varepsilon$ , which means $|\max(a_n,b_n) - y| \leq \varepsilon$ . Since $y = \max(x,y)$ in this case, this means $|\max(a_n,b_n) - \max(x,y)| \leq \varepsilon$ ; this holds for all $n\geq N$ , so this proves convergence.

(h) We first show that $\min(a,b) = - \max(-a, -b)$ for all real numbers $a,b$ . We have three cases, $a < b$ , $a=b$ , and $a > b$ . If $a < b$ then $\min(a,b) = a$ . We also have $-a > -b$ so $- \max(-a,-b) = - (-a) = a$ . Thus the two are equal. If $a=b$ then $-a=-b$ so $\min(a,b) = a = -(-a) = -\max(-a,-b)$ . If $a > b$ then $-a < -b$ so $\min(a,b) = b = -(-b) = -\max(-a,-b)$ as required.

Now by parts (c) and (g) we have

$\displaystyle \begin{aligned}\lim_{n\to\infty} \min(a_n, b_n) &= \lim_{n\to\infty} (-\max(-a_n, -b_n)) \\ &=_{(\text c)} -\lim_{n\to\infty} \max(-a_n, -b_n) \\ &=_{(\text g)} - \max\left( \lim_{n\to\infty}(-a_n), \lim_{n\to\infty}(-b_n)\right) \\ &=_{(\text c)} - \max\left( - \lim_{n\to\infty}a_n, - \lim_{n\to\infty}b_n\right) \\ &= \min\left(\lim_{n\to\infty}a_n, \lim_{n\to\infty}b_n\right)\end{aligned}$

Solutions

Exercise 3.1.6

June 2, 2020 Issa Rice 1 Comment

Exercise statement

Prove Proposition 3.1.28.

Proposition 3.1.28 (Sets form a boolean algebra). Let $A,B,C$ be sets, and let $X$ be a set containing $A,B,C$ as subsets.

(a) (Minimal element) We have $A\cup \emptyset = A$ and $A \cap \emptyset = \emptyset$ .
(b) (Maximal element) We have $A \cup X = X$ and $A \cap X = A$ .
(c) (Identity) We have $A \cap A = A$ and $A \cup A = A$ .
(d) (Commutativity) We have $A \cup B = B \cup A$ and $A \cap B = B \cap A$ .
(e) (Associativity) We have $(A\cup B) \cup C = A \cup (B \cup C)$ and $(A \cap B) \cap C = A \cap (B \cap C)$ .
(f) (Distributivity) We have $A \cap (B\cup C) = (A \cap B) \cup (A\cap C)$ and $A\cup (B\cap C) = (A\cup B) \cap (A \cup C)$ .
(g) (Partition) We have $A \cup (X \setminus A) = X$ and $A \cap (X \setminus A) = \emptyset$ .
(h) (De Morgan laws) We have $X \setminus (A \cup B) = (X \setminus A) \cap (X \setminus B)$ and $X\setminus (A \cap B) = (X \setminus A) \cup (X \setminus B)$ .

Hints

One can use some of these claims to prove others.
Some of the claims have also appeared previously in Lemma 3.1.13.

How to think about the exercise

The strategy for most of the parts of this exercise is to show that both $A \subseteq B$ and $B \subseteq A$ , from which we can conclude $A=B$ . (Just to be clear, the $A,B$ here are not the same as the $A,B$ in the exercise itself.) To show that $A \subseteq B$ , we suppose that $x \in A$ , and then show that $x \in B$ . You might be nervous about this maneuver, since we didn’t check that $A$ is non-empty. By single choice (Lemma 3.1.6) we can only say that $x \in A$ when $A$ is non-empty, right? What is going on, and does this make all of our proofs invalid? Might we need to redo all of our proofs to split into cases depending on whether each set is empty or non-empty? It turns out that all of the proofs we do here are correct as stated, without having to consider empty sets separately. But we do need to be careful; indeed, I believe Exercise 3.5.6 is designed to demonstrate why we must be careful.

So why are all of the proofs here fine as stated? To show that $A \subseteq B$ , we must show that for all objects $x$ , if $x \in A$ then $x \in B$ . So we let $x$ be an arbitrary object, and we suppose that $x \in A$ , in order to show $x \in B$ . We aren’t claiming that an arbitrary object $x$ is contained in $A$ , and we aren’t even claiming that $A$ is non-empty. We are just saying to assume this as a hypothesis, in order to demonstrate an implication. This is the same as trying to show an implication $P \implies Q$ and supposing that $P$ is true. If $A$ is empty, the proof is still valid since the implication is vacuous in this case.

If you are suspicious of some of the proofs here (e.g. the De Morgan laws) because they seem to rely on verbal trickery, you are right. We can’t do any better without going into the details of first-order logic, and even then it won’t be completely satisfying because a mind must already contain certain rules in order to do any mathematics at all; see here for a longer explanation.

I’m not entirely sure what Tao meant by “One can use some of these claims to prove others”; I can’t see a way to apply any of the parts to some other part in a way that saves a lot of time.

This exercise is pretty long and tedious, and it can become pretty tempting to quickly rush through it. If you don’t want to do the whole thing, and instead want to pick a couple of parts and do those carefully, then I would recommend doing parts (f) and/or (h).

The distributivity law, part (f), is probably the most interesting one to prove. My recommendation is to not appeal to the fact that logical “or” and logical “and” distribute over each other, as that fact has not been covered in the text. If you prefer, you could first show that logical “or” and logical “and” distribute over each other, after which proving distributivity for set operations becomes easy. The important point is that you show distributivity in one way or another “from first principles” rather than just assuming it.

Model solution

(a) We have $A\cup \emptyset = A$ by Lemma 3.1.13. Thus we only have to show $A \cap \emptyset = \emptyset$ . There cannot be any object $x \in A \cap \emptyset$ , because if there were such an object, we would have $x \in A$ and $x \in \emptyset$ , which contradicts the fact that $\emptyset$ contains no elements. Thus $A\cap \emptyset$ is empty, which means $A \cap \emptyset = \emptyset$ by the uniqueness of the empty set. (See the text following Axiom 3.2 for the uniqueness of the empty set.)

(One can also use Exercise 3.1.5 and the commutativity of the intersection operation for this part; part (d) can be proved without using part (a), so there is no circularity.)

(b) We first show $A \cup X = X$ . If $x \in A \cup X$ , then $x \in A$ or $x \in X$ . If $x \in A$ , then since $A$ is subset of $X$ we have $x \in X$ as required. If $x \in X$ , then we are already done. In either case we have $x \in X$ , so this shows that $A \cup X \subseteq X$ . Now suppose conversely that $x \in X$ . We must show that $x \in A$ or $x \in X$ ; but the latter statement is true, so $x \in A \cup X$ , which means that $X \subseteq A\cup X$ .

Next we show that $A \cap X = A$ . Suppose first that $x \in A \cap X$ . Then $x \in A$ and $x \in X$ , so in particular $x \in A$ . Conversely, suppose $x \in A$ . Then since $A$ is a subset of $X$ , we have $x \in X$ . Thus we have both $x \in A$ and $x \in X$ , which means $x \in A \cap X$ as required.

(One can also use Exercise 3.1.5 for this part, but I am doing the exercises out of order and I still haven’t done that one.)

(c) We have $A \cup A = A$ by Lemma 3.1.13. Thus we only have to show that $A \cap A = A$ . Suppose $x \in A \cap A$ . Then $x \in A$ and $x \in A$ , so in particular $x \in A$ . This shows that $A \cap A \subseteq A$ . Now suppose $x \in A$ . Then $x \in A$ and $x \in A$ , so $x \in A \cap A$ . This shows that $A \subseteq A \cap A$ . Combining these two parts, we have $A\cup A = A$ as required.

(One can also use Exercise 3.1.5 for this part, but I am doing the exercises out of order and I still haven’t done that one.)

(Since $A \subseteq A$ , we can also take $X=A$ and apply part (b).)

(d) We showed that the union operation is commutative in Lemma 3.1.13, so we only have to show that $A \cap B = B \cap A$ . Suppose $x \in A \cap B$ . Then $x \in A$ and $x \in B$ . We can reorder logical “and” statements, so we have $x \in B$ and $x \in A$ , which means $x \in B \cap A$ as required. The converse is proved in the same way, just switching the roles of $A$ and $B$ . Thus $A \cap B = B \cap A$ as required.

(e) The union operation is associative by Lemma 3.1.13, so we only have to show that $(A \cap B) \cap C = A \cap (B \cap C)$ . Suppose $x \in (A \cap B) \cap C$ . This means that $x \in A \cap B$ and $x \in C$ . To say that $x \in A \cap B$ means to say that $x \in A$ and $x \in B$ . Since $x \in B$ and $x \in C$ , this means $x \in B \cap C$ . Since we also know that $x \in A$ , we thus have $x \in A \cap (B \cap C)$ . The converse is proved in the same way. Thus $(A \cap B) \cap C = A \cap (B \cap C)$ as required.

(f) We first show that $A \cap (B\cup C) = (A \cap B) \cup (A\cap C)$ . Suppose $x \in A \cap (B \cup C)$ . This means that $x \in A$ and $x \in B \cup C$ . Since $x \in B \cup C$ , this means that $x \in B$ or $x \in C$ , so now we have two cases. If $x \in B$ , then since we already know that $x \in A$ , we have $x \in A \cap B$ . Thus we have $x \in A \cap B$ or $x \in A \cap C$ (since the first statement is true), so $x \in (A \cap B)\cup(A \cap C)$ . Alternatively if $x \in C$ , then we already know $x \in A$ so $x \in A \cap C$ . Thus we have $x \in A \cap B$ or $x \in A \cap C$ (since the second statement is true), which means that $x \in (A \cap B)\cup (A\cap C)$ . In either case we have shown that $x \in (A \cap B)\cup (A\cap C)$ , so this proves that $A \cap (B\cup C) \subseteq (A \cap B) \cup (A\cap C)$ . Conversely suppose that $x \in (A \cap B)\cup(A\cap C)$ . This means that either $x \in A \cap B$ or $x \in A \cap C$ . In the former case, we have $x \in A$ and $x \in B$ . Since $x \in B$ , we have $x \in B$ or $x \in C$ , which means $x \in B \cup C$ . Thus we have both $x \in A$ and $x \in B \cup C$ , which means $x \in A\cap (B\cup C)$ . Similarly in the latter case where $x \in A \cap C$ , we can show that $x \in A \cap (B\cup C)$ . In either case we have $x \in A\cap (B\cup C)$ , so $(A \cap B)\cup(A\cap C) \subseteq A \cap (B\cup C)$ as required.

Next we show that $A\cup (B\cap C) = (A\cup B) \cap (A \cup C)$ . Suppose that $x \in A\cup (B\cap C)$ . Thus we have $x \in A$ or $x \in B \cap C$ . If $x \in A$ , then $x \in A$ or $x \in B$ (since the first statement is true), so $x \in A \cup B$ . We also have $x \in A$ or $x \in C$ (since again the first statement is true), so $x \in A\cup C$ . Thus we have $x \in A\cup B$ and $x \in A \cup C$ , so $x \in (A\cup B)\cap (A\cap C)$ . On the other hand, if $x \in B\cap C$ , then we have both $x \in B$ and $x \in C$ . Thus we have $x \in A$ or $x \in B$ (since the second statement is true), so $x \in A \cup B$ . Similarly, we have $x \in A$ or $x \in C$ (since again the second statement is true), so $x \in A \cup C$ . We thus have both $x \in A \cup B$ and $x \in A \cup C$ , so $x \in (A\cup B) \cap (A \cup C)$ as required. In both cases, we have $x \in (A\cup B) \cap (A \cup C)$ , so this shows that $A\cup (B\cap C) \subseteq (A\cup B) \cap (A \cup C)$ . Conversely suppose $x \in (A\cup B) \cap (A \cup C)$ . Then we have both $x \in A\cup B$ and $x \in A\cup C$ . Now we have two cases, $x \in A$ or $x \notin A$ . If $x \in A$ , then $x \in A$ or $x \in B\cap C$ (since the first statement is true), so $x \in A \cup (B\cap C)$ . On the other hand, if $x \notin A$ , then since $x \in A\cup B$ we have $x \in A$ or $x \in B$ , and since the first option is impossible we conclude that $x \in B$ . Similarly we have $x \in C$ since $x \in A \cup C$ and $x\notin A$ . Thus in this case $x \in B\cap C$ , so we have $x \in A$ or $x \in B\cap C$ (since the second statement is true), which means $x \in A \cup (B\cap C)$ . In either case we have shown that $x \in A \cup (B\cap C)$ , so this shows that $(A\cup B) \cap (A \cup C) \subseteq A \cup (B\cap C)$ .

(g) We first show that $A \cup (X \setminus A) = X$ . Suppose $x \in A \cup (X \setminus A)$ . Then $x \in A$ or $x \in X \setminus A$ , so we have two cases. If $x \in A$ , then $x \in X$ since $A$ is a subset of $X$ . On the other hand, if $x \in X \setminus A$ , then we have $x \in X$ and $x \notin A$ , so in particular $x \in X$ . In either case we have $x \in X$ , so $A \cup (X \setminus A) \subseteq X$ . Conversely suppose that $x \in X$ . We have two cases, either $x \in A$ or $x \notin A$ . If $x \in A$ then $x \in A$ or $x \in X \setminus A$ (since the first statement is true), so $x \in A \cup (X \setminus A)$ as required. If $x \notin A$ , then since $x \in X$ this means $x \in X \setminus A$ . Thus $x \in A$ or $x \in X \setminus A$ (since the second statement is true), so $x \in A \cup (X \setminus A)$ . In either case we have $x \in A \cup (X \setminus A)$ , so $X \subseteq A \cup (X \setminus A)$ .

Next we show that $A \cap (X \setminus A) = \emptyset$ . To do this, we shall show that $A \cap (X \setminus A)$ is empty; since the empty set is unique this will be sufficient. We want to show that there is no object $x$ such that $x \in A \cap (X \setminus A)$ . Suppose for sake of contradiction that such an object $x$ exists. Then we have $x \in A$ and $x \in X \setminus A$ . The latter statement means $x \in X$ and $x \notin A$ . Thus we have both $x \in A$ and $x \notin A$ , a contradiction.

(h) First we show that $X \setminus (A \cup B) = (X \setminus A) \cap (X \setminus B)$ . Suppose $x \in X \setminus (A \cup B)$ . This means $x \in X$ and $x \notin A \cup B$ . The latter statement means that it is not the case that $x\in A$ or $x \in B$ ; thus $x \notin A$ and $x \notin B$ . But now we have $x \in X$ and $x \notin A$ , which means $x \in X \setminus A$ , and we also have both $x \in X$ and $x \notin B$ , so $x \in X \setminus B$ . Thus we have $x \in (X \setminus A) \cap (X\setminus B)$ as required. Conversely, suppose $x \in (X \setminus A) \cap (X \setminus B)$ . Thus we have both $x \in X \setminus A$ and $x \in X\setminus B$ . The first of these decomposes to $x \in X$ and $x \notin A$ , and the second decomposes to $x \in X$ and $x \notin B$ . To say that $x \notin A$ and $x \notin B$ is to say that $x$ is not in either of these sets, so $x \notin A\cup B$ . Since we also know $x \in X$ , this means $x \in X \setminus (A \cup B)$ .

Next we show that $X\setminus (A \cap B) = (X \setminus A) \cup (X \setminus B)$ . Suppose first that $x \in X\setminus (A \cap B)$ . This means $x \in X$ and $x \notin A \cap B$ . The latter statement means that $x$ is not in both of the sets $A$ and $B$ , so it is either not in $A$ or not in $B$ , i.e. $x \notin A$ or $x \notin B$ . We now have two cases. If $x \notin A$ then since we already know $x \in X$ , we have $x \in X \setminus A$ . Thus $x \in X \setminus A$ or $x \in X \setminus B$ (since the first statement is true), which means $x \in (X \setminus A)\cup(X \setminus B)$ . On the other hand, if $x \notin B$ then we similarly have $x \in (X \setminus A)\cup(X \setminus B)$ . Thus $X\setminus (A \cap B) \subseteq (X \setminus A) \cup (X \setminus B)$ . Conversely suppose $x \in (X \setminus A) \cup (X \setminus B)$ . Then we have either $x \in X \setminus A$ or $x \in X \setminus B$ . In the first case, we have both $x \in X$ and $x \notin A$ . If $x \in A\cap B$ then we would have $x \in A$ , a contradiction, so we must have $x \notin A\cap B$ . Thus we have $x \in X$ and $x \notin A\cap B$ , which means $x \in X \setminus (A \cap B)$ . In the second case, we can similarly show that $x \in X \setminus (A \cap B)$ . In either case we have $x \in X \setminus (A \cap B)$ so $(X \setminus A) \cup (X \setminus B) \subseteq X \setminus (A \cap B)$ .

Solutions

Exercise 6.1.7

June 1, 2020 Issa Rice 3 Comments

Exercise statement

Show that Definition 6.1.16 is consistent with Definition 5.1.12 (i.e., prove an analogue of Proposition 6.1.4 for bounded sequences instead of Cauchy sequences).

Definition 6.1.16 (Bounded sequences). A sequence $(a_n)_{n=m}^\infty$ of real numbers is bounded by a real number $M$ iff we have $|a_n| \leq M$ for all $n \geq m$ . We say that $(a_n)_{n=m}^\infty$ is bounded iff it is bounded by $M$ for some real number $M > 0$ .

Definition 5.1.12 (Bounded sequences). Let $M \geq 0$ be rational. A finite sequence $a_1, a_2, \ldots, a_n$ is bounded by $M$ iff $|a_i| \leq M$ for all $1 \leq i \leq n$ . An infinite sequence $(a_n)_{n=1}^\infty$ is bounded by $M$ iff $|a_i| \leq M$ for all $i \geq 1$ . A sequence is said to be bounded iff it is bounded by $M$ for some rational $M \geq 0$ .

Hints

None.

How to think about the exercise

The finite sequence part of Definition 5.1.12 isn’t relevant to Definition 6.1.16, so you can just ignore it.

The “bounded by” part is silly, and I don’t think you really need to do it. If we filter to the case when both definitions make sense (i.e. rational sequence, positive rational $M$ ), then both definitions are exactly the same, so there is nothing to prove. I’ve included this part in the solution anyway.

If you find this exercise confusing, really read and understand the proof of Proposition 6.1.4 given in the book.

Model solution

Let $(a_n)_{n=m}^\infty$ be a sequence of rational numbers, and let $M > 0$ be rational. If $(a_n)_{n=m}^\infty$ is bounded by $M$ in the sense of Definition 6.1.16, then $|a_n| \leq M$ for all $n \geq m$ . But this is exactly what it means for $(a_n)_{n=m}^\infty$ to be bounded by $M$ in the sense of Definition 5.1.12. The converse can be proved in the same way. So the definition of “bounded by” is consistent between the two definitions.

Now suppose $(a_n)_{n=m}^\infty$ is bounded in the sense of Definition 6.1.16. Thus there is some real number $M > 0$ such that $|a_n| \leq M$ for all $n \geq m$ . To show that $(a_n)_{n=m}^\infty$ is bounded in the sense of Definition 5.1.12, we must find a rational number $M' \geq 0$ such that $|a_n| \leq M'$ for all $n \geq m$ . By the Archimedean property, we can find a positive integer $M'$ such that $M' > M$ . Every integer is also a rational number, so $M'$ is rational. Now we have $|a_n| \leq M < M'$ for all $n \geq m$ as required.

Conversely, suppose $(a_n)_{n=m}^\infty$ is bounded in the sense of Definition 5.1.12. Then we have a rational number $M \geq 0$ such that $|a_n| \leq M$ for all $n \geq m$ . To show that the sequence is bounded in the sense of Definition 6.1.16, we must find a positive real number $M' > 0$ such that $|a_n| \leq M'$ . Take $M' := M+1$ , which is a real number. Since $M\geq 0$ , we have $M' = M+1 \geq 1 > 0$ so $M'$ is positive. We also have $|a_n| \leq M < M+1 = M'$ for all $n \geq m$ . Thus $(a_n)_{n=m}^\infty$ is bounded in the sense of Definition 6.1.16.