Category Archives: Solutions

Exercise 2.3.2

April 3, 2020 Issa Rice 8 Comments

Exercise statement

Prove Lemma 2.3.3.

Lemma 2.3.3 (Positive natural numbers have no zero divisors). Let $n,m$ be natural numbers. Then $n\times m = 0$ if and only if at least one of $n,m$ is equal to zero. In particular, if $n$ and $m$ are both positive, then $nm$ is also positive.

Hints

Prove the second statement first.
You can use induction, but you don’t need to use induction.

How to think about the exercise

We want to show

$n\times m = 0 \iff (n=0 \lor m=0)$

This is equivalent to showing two things:

$n\times m = 0 \implies (n=0 \lor m=0)$

and

$(n=0 \lor m=0) \implies n\times m = 0$

The first of these is equivalent to

$(n\ne0 \land m\ne0) \implies n\times m \ne 0$

since it is the contrapositive. But “not equal to zero” is the same thing as “positive”, so this last implication means exactly the same thing as what Tao wrote in the statement of the lemma: “In particular, if $n$ and $m$ are both positive, then $nm$ is also positive.”

In the proof below, we will first show

$(n\ne0 \land m\ne0) \implies n\times m \ne 0\ \ \ \ \ (*)$

and then we will show

$(n=0 \lor m=0) \implies n\times m = 0$

And actually, in the proof below, the two parts are completely independent, i.e. it doesn’t matter what order you do them in. So then why does Tao’s hint say to prove the second one (i.e. the starred implication) first? I think Tao’s thinking was something like this: at this stage, it might be difficult to manipulate implications like I did above, and to realize that proving the contrapositive is equivalent to proving the original implication. So instead, if you prove the contrapositive version (as stated by Tao), then you can very easily prove the original implication using a proof by contradiction. In other words, you could say: “Suppose $n\times m = 0$ . Now suppose for a contradiction that neither $n$ nor $m$ is zero. Then we see that $nm$ is positive, a contradiction.” I think that is what Tao intended.

Model solution

Suppose $n$ and $m$ are positive. By Lemma 2.2.10, there exist natural numbers $a,b$ such that $a{{+}\!{+}} = n$ and $b{{+}\!{+}} = m$ . Thus $n\times m = (a{{+}\!{+}})\times (b{{+}\!{+}}) = ab + a + b + 1$ which is positive. (For suppose $(ab + a + b) + 1$ is not positive. Then by Corollary 2.2.9 we see that $1=0$ , a contradiction.)

Now suppose $n=0$ or $m=0$ . If $n=0$ , then $nm = 0\times m=0$ by definition of multiplication. If $m=0$ , then $nm=mn=0\times n = 0$ by commutativity of multiplication and the definition of multiplication.

Solutions

Exercise 2.3.1

April 2, 2020 Issa Rice 5 Comments

Exercise statement

Prove Lemma 2.3.2.

Lemma 2.3.2 (Multiplication is commutative). Let $n,m$ be natural numbers. Then $n\times m = m\times n$ .

Hints

Modify the proofs of Lemmas 2.2.2, 2.2.3 and Proposition 2.2.4.

How to think about the exercise

In the solution below, we prove two facts that help us with the actual proof. You might wonder where these two facts came from. And you might answer “well, you can just peek at Lemmas 2.2.2 and 2.2.3”. That’s quite right, but what if you didn’t have access to the textbook? It turns out that you can try to solve the exercise without proving the two facts, and see where you get stuck. Then, you can turn those parts into lemmas. Let’s see how this works in practice.

We want to show $n\times m = m\times n$ . We fix $m$ and induct on $n$ . For the base case, we need $0\times m = m\times 0$ . By the definition of multiplication, the left side is zero. What about the right side? Well, it would be nice if we could show that $m\times 0 = 0$ . So spin this off into a lemma. [Insert proof of the lemma here.]

Now suppose inductively that we have $n\times m = m\times n$ . We want to show $(n{{+}\!{+}})\times m = m\times (n{{+}\!{+}})$ . By definition of multiplication and the inductive hypothesis, the left side is $(n{{+}\!{+}})\times m = n\times m + m = m\times n + m$ . What about the right side? It would be nice if we could show that $m\times (n{{+}\!{+}}) = m\times n + m$ . So spin this off into a second lemma. [Insert proof of lemma here.] This closes the induction, and completes the proof.

So as you can see, the source of the lemmas isn’t mysterious: it’s what you naturally get by attempting the proof and getting stuck.

Model solution

We first show two facts analogous to Lemmas 2.2.2 and 2.2.3:

For any natural number $n$ , $n\times 0 = 0$ : We induct on $n$ . The base case is $0\times 0 = 0$ , which follows from the definition of multiplication. Now suppose inductively that $n\times 0 = 0$ . We want to show $(n{{+}\!{+}})\times 0 = 0$ . By definition of multiplication and the inductive hypothesis, $(n{{+}\!{+}})\times 0 = (n\times 0) + 0 = 0$ . This closes the induction.
For any natural numbers $n$ and $m$ , $n\times (m{{+}\!{+}}) = (n\times m) + n$ : We induct on $n$ (keeping $m$ fixed). For the case $n=0$ , we have to show $0\times (m{{+}\!{+}}) = (0\times m) + 0$ . But $0\times (m{{+}\!{+}}) = 0$ by definition of multiplication, and $(0\times m) + 0 = 0+0=0$ , so they are equal. Now suppose inductively that $n\times (m{{+}\!{+}}) = (n\times m) + n$ . We want to show that $(n{{+}\!{+}})\times (m{{+}\!{+}}) = ((n{{+}\!{+}})\times m) + (n{{+}\!{+}})$ . By definition of multiplication, $(n{{+}\!{+}})\times (m{{+}\!{+}})$ is equal to $n\times (m{{+}\!{+}}) + (m{{+}\!{+}})$ , which is equal to $n\times m + n + (m{{+}\!{+}})$ by the inductive hypothesis. Similarly, we have $((n{{+}\!{+}})\times m) + (n{{+}\!{+}}) = (n\times m + m) + (n{{+}\!{+}})$ by the definition of multiplication. Thus both sides are equal to $n\times m + m + n + 1$ .

Now we can prove the actual lemma. We fix $m$ and induct on $n$ . For the base case, we need $0\times m = m\times 0$ . By the definition of multiplication, the left side is zero, and by fact (1) above the right side is also zero.

Now suppose inductively that we have $n\times m = m\times n$ . We want to show $(n{{+}\!{+}})\times m = m\times (n{{+}\!{+}})$ . By definition of multiplication, the left side is $(n{{+}\!{+}})\times m = n\times m + m$ . By fact (2) above, the right side is $m\times (n{{+}\!{+}}) = m\times n + m$ . Thus we have to show $n\times m + m = m\times n + m$ , but this follows from the inductive hypothesis.

Solutions

Exercise 2.2.5

April 1, 2020 Issa Rice 30 Comments

Exercise statement

Prove Proposition 2.2.14.

Proposition 2.2.14 (Strong principle of induction). Let $m_0$ be a natural number, and let $P(m)$ be a property pertaining to an arbitrary natural number $m$ . Suppose that for each $m \geq m_0$ , we have the following implication: if $P(m')$ is true for all natural numbers $m_0 \leq m' < m$ , then $P(m)$ is also true. (In particular, this means that $P(m_0)$ is true, since in this case the hypothesis is vacuous.) Then we can conclude that $P(m)$ is true for all natural numbers $m \geq m_0$ .

Hints

Define $Q(n)$ to be the property that $P(m)$ is true for all $m_0 \leq m < n$ ; note that $Q(n)$ is vacuously true when $n < m_0$ .

How to think about the exercise

My first reaction to reading the proposition is something like “What on earth is going on here?”, and if that’s your reaction too, don’t worry! Even just understanding what we are trying to prove can be a challenge sometimes. In this case, the proposition has a nested “if … then …” clause and multiple variables ( $m, m', m_0$ ) that make it hard to tell what is going on. In cases like this, we can first ask, is there a simpler statement we can try to prove instead that could still give us the main idea for the full solution? One idea is to take $m_0 := 0$ ; in the proposition $m_0$ just a constant that is fixed throughout, and acts as the “base case” of the strong induction. Picking $0$ as the constant also cleans up the inequality $m \geq m_0$ because every natural number is greater than or equal to zero, so we can simply omit those conditions too.

So by setting $m_0 := 0$ and cleaning things up a bit, what we are trying to show is something like this: Let $P(m)$ be a property pertaining to an arbitrary natural number $m$ . Suppose that for each $m$ , we have the following implication: if $P(m')$ is true for all natural numbers $m' < m$ , then $P(m)$ is also true. Then we can conclude that $P(m)$ is true for all natural numbers $m$ .

Okay, since we are proving a version of strong induction, and in induction we start at some base case $P(0)$ , a natural question to ask now is, can we prove that $P(0)$ is true? The special property of $P$ we are given in this case is that if $P(m')$ is true for all $m' < 0$ , then $P(0)$ is also true. But there is no natural number $m'$ such that $m' < 0$ , so it is vacuously true that $P(m')$ is true for all $m' < 0$ . So we see that $P(0)$ is true.

Now can we prove that $P(1)$ is true? The special property of $P$ we are given in this case is that if $P(m')$ is true for all $m' < 1$ , then $P(1)$ is also true. But the only natural number $m'$ such that $m' < 1$ is the number $0$ , and we already know that $P(0)$ is true. So we have $P(1)$ as well.

Can we now prove that $P(2)$ is true? The special property of $P$ we are given in this case is that if $P(m')$ is true for all $m' < 2$ , then $P(2)$ is also true. What are the numbers less than $2$ ? That would be $0$ and $1$ , and we know both $P(0)$ and $P(1)$ are true. So $P(2)$ is also true.

I hope you see the pattern now. In the general case, we are trying to prove that $P(m)$ is true. The special property of $P$ we are given is that if $P(m')$ is true for all natural numbers $m' < m$ , then $P(m)$ is also true. But by the previous rounds of the proof, we know that $P(0), P(1), P(2), \ldots, P(m-2), P(m-1)$ are all true, and $0, 1, 2, \ldots, m-2, m-1$ are the only natural numbers less than $m$ . So $P(m)$ is true as well.

So that’s the basic idea. The argument above wasn’t rigorous because (1) we used notation like $m-2$ and $m-1$ even though subtraction hasn’t been defined in the book yet, and (2) we just said “by the previous rounds of the proof” and didn’t actually give all the previous rounds of the proof. We need to fill in those previous rounds in a rigorous way, which is where (ordinary) induction comes in.

So now how do we set up the induction? The obvious statement to try to prove by induction is $P(m)$ . We already showed that $P(0)$ is true above, which completes the base case. So if we can prove that $P(m)$ implies $P(m{+}\!{+})$ , then we’ll be done. So suppose $P(m)$ is true. The special property of $P$ we are given is that if $P(m')$ is true for all natural numbers $m' < m{+}\!{+}$ , then $P(m{+}\!{+})$ is also true. What are the numbers less than $m{+}\!{+}$ ? That would be $0, 1, 2, \ldots, m-1, m$ . Now we see the problem. We only know that $P(m)$ is true; we don’t know that $P(0), P(1), P(2), \ldots, P(m-1)$ are true, since those statements weren’t part of our inductive hypothesis. So we can’t make use of the special property of $P$ , and we are stuck.

But the nice thing about trying the obvious thing and hitting a dead end is that this can give you insight into the problem and help you reach an actual solution. This is true here. If we think about the reason we couldn’t make use of the special property of $P$ , it was that we only knew $P(m)$ as part of our inductive hypothesis, whereas we wanted to know all of $P(0), P(1), P(2), \ldots, P(m-1), P(m)$ . So could we make the conjunction “ $P(0)$ and $P(1)$ and $P(2)$ and $\cdots$ and $P(m-1)$ and $P(m)$ ” appear as our inductive hypothesis? Yes, we can! We can change the statement we prove by induction from $P(m)$ to “ $P(0)$ and $P(1)$ and $P(2)$ and $\cdots$ and $P(m-1)$ and $P(m)$ ”. To get rid of the “ $\cdots$ ”, we can state this instead as “ $P(m')$ is true for all $m' \leq m$ ”. We can call this statement $R(m)$ .

Now let’s see if we can prove $R(m)$ is true for all natural numbers $m$ by induction. For the base case, we have to show $R(0)$ , which is the statement that $P(m')$ is true for all $m' \leq 0$ . But, since the only natural number less than or equal to $0$ is $0$ itself, this is just the assertion that $P(0)$ is true. And we already know that $P(0)$ is true from our discussion above. Now suppose inductively that $R(m)$ is true. We want to show that $R(m{+}\!{+})$ is true. The statement $R(m)$ is the assertion that $P(m')$ is true for all $m' \leq m$ , and the statement $R(m{+}\!{+})$ is the assertion that $P(m')$ is true for all $m' \leq m{+}\!{+}$ . In more intuitive terms, this means that we know $P(0), P(1), \ldots, P(m-1), P(m)$ are all true, and we want to show that $P(0), P(1), \ldots, P(m-1), P(m), P(m{+}\!{+})$ are all true. The only new statement to prove is the claim that $P(m{+}\!{+})$ is true, so if we can show just that new statement, then we’ll be done. But the special property of $P$ we are given is that if $P(m')$ is true for all natural numbers $m' < m{+}\!{+}$ , then $P(m{+}\!{+})$ is also true. And we already know that $P(m')$ is true for all natural numbers $m' < m{+}\!{+}$ (that’s just the claim that $P(0), P(1), \ldots, P(m-1), P(m)$ are all true). So we get $P(m{+}\!{+})$ , and that closes our induction. Since $R(m)$ is true for all $m$ , this means in particular that $P(m)$ is also true for all $m$ .

The statement $R(m)$ that we used above is almost the same as the property $Q(m)$ that is suggested in the hint, but slightly different in that it includes the endpoint $P(m)$ . It doesn’t really matter which of $R$ or $Q$ you use. I found $R$ a bit more natural above, but the model solution below uses $Q$ as suggested in the hint.

To recap some of the problem-solving strategies I employed above:

If the full goal is too complicated, try to simplify by e.g. proving a special case. Here, we used $m_0 = 0$ .
If you don’t know which statement to prove by induction, just pick the obvious one and see how far you get; sometimes a “wrong” approach is a necessary stepping stone to finding the right approach.
Quantified statements like “ $P(m')$ is true for all $m' \leq m$ ” can be tricky for your brain to understand, so just write “ $P(0)$ and $P(1)$ and $P(2)$ and $\cdots$ and $P(m-1)$ and $P(m)$ ” instead when you are still figuring out how to approach the proof.

I want to say more, but I’m feeling tired after writing up the proof, so here are some quick comments, mostly intended as notes to myself for when I return to this exercise later:

I should also say something about why this is called strong induction. (basically the hypothesis contains more assumptions, which makes the statement stronger)
I should give an example of a problem where using strong induction makes the proof go through but where using regular induction makes it impossible.
In the proof below I showed at one point that $n \geq m_0$ . This is like splitting by the cases $n\geq m_0$ and $n < m_0$ (where the latter ends in contradiction so we don’t need to worry about it). There is an alternative way to split by cases, which is $n{{+}\!{+}} \geq m_0$ and $n{{+}\!{+}} < m_0$ . In the latter case, $Q(n{{+}\!{+}})$ is automatically true as Tao writes in the hint. In the former case, we have to further break into $n\geq m_0$ (use $Q(n) \to P(n)$ ) or $n{{+}\!{+}} = m_0$ (so we want to show $Q(m_0)$ , but this is vacuously true).
There are a lot of questions on math SE asking about this exercise. It would be nice if I can go through them in detail at some point to make sure that this post covers all of the common points of confusion.

Model solution 1

Let $Q(n)$ to be the property that $P(m)$ is true for all $m_0 \leq m < n$ . Given this definition of $Q$ , we can restate the hypothesis for $P$ as follows: for each $m \geq m_0$ , if $Q(m)$ is true then $P(m)$ is also true. To go a little more slowly, we know from the statement of Proposition 2.2.14 that $P$ has the following property:

For each $m \geq m_0$ : if $P(m')$ is true for all $m_0 \leq m' < m$ then $P(m)$ is also true.

We can use $Q$ to rewrite the above bullet point as follows:

For each $m\geq m_0$ : if $Q(m)$ is true then $P(m)$ is also true.

We will prove by induction that $Q(n)$ is true for all natural numbers $n$ .

We first want to show $Q(0)$ , which says that $P(m)$ is true for all $m_0 \leq m < 0$ . This is vacuously true since there is no natural number strictly less than zero: $m <0$ means $m \leq 0$ and $m\ne 0$ . So we have some natural number $a$ such that $0 = m+a$ , but this means $m=0$ by Corollary 2.2.9, which contradicts the fact that $m\ne 0$ . So $P(m)$ is true for all such numbers, because none exist.

Now suppose inductively that we have shown $Q(n)$ is true. We want to show that $Q(n{{+}\!{+}})$ is true, i.e. we want to show that $P(m)$ is true for all $m_0 \leq m < n{{+}\!{+}}$ . So let $m$ be a natural number and suppose $m_0 \leq m < n{{+}\!{+}}$ . Our goal is to show that $P(m)$ is true.

Since $m_0 \leq m < n{{+}\!{+}}$ , we claim that either $m_0 \leq m < n$ or $m = n$ . This is because $m < n{{+}\!{+}}$ implies $m{{+}\!{+}} \leq n{{+}\!{+}}$ by Proposition 2.2.12(e) which implies $m \leq n$ by Proposition 2.2.12(d). We know $m = n$ or $m \ne n$ ; in the latter case we thus have $m < n$ , so $m_0 \leq m < n$ . Thus we see that either $m_0 \leq m < n$ or $m = n$ .

Since $Q(n)$ is true, we know that $P(m)$ is true for all $m_0 \leq m < n$ . Thus in the case where $m_0 \leq m < n$ , we already know that $P(m)$ is true.

To complete the proof we must show that $P(m)$ is true in the case $m=n$ , i.e. we must show that $P(n)$ is true. Since $m_0 \leq m < n{{+}\!{+}}$ , by transitivity of order $m_0 < n{{+}\!{+}}$ , so $m_0{{+}\!{+}} \leq n{{+}\!{+}}$ which means $m_0 \leq n$ . Since $m_0 \leq n$ we can use the hypothesis for $P$ , which says that if $Q(n)$ is true then $P(n)$ is also true. Since $Q(n)$ is true by inductive hypothesis, we see that $P(n)$ . But since $m=n$ in this case, we have $P(m)$ as desired.

This completes the induction, and we have that $Q(n)$ is true for all natural numbers $n$ . Our original goal was to show that $P(m)$ is true for all natural numbers $m \geq m_0$ . So let $m \geq m_0$ . Then we know that $Q(m{{+}\!{+}})$ is true. Since $m_0 \leq m < m{{+}\!{+}}$ , we see that $P(m)$ is true as required.

Model solution 2

Solutions

Exercise 2.2.4

March 31, 2020 Issa Rice 10 Comments

Exercise statement

Justify the three statements marked (why?) in the proof of Proposition 2.2.13.

Hints

You might want to use Proposition 2.2.12.

How to think about the exercise

This is a simple exercise, so I don’t have any comments.

Model solution

When $a=0$ we have $0\leq b$ for all $b$ : We want to show that $b = 0+n$ for some $n$ . Take $n:=b$ . Then $0+n = 0+b = b$ by Definition 2.2.1.

If $a > b$ , then $a{{+}\!{+}} > b$ : To show $a{{+}\!{+}} > b$ , we can instead show $a{{+}\!{+}} \geq b{{+}\!{+}}$ by Proposition 2.2.12(e). Since $a > b$ we have $a \geq b$ , so by Proposition 2.2.12(d) we have $a{{+}\!{+}} = a+1 \geq b+1 = b{{+}\!{+}}$ .

If $a=b$ , then $a{{+}\!{+}} > b$ : Since $a=b$ , we want to show that $a{{+}\!{+}} > a$ . By Proposition 2.2.12(e) it suffices to show $a{{+}\!{+}} \geq a{{+}\!{+}}$ , but this is true since $a{{+}\!{+}} = (a{{+}\!{+}}) + 0$ .

Solutions

Exercise 2.2.3

March 30, 2020 Issa Rice 19 Comments

Exercise statement

Prove Proposition 2.2.12.

Proposition 2.2.12 (Basic properties of order for natural numbers). Let $a,b,c$ be natural numbers. Then

(a) (Order if reflexive) $a \geq a$ .
(b) (Order is transitive) If $a \geq b$ and $b \geq c$ , then $a\geq c$ .
(c) (Order is anti-symmetric) If $a\geq b$ and $b\geq a$ , then $a=b$ .
(d) (Addition preserves order) $a \geq b$ if and only if $a+c \geq b+c$ .
(e) $a<b$ if and only if $a{{+}\!{+}} \leq b$ .
(f) $a<b$ if and only if $b=a+d$ for some positive number $d$ .

Hints

You will need many of the preceding propositions, corollaries, and lemmas.

How to think about the exercise

Each part of the exercise is pretty straightforward. It is tiring to write down everything, but at this stage it is good for your soul.

Model solution

(a) To show that $a\leq a$ we must show that $a = a + m$ for some natural number $m$ . Pick $m:=0$ . Then by Lemma 2.2.2 we see that $a+m = a+0 = a$ as required.

(b) Suppose $a \geq b$ and $b \geq c$ , thus there are natural numbers $n,m$ such that $a = b+n$ and $b=c+m$ . We want to show that $a = c + r$ for some natural number $r$ . Pick $r := m+n$ . Then $c+r = c + (m+n) = (c+m) + n = b+n =a$ by the associativity of addition (Proposition 2.2.5).

(c) Suppose $a\geq b$ and $b\geq a$ , thus there are natural numbers $n,m$ such that $a = b+n$ and $b = a+m$ . Thus we see that $a = (a+m)+n = a + (m+n)$ by associativity of addition (Proposition 2.2.5). By the cancellation law (Proposition 2.2.6) we see that $0 = m+n$ and so by Corollary 2.2.9 we conclude that $m=0$ and $n=0$ . Thus $a = b+n = b + 0 = b$ by Lemma 2.2.2.

(d) Suppose $a \geq b$ , so that we have a natural number $n$ such that $a = b+n$ . By adding $c$ to both sides, we obtain $a+c = (b+n)+c$ . By associativity and commutativity of addition, we have $(b+n)+c = b + (n+c) = b+(c+n) = (b+c)+n$ . Thus $a+c = (b+c) + n$ , which means $a+c \geq b+c$ .

Now suppose $a+c \geq b+c$ , thus $a+c = (b+c) + n$ for some natural number $n$ . We have $(b+c) + n = b+(c+n) = b+(n+c) = (b+n)+c$ by associativity and commutativity of addition. Thus $a+c = (b+n)+c$ , so by cancellation we have $a = b+n$ , which means $a \geq b$ .

(e) Suppose $a<b$ . Thus $a \leq b$ , which means $b = a+n$ for some natural number $n$ , and we also know that $a\ne b$ . If $n=0$ , then $b=a+0=a$ which would contradict the fact that $a\ne b$ . Thus $n$ is positive. By Lemma 2.2.10 this means that there is a natural number $m$ such that $m{{+}\!{+}} = n$ . But now we have

$\begin{aligned}b &= a + (m{{+}\!{+}}) \\ &= (a+m){{+}\!{+}} \\ &= (m+a){{+}\!{+}} \\ &= m+(a{{+}\!{+}}) \\& = (a{{+}\!{+}}) + m\end{aligned}$

by repeated applications of Lemma 2.2.3 and Proposition 2.2.4. Thus we see that $b \geq a{{+}\!{+}}$ .

Now suppose $a{{+}\!{+}} \leq b$ . Thus $b = (a{{+}\!{+}}) + n$ for some natural number $n$ . We have $(a{{+}\!{+}}) + n = (a+n){{+}\!{+}} = a+ (n{{+}\!{+}})$ by Definition 2.2.1 and Lemma 2.2.3. Thus $b = a+ (n{{+}\!{+}})$ , which means that $b \geq a$ . If $b = a$ , then by cancellation we would have $0 = n{{+}\!{+}}$ , which contradicts Axiom 2.3. Thus $b \ne a$ , which combined with $b\geq a$ means that $b > a$ as required.

(f) Suppose $a<b$ . In the first part of the proof of part (e), we already showed that $b = a+n$ for positive $n$ .

Now suppose $b=a+d$ for some positive number $d$ . Since $d$ is a natural number, we have $b \geq a$ . It remains to show that $a\ne b$ . Suppose for contradiction that $a=b$ . Then by cancellation we have $0=d$ , which means $d$ is not positive, a contradiction. Thus $a\ne b$ as required.

Solutions

Exercise 5.4.1

March 29, 2020 Issa Rice 4 Comments

Exercise statement

Prove Proposition 5.4.4.

Proposition 5.4.4 (Basic properties of positive reals). For every real number $x$ , exactly one of the following three statements is true: (a) $x$ is zero; (b) $x$ is positive; (c) $x$ is negative. A real number $x$ is negative if and only if $-x$ is positive. If $x$ and $y$ are positive, then so are $x+y$ and $xy$ .

Hints

If $x$ is not zero, and $x$ is the formal limit of some sequence $(a_n)_{n=1}^\infty$ , then this sequence cannot be eventually $\varepsilon$ -close to the zero sequence $(0)_{n=1}^\infty$ for every single $\varepsilon > 0$ . Use this to show that the sequence $(a_n)_{n=1}^\infty$ is eventually either positively bounded away from zero or negatively bounded away from zero.

How to think about the exercise

This is a pretty involved exercise, and just writing up the proof is pretty tiring, so I’m struggling to come up with things to say. I suggest drawing a picture.

Bonus question: which part of the exercise is the hint talking about?

Model solution

We first show that at most one of (a), (b), (c) is true.

$x$ cannot be both zero and positive: Suppose $x$ is positive, so that $x = \mathrm{LIM}_{n\to\infty} a_n$ for some Cauchy sequence $(a_n)_{n=1}^\infty$ which is positively bounded away from zero. Thus there is some $c >0$ such that $a_n \geq c$ for all $n \geq 1$ . This means that $|a_n - 0| > c/2$ , so $(a_n)_{n=1}^\infty$ and $(0)_{n=1}^\infty$ are not eventually $c/2$ -close, so these two sequences are not equivalent. Thus $x \ne 0$ .
$x$ cannot be both zero and negative: This is similar to the above case. If $x$ is negative, then $x = \mathrm{LIM}_{n\to\infty} a_n$ for some Cauchy sequence $(a_n)_{n=1}^\infty$ which is negatively bounded away from zero. Thus $a_n \leq -c$ for some $-c < 0$ . This means $|a_n - 0| = -a_n > c/2$ so $(a_n)_{n=1}^\infty$ is not equivalent to the zero sequence, and so $x \ne 0$ .
$x$ cannot be both positive and negative: Suppose for sake of contradiction that $x$ is both positive and negative. Thus $x = \mathrm{LIM}_{n\to\infty} a_n$ for some Cauchy sequence $(a_n)_{n=1}^\infty$ which is positively bounded away from zero, and $x = \mathrm{LIM}_{n\to\infty} b_n$ for some Cauchy sequence $(b_n)_{n=1}^\infty$ which is negatively bounded away from zero. Thus we have positive rationals $c,d > 0$ such that $a_n \geq c > 0$ and $b_n \leq -d < 0$ for all $n\geq 1$ . Since $a_n$ is positive and $b_n$ is negative, we see that $a_n - b_n$ is positive, thus $|a_n - b_n| = a_n - b_n$ . Adding the inequalities above we get $|a_n-b_n| = a_n - b_n \geq c+d > (c+d)/2$ . Thus the sequences $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ are not eventually $(c+d)/2$ -close, which contradicts the fact that they are equivalent sequences.

Next we show that at least one of (a), (b), (c) is true. To do this we will show that if $x \ne 0$ then $x$ is either positive or negative. Suppose $x$ is not zero. By Lemma 5.3.14 we know that $x$ can be written as $x = \mathrm{LIM}_{n\to\infty} a_n$ for some Cauchy sequence $(a_n)_{n=1}^\infty$ which is bounded away from zero, i.e. we have some rational $c > 0$ such that $|a_n| \geq c$ for all $n \geq 1$ . Since $(a_n)_{n=1}^\infty$ is Cauchy, eventually the sequence is $c/2$ -steady. Call this point $N$ so that $|a_j - a_N| \leq c/2$ for all $j\geq N$ . Since the sequence $(a_n)_{n=1}^\infty$ is bounded away from zero, $a_N$ cannot be zero, so it is either positive or negative.

If $a_N > 0$ , then $a_N = |a_N| \geq c$ . From $|a_j - a_N| \leq c/2$ we have in particular $a_N - a_j \leq c/2$ (by Proposition 4.3.3(c)) which means $a_N - c/2 \leq a_j$ ; now using $c \leq a_N$ we have $0 < c/2 \leq a_N - c/2 \leq a_j$ , which holds for all $j \geq N$ . This shows that $(a_n)_{n=N}^\infty$ is positively bounded away from zero. This is almost what we need, except that as in the proof of Lemma 5.3.14, we cannot guarantee that the start of the sequence is above our $c/2$ threshold. To fix this, define a new sequence $b_n := c/2$ if $n < N$ and $b_n := a_n$ if $n\geq N$ . This new sequence is positively bounded away from zero, and is equivalent to $(a_n)_{n=1}^\infty$ . Thus $x$ is positive.
If $a_N < 0$ then $-a_N = |a_N| \geq c$ so $a_N \leq -c$ . By a reasoning similar to the previous case, we can show that $a_j \leq -c/2$ for all $j \geq N$ , and thus show that $x$ is negative.

Next we show that $x$ is negative if and only if $-x$ is positive. Suppose $x$ is negative. Thus $x = \mathrm{LIM}_{n\to\infty} a_n$ for some sequence $(a_n)_{n=1}^\infty$ which is negatively bounded away from zero, which means that we have a rational $-c < 0$ such that $a_n \leq -c$ for all $n \geq 1$ . By Proposition 4.2.9(d) we can add $-a_n+c$ to both sides of the inequality to get $c \leq -a_n$ , which holds for all $n\geq 1$ . Since $c$ is positive, this means that the sequence $(-a_n)_{n=1}^\infty$ is positively bounded away from zero, so $-x = \mathrm{LIM}_{n\to\infty} (-a_n)$ is positive. The converse can be proven in the same way.

Finally we show that if $x$ and $y$ are positive, then so are $x+y$ and $xy$ . Suppose $x$ and $y$ are positive, so that we can write them as $x = \mathrm{LIM}_{n\to\infty} a_n$ and $y = \mathrm{LIM}_{n\to\infty} b_n$ for some Cauchy sequences $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ which are positively bounded away from zero. This means that there are positive rational numbers $c,d > 0$ such that $a_n \geq c$ and $b_n \geq d$ for all $n \geq 1$ . By Proposition 4.2.9 parts (d) and (e) we see that $a_n + b_n \geq a_n + d \geq c+d$ and $a_n b_n \geq a_n d \geq cd$ for all $n \geq 1$ . Since $c+d$ and $cd$ are positive, this means the sequences $(a_n + b_n)_{n=1}^\infty$ and $(a_n b_n)_{n=1}^\infty$ are positively bounded away from zero. Thus $x+y$ and $xy$ are positive.

Solutions

Exercise 5.3.5

March 28, 2020 Issa Rice Leave a comment

Exercise statement

Show that $\mathrm{LIM}_{n\to\infty} 1/n = 0$ .

Hints

You might find Proposition 4.4.1 and Proposition 4.3.12 helpful.

How to think about the exercise

This is a simple exercise, so I don’t have any comments.

Model solution

We want to show that $(1/n)_{n=1}^\infty$ is equivalent to $(0)_{n=1}^\infty$ , i.e. we want to show that for every rational $\varepsilon > 0$ there exists $N\geq 1$ such that for all $n\geq N$ we have $|1/n - 0| \leq \varepsilon$ .

Let a rational $\varepsilon > 0$ be given. By Proposition 4.4.1 there exists some natural number $N$ such that $N > 1/\varepsilon$ . (Since $1/\varepsilon > 0$ , we see that $N$ cannot be zero, so its reciprocal is defined.) Now let $n \geq N$ . Then we have $n\geq 1/\varepsilon > 0$ so by Proposition 4.3.12(b) we have $0 < 1/n \leq \varepsilon$ . Since $|1/n - 0| = 1/n$ , this completes the proof.

Solutions

Exercise 5.3.4

March 27, 2020 Issa Rice 3 Comments

Exercise statement

Let $(a_n)_{n=1}^\infty$ be a sequence of rational numbers which is bounded. Let $(b_n)_{n=1}^\infty$ be another sequence of rational numbers which is equivalent to $(a_n)_{n=1}^\infty$ . Show that $(b_n)_{n=1}^\infty$ is also bounded.

Hints

Use Exercise 5.2.2.

How to think about the exercise

This is a simple exercise, so I don’t have any comments.

Model solution

Since $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ are equivalent, they are eventually $\varepsilon$ -close for every rational $\varepsilon > 0$ . Thus for $\varepsilon:=1$ in particular, $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ are eventually $1$ -close. By Exercise 5.2.2, we thus see that $(a_n)_{n=1}^\infty$ is bounded if and only if $(b_n)_{n=1}^\infty$ is bounded. Since $(a_n)_{n=1}^\infty$ is bounded by hypothesis, we see that $(b_n)_{n=1}^\infty$ is bounded as required.

Solutions

Exercise 5.3.3

March 27, 2020 Issa Rice 1 Comment

Exercise statement

Let $a,b$ be rational numbers. Show that $a=b$ if and only if $\mathrm{LIM}_{n\to\infty} a = \mathrm{LIM}_{n\to\infty} b$ (i.e., the Cauchy sequences $a,a,a,a,\ldots$ and $b,b,b,b, \ldots$ are equivalent if and only if $a=b$ ). This allows us to embed the rational numbers inside the real numbers in a well-defined manner.

Hints

For the “if” direction, prove by contradiction or contrapositive.

How to think about the exercise

I don’t have much to say; this is a pretty simple exercise. One comment I’ll make is that since we are working with the “equivalent sequences” definition, we have to deal with the three nested layers of quantifiers ( $\forall \varepsilon > 0\ \exists N\geq 1\ \forall n\geq N$ ). But here, our sequences don’t actually depend on $n$ . This makes it tempting to skip all the work of dealing with the quantifiers, but I think that’s wrong; we still have to unroll all the quantifiers.

Model solution

Suppose $a=b$ . Then given $\varepsilon > 0$ , pick $N:=1$ . So if $n \geq N$ we have $|a-b| = 0 < \varepsilon$ , which shows that $(a)_{n=1}^\infty$ and $(b)_{n=1}^\infty$ are equivalent.

Now suppose $a\ne b$ . We want to show that $(a)_{n=1}^\infty$ and $(b)_{n=1}^\infty$ are not equivalent. This means that we must find an $\varepsilon > 0$ such that for all $N \geq 1$ there exists $n \geq N$ such that $|a-b| > \varepsilon$ . Choose $\varepsilon := |a-b|/2$ , which is positive since $a\ne b$ . Let $N\geq 1$ . Then for $n = N$ we have $|a-b| > |a-b|/2 = \varepsilon$ .

Solutions

Exercise 5.3.2

March 26, 2020 Issa Rice 9 Comments

Exercise statement

Prove Proposition 5.3.10.

Proposition 5.3.10 (Multiplication is well defined). Let $x = \mathrm{LIM}_{n\to\infty} a_n$ , $y = \mathrm{LIM}_{n\to\infty} b_n$ , and $x' = \mathrm{LIM}_{n\to\infty} a'_n$ be real numbers. Then $xy$ is also a real number. Furthermore, if $x=x'$ , then $xy=x'y$ .

Hints

Proposition 4.3.7 may be useful.

How to think about the exercise

I think the tricky part about this exercise is choosing the right $\varepsilon$ (called $\varepsilon'$ in model solution 1) and $\delta$ for Proposition 4.3.7. Two general principles I have are:

Work backwards from the final expression, and don’t worry about all of the nested quantifiers until you are ready to write up the formal proof.
Use the $\min$ operator to require multiple constraints, so that you can avoid dealing with messy algebra.

How does this work on this exercise? Well, eventually I get to something like $\varepsilon'M_2 + \delta M_1 + \varepsilon'\delta$ and I want this to be at most $\varepsilon$ . How would I pick the right $\varepsilon', \delta$ ? Well, there are three terms, so it would be very convenient if I could get each term to come out to $\varepsilon/3$ . So looking at the first term, $\varepsilon'M_2 \leq \varepsilon/3$ which means $\varepsilon' \leq \frac{\varepsilon}{3M_2}$ . We might want to tack on another constraint, but at least for now we can put $\varepsilon' := \frac{\varepsilon}{3M_2}$ . Similarly, $\delta$ must be smaller than $\frac{\varepsilon}{3M_1}$ . Finally, we want $\varepsilon'\delta \leq \varepsilon/3$ . Here we have control over both factors, so there’s many ways to do this. The one that I chose was to simply require one of them to be smaller than $\varepsilon/3$ , and require the other one to be smaller than one.

Model solution 1

To show that $xy$ is a real number, we need to show that $(a_n b_n)_{n=1}^\infty$ is a Cauchy sequence. Let $\varepsilon > 0$ be given. Since $(a_n)_{n=1}^\infty$ is a Cauchy sequence, by Lemma 5.1.15 it is bounded, so there is a number $M_1 > 0$ which bounds it. Similarly, there is a number $M_2 > 0$ which bounds $(b_n)_{n=1}^\infty$ . Since $(a_n)_{n=1}^\infty$ is Cauchy, for $\varepsilon' := \min\left(\frac{\varepsilon}{3M_2}, \frac\varepsilon 3\right)$ we see that this sequence is eventually $\varepsilon'$ -steady. Similarly, since $(b_n)_{n=1}^\infty$ is Cauchy, for $\delta := \min\left(\frac{\varepsilon}{3M_1}, 1\right)$ the sequence is eventually $\delta$ -steady. Thus there exists $N\geq 1$ such that for all $j,k \geq N$ we have both of the following:

$a_j$ and $a_k$ are $\varepsilon'$ -close
$b_j$ and $b_k$ are $\delta$ -close

Thus, by Proposition 4.3.7(h) we see that $a_jb_j$ and $a_kb_k$ are $(\varepsilon'|b_j| + \delta|a_j| + \varepsilon'\delta)$ -close. If we can show that $\varepsilon'|b_j| + \delta|a_j| + \varepsilon'\delta \leq \varepsilon$ , this will prove that $(a_n b_n)_{n=1}^\infty$ is Cauchy. Term by term, we see that:

$\varepsilon'|b_j| \leq \varepsilon' M_2 \leq \frac{\varepsilon}{3M_2} \cdot M_2 = \frac\varepsilon3$
$\delta|a_j| \leq \delta M_1 \leq \frac{\varepsilon}{3M_1} \cdot M_1 = \frac\varepsilon3$
$\varepsilon'\delta \leq \frac\varepsilon 3 \cdot 1 = \frac\varepsilon3$

Thus adding the inequalities we see that $\varepsilon'|b_j| + \delta|a_j| + \varepsilon'\delta \leq \varepsilon$ as required.

Now we show that if $x=x'$ then $xy=x'y$ . Suppose $x=x'$ , so that $(a_n)_{n=1}^\infty$ and $(a'_n)_{n=1}^\infty$ are equivalent sequences. Since $(b_n)_{n=1}^\infty$ is a Cauchy sequence, there is some number $M > 0$ which bounds it. Now let $\varepsilon > 0$ . Then since $(a_n)_{n=1}^\infty$ and $(a'_n)_{n=1}^\infty$ are equivalent sequences, they are eventually $\varepsilon/M$ -close. Thus there exists $N\geq 1$ such that $a_n$ and $a'_n$ are $\varepsilon/M$ -close for each $n\geq N$ . Let $n\geq N$ . By Proposition 4.3.7(g), $a_nb_n$ and $a'_nb_n$ are $(\varepsilon/M)|b_n|$ -close. Thus if we can show that $(\varepsilon/M)|b_n| \leq \varepsilon$ , we will be done. But this follows from the fact that $|b_n| \leq M$ .

Model solution 2

In my opinion, there is a simpler way to do the first part where we show $xy$ is a real number. It doesn’t make use of Proposition 4.3.7 though.

The trick is to add and subtract the same term, so we have

$\begin{aligned}|a_jb_j - a_kb_k| &= |a_jb_j - a_jb_k + a_jb_k - a_kb_k| \\ &\leq |a_j||b_j-b_k| + |b_k||a_j - a_k|\end{aligned}$

We know we can get $|b_j-b_k|$ and $|a_j - a_k|$ small (since these sequences are Cauchy), and we can also bound $|a_j|$ and $|b_k|$ (since Cauchy sequences are bounded). Thus given bounds $M_1, M_2 > 0$ on $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ , respectively, and given an $\varepsilon > 0$ , choose $N$ large enough so that $|a_j - a_k| \leq \frac\varepsilon{2M_2}$ and $|b_j-b_k| \leq \frac\varepsilon{2M_1}$ for all $j,k \geq N$ . Now we have $|a_jb_j - a_kb_k| \leq \varepsilon$ for $j,k\geq N$ as required.