Category Archives: Solutions

Exercise 4.2.5

April 19, 2020 Issa Rice 3 Comments

Exercise statement

Prove Proposition 4.2.9.

Proposition 4.2.9 (Basic properties of order on the rationals). Let $x,y,z$ be rational numbers. Then the following properties hold.

(a) (Order trichotomy) Exactly one of the three statements $x=y$ , $x < y$ , or $x > y$ is true.
(b) (Order is anti-symmetric) One has $x < y$ if and only if $y > x$ .
(c) (Order is transitive) If $x < y$ and $y < z$ , then $x < z$ .
(d) (Addition preserves order) If $x < y$ , then $x+z < y+z$ .
(e) (Positive multiplication preserves order) If $x < y$ and $z$ is positive, then $xz < yz$ .

Hints

None.

How to think about the exercise

I want to say a few things about the definition of order on the rationals, and compare this definition to the definitions for the natural numbers and integers. None of what I say will be directly relevant to this exercise, but I think this is probably the best place to say these things (as opposed to saying these things in a post about a different exercise).

You might be wondering why the definition of order for the rationals is so different from the definitions for naturals and integers. A few things you might notice:

For rationals, the strict inequality $<$ is taken to be fundamental, whereas in the naturals and integers, the non-strict inequality $\leq$ is fundamental. By “fundamental”, I just mean that it’s the thing that’s defined in a “novel” way, rather than the one that’s defined by including or excluding the case of equality.
For rationals, order is defined using subtraction and with respect to positive and negative numbers, whereas for naturals and integers, it’s defined via addition by saying $a \geq b$ iff $a = b+n$ for some natural number $n$ .

For (1), mathematically this turns out to not be a very important distinction. We could have defined order on naturals and integers as follows: $a > b$ iff $a = b+n$ for a positive natural number $n$ ; indeed, this is exactly what Proposition 2.2.12(f) is about. Then we could have defined $a\geq b$ to mean $a>b$ or $a=b$ . Similarly, we could have defined order on rationals by saying that $x \leq y$ iff $x-y$ is either zero or negative. Then we could have defined $x < y$ to mean $x\leq y$ and $x\neq y$ .

So if there is an important distinction, I think it would have to be psychological (i.e. pedagogical). And here I’m not sure why Tao chose these particular definitions. The definition for rationals is slightly cleaner if one uses strict inequality, because otherwise one must include the “or zero” condition. And I think (but I’m not sure) that proving some of the results for natural numbers is easier if order is defined using non-strict inequality.

Moving onto (2), we have the “positive” concept for natural numbers, but we don’t have subtraction. So we can’t say $a > b$ iff $a-b$ is positive. But saying $a-b = n$ for some positive number $n$ is like saying $a = b+n$ for some positive number $n$ , so we are doing something similar even in the natural numbers case. For integers, we do have subtraction, so we indeed could have said that $a < b$ iff $a-b$ is negative, and $a > b$ iff $a-b$ is positive. This is actually precisely what Lemma 4.1.11(a) is about.

What about the other way around? For rationals, could we have defined $x > y$ to mean that $x = y + z$ for some positive $z$ ? As long as we allow $z$ to be rational (rather than just a positive integer), then I think this would work.

So to summarize, for (2), we could have defined order for the integers and rationals in whatever way we like, but for natural numbers we are restricted to not being able to use subtraction. I’m not sure why Tao decided to define order for the integers one way and for the rationals a different way.

Another question you might have is, how does the list of properties of order compare to the ones given in Lemma 4.1.11 and Proposition 2.2.12? Looking at Lemma 4.1.11, we see that its (a) is part of the definition of order for rationals (so we don’t need to prove it), its (b) we have, its (c) we have, its (d) appears in Exercise 4.2.6, its (e) we have, and its (f) we have. Lemma 4.1.11 doesn’t have anti-symmetry, but that’s actually part of the definition of order for integers.

Looking at Proposition 2.2.12, we see that its (a) follows trivially from the reflexivity of equality, its (b) we have (after some rewriting to deal with cases), its (c) we have (again after some rewriting), its (d) we have, its (e) we don’t have (but that doesn’t matter, since the notion of successor does not really matter for rationals), and its (f) we have (as long as we allow $d$ to be rational). Proposition 2.2.12 doesn’t have trichotomy (because there are no negative natural numbers), and for some reason Tao decided not to include the positive multiplication result (I’m not sure why).

Model solution

(a) Consider the number $x-y$ . By Lemma 4.2.7, this number is exactly one of zero, positive, or negative. But $x-y=0$ iff $x=y$ ; $x-y$ is positive iff $x > y$ ; and $x - y$ is negative iff $x < y$ . So each possibility in the order trichotomy corresponds to some possibility in the trichotomy of rationals. (If this reasoning makes you uncomfortable, you can also do this in the usual way, by first showing that at least one of the statements is true, and then showing that at most one of the statements is true. This would again make use of Lemma 4.2.7 extensively.)

(b) Suppose $x < y$ . By definition of order, this means that $x - y$ is negative, i.e. $x-y = (-a)/b$ for some positive integers $a$ and $b$ . Thus $y-x = -(x-y) = a/b$ is a positive number. By definition of order, this means $y > x$ as required.

The other direction is proved in the same way.

(c) Suppose $x < y$ and $y < z$ . Thus $x-y$ and $y-z$ are negative, which means that $x-y = (-a)/b$ and $y-z = (-c)/d$ for some positive integers $a,b,c,d$ . But now

$\begin{aligned}x-z &= (x-y)+(y-z) \\ &= (-a)/b + (-c)/d \\ &= (-ad-bc)/(bd) \\ &= (-(ad+bc))/(bd)\end{aligned}$

By Lemma 2.3.3 $ad$ , $bc$ , and $bd$ are all positive, and by Proposition 2.2.8 $ad+bc$ is positive. This means that $x-z$ is a negative rational, so $x < z$ as required.

(d) Suppose $x < y$ , so that $x-y$ is a negative number. But $(x+z) - (y+z) = x-y$ , so $x+z < y+z$ .

(e) Suppose $x < y$ and $z$ is positive. Then $x-y$ is negative. We thus have $x-y = (-a)/b$ and $z=c/d$ for positive integers $a,b,c,d$ . But now $xz-yz = (x-y)z = (-a)/b \times c/d = (-ac)/(bd)$ . Since $ac$ and $bd$ are positive by Lemma 2.3.3, we see that $(-ac)/(bd)$ is negative. Thus $xz < yz$ as required.

Solutions

Exercise 4.2.4

April 17, 2020 Issa Rice 1 Comment

Exercise statement

Prove Lemma 4.2.7.

Lemma 4.2.7 (Trichotomy of rationals). Let $x$ be a rational number. Then exactly one of the following three statements is true: (a) $x$ is equal to $0$ . (b) $x$ is a positive rational number. (c) $x$ is a negative rational number.

Hints

Note that, as in Proposition 2.2.13, you have to prove two different things: firstly, that at least one of (a), (b), (c) is true; and secondly, that at most one of (a), (b), (c) is true.

How to think about the exercise

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

Model solution

Let $x = a//b$ be a rational number, where $a$ is an integer and $b$ is a non-zero integer. First we show that at least one of (a), (b), (c) is true. If $a=0$ , then $x=0$ . If $a \ne 0$ , then by trichotomy of integers $a$ is positive or negative. Similarly, $b$ is positive or negative. So we have four cases:

Both $a,b$ are positive: We see that $x = a//b = a/b$ , so $x$ is positive.
$a$ is negative and $b$ is positive: We see that $-a$ is positive, so $(-a)//b$ is positive. But $x = -((-a)//b)$ , so $x$ is negative.
$a$ is positive and $b$ is negative: Then $-b$ is positive so $a//(-b)$ is positive. We have $x = -(a//(-b))$ so $x$ is negative.
Both $a,b$ are negative: Then $-a$ and $-b$ are both positive, so $(-a)//(-b)$ is positive. But $(-a)//(-b) = a//b =x$ so $x$ is positive.

Thus, in each case $x$ is zero, positive, or negative.

Now we show that at most one of (a), (b), (c) is true. Suppose for sake of contradiction that $x$ is equal to zero and is also positive. Thus $x = c//d = 0//1$ for positive integers $c,d$ . But this means $c1 = 0d$ , i.e. $c = 0$ . This contradicts the trichotomy for integers, since $c$ cannot be both positive and equal to zero. Thus we conclude that $x$ cannot be both positive and equal to zero.

Similarly, $x$ cannot be equal to zero and also negative, since this would imply that $x = (-c)//d = 0//1$ for positive integers $c,d$ , which would mean $-c = 0$ , i.e. $c=0$ .

Finally we show that $x$ cannot be both positive and negative. Suppose $x = (-c)//d = e//f$ where $c,d,e,f$ are all positive integers. Thus $-cf = ed$ . By Lemma 2.3.3, $cf$ and $ed$ are positive, so $-cf$ is negative. But this means that $-cf$ is both positive and negative, which contradicts the trichotomy of integers. Thus $x$ cannot be both positive and negative after all.

Solutions

Exercise 4.2.3

April 16, 2020 Issa Rice 1 Comment

Exercise statement

Prove the remaining components of Proposition 4.2.4.

Proposition 4.2.4 (Laws of algebra for rationals). Let $x,y,z$ be rationals. Then the following laws of algebra hold:

$x+y = y+x$
$(x+y) + z = x + (y+z)$
$x+0 = 0+x = x$
$x + (-x) = (-x) + x = 0$
$xy = yx$
$(xy)z = x(yz)$
$x1 = 1x = x$
$x(y+z) = xy+xz$
$(y+z)x = yx + zx$

If $x$ is non-zero, we also have

$xx^{-1} = x^{-1}x = 1$

Hints

As with Proposition 4.1.6, you can save some work by using some identities to prove others.

How to think about the exercise

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

Model solution

Let $x = a//b$ , $y = c//d$ , and $z=e//f$ for integers $a,c,e$ and non-zero integers $b,d,f$ .

First we show that $x+y = y+x$ . We have $x+y = (ad+bc)//(bd)$ and $y+x = (cb+da)//(db) = (ad+bc)//(bd)$ . So we see that the two are equal.

The law $(x+y) + z = x + (y+z)$ was already shown in the book.

Next we show $x+0 = 0+x = x$ . Since we already showed addition is commutative, we already know that $x+0=0+x$ . Thus we just need to show that $0+x = x$ . We have $0+x = 0//1 + a//b = (0b+1a)//(1b) = a//b = x$ as required.

Next we have to show $x + (-x) = (-x) + x = 0$ . By commutativity of addition, we get $x + (-x) = (-x) + x$ , so we can just show $(-x) + x = 0$ . We have $(-x) +x = (-a)//b + a//b = (-ab + ba)//(b^2) = 0//(b^2)$ . We have $0//(b^2) = 0//1$ since $0\times 1 = 0b^2$ . Thus $(-x)+x = 0$ as desired.

Next we show that $xy = yx$ . We have $xy = (ac)//(bd)$ and $yx = (ca)//(db) = (ac)//(bd)$ . Thus the two are equal.

Next we show that $(xy)z = x(yz)$ . We have $(xy)z = (ace)//(bdf) = x(yz)$ .

Next we show that $x1 = 1x = x$ . By commutativity of multiplication, we have $x1 = 1x$ , so we just need to show that $1x = x$ . We have $1x = (1a)//(1b) = a//b = x$ .

Next we show that $x(y+z) = xy+xz$ . We have

$\begin{aligned}x(y+z) &= (a//b)\times (c//d + e//f) \\ &= (a//b) \times (cf +de)//(df) \\ &= (acf + ade)//(bdf)\end{aligned}$

$\begin{aligned}xy + xz &= (a//b)(c//d) + (a//b)(e//f) \\ &= (ac)//(bd) + (ae)//(bf) \\ &= (acbf + bdae)//(b^2df) \\ &= (acf + dae)//(bdf)\end{aligned}$

Thus the two are equal.

Next we show that $(y+z)x = yx + zx$ . This follows from commutativity of multiplication and the first form of the distributive law, both of which were proved above. We have $(y+z)x = x(y+z) = xy+xz = yx+zx$ .

Finally, suppose $x \ne 0$ . We want to show that $xx^{-1} = x^{-1}x = 1$ . The first equality follows from the commutativity of multiplication. For the second equality, we have $x^{-1}x = (b//a)(a//b) = (ba)//(ab)$ . And $(ba)//(ab) = 1//1$ since $ba=ab$ .

Solutions

Exercise A.7.1

April 15, 2020 Issa Rice Leave a comment

Exercise statement

Suppose you have four real numbers $a,b,c,d$ and you know that $a=b$ and $c=d$ . Use the above four axioms to deduce that $a+d=b+c$ .

Hints

None.

How to think about the exercise

So we have $a=b$ and $c=d$ . We want $a+d=b+c$ . Since we want $a+d = \text{something}$ , we can start by adding $d$ to the equation involving $a$ . This yields $a+d=b+d$ . We could also have added $a$ to both sides of $c=d$ , to get $a+c=a+d$ .

Now what? We want $\text{something} = b+c$ , so we can add $c$ to both sides of $a=b$ to get $a+c=b+c$ . Or we could have added $b$ to both sides of $c=d$ to get $b+c=b+d$ .

Now we’ve over-solved the problem. We could take $a+d=b+d$ and $b+c=b+d$ to get what we want, or we could also take $a+c=a+d$ and $a+c=b+c$ .

Model solution

Since $a=b$ , we have $a+d = b+d$ . Formally, we define a function $f : \mathbf R\to \mathbf R$ by $f(x) := x+d$ . Since $a=b$ , we must have $f(a) = f(b)$ , i.e. $a+d=b+d$ . (Strictly speaking, we would need to say that $f(a) = a+d$ , so by symmetry, $a+d=f(a)$ . Since $f(a)=f(b)$ , by transitivity we have $a+d=f(b)$ . And since $f(b)=b+d$ , by transitivity again we have $a+d=b+d$ . We shall skip this in the following.)

Analogously, since $c=d$ we have $b+c = b+d$ . By symmetry, we have $b+d=b+c$ . So by transitivity we have $a+d = b+c$ as desired.

Solutions

Exercise A.5.1

April 15, 2020 Issa Rice Leave a comment

Exercise statement

What does each of the following statements mean, and which of them are true? Can you find gaming metaphors for each of these statements?

(a) For every positive number $x$ , and every positive number $y$ , we have $y^2=x$ .
(b) There exists a positive number $x$ such that for every positive number $y$ , we have $y^2=x$ .
(c) There exists a positive number $x$ , and there exists a positive number $y$ , such that $y^2=x$ .
(d) For every positive number $y$ , there exists a positive number $x$ such that $y^2=x$ .
(e) There exists a positive number $y$ such that for every positive number $x$ , we have $y^2=x$ .

Hints

None.

How to think about the exercise

I think this is a pretty simple exercise, but that’s possibly only because I’ve gotten used to thinking about nested quantifiers. If you find this confusing, you might want to find a book on proofs, such as Velleman’s How to Prove It.

Model solution

(a) False. This is saying that every positive number is the square of every positive number. That can’t be right, since most of the time, if one picks two positive numbers, one of them isn’t the square of the other. Consider $x=1$ and $y=2$ . Then we have $y^2 = 4 \ne 1 = x$ . In terms of the gaming metaphor, your opponent hands you two positive numbers $x,y$ , and you win if $y^2=x$ . You don’t get to interact in this game; your opponent chooses two numbers, and that determines the outcome of the game. Obviously, you can’t always win this game since your opponent can choose one number, and then choose a different number which is not the square of the first number.

(b) False. This is saying that there is a single number which is the square of every positive number. But that can’t be right, since if two positive numbers are distinct, then their squares are also distinct. To prove this, suppose for contradiction that such an $x$ exists. Then in particular for $y=1$ and $y=2$ we must have $1^2 = x$ and $2^2=x$ . Thus $1=4$ , a contradiction. This contradiction shows that the statement must have been false. In terms of the gaming metaphor, you are asked to present a number $x$ . Then your opponent gets to pick a number $y$ . You win if $y^2 = x$ . Obviously you can’t always win, since your opponent gets to see your number and pick one which doesn’t square to yield your number. For instance, your opponent can pick $y:= x+1$ .

(c) True. This is saying that there are two positive numbers, one of which is the square of the other. That’s clearly true, since we can just take any positive number, then square it to get a positive number. In particular, take $x=4$ and $y=2$ . Then $y^2 = 4 = x$ . In terms of the gaming metaphor, the game begins as your move, and you get to pick two numbers. Your opponent doesn’t get to move. You can always win the game, just by picking two numbers that work.

(d) True. This is saying that every positive number can be squared to yield a positive number. So this statement is saying that every positive number has a positive square. This is true, since a positive number times a positive number is a positive number. In terms of the gaming metaphor, your opponent hands you a positive number, and you have to find a positive number which is its square; you can always win regardless of the number your opponent hands you, since you can just square your opponent’s number.

(e) False. This is saying that there is a single number which is the positive square root of every positive number. This can’t be right, since distinct positive numbers have distinct positive square roots. To prove this, suppose for sake of contradiction that such a $y$ existed. Then in particular for $x=1$ and $x=4$ we must have $y^2 = 1$ and $y^2=4$ . Thus $1=4$ , a contradiction. In terms of the gaming metaphor, you are asked to pick a number $y$ , then your opponent picks a number $x$ . You win if $y^2 = x$ . Obviously you can’t always win, since your opponent gets to see your number. For instance, your opponent can square your number and add one to get a different number.

Solutions

Exercise A.1.6

April 14, 2020 Issa Rice 5 Comments

Exercise statement

Suppose you know that whenever $X$ is true, then $Y$ is true; that whenever $Y$ is true, then $Z$ is true; and whenever $Z$ is true, then $X$ is true. Is this enough to show that $X, Y, Z$ are all logically equivalent? Explain.

Hints

None.

How to think about the exercise

Once you’ve done this exercise and the previous one, you might be wondering if there’s a general rule for figuring out when a given list of statements consists of logically equivalent statements. Here’s one attempt. Draw all the statements as nodes on a graph, then write a directed edge whenever there is an implication. For this exercise you end up with the following graph:

Now what you have to ask is, starting at any node, can I get to any other node? In this case it’s pretty clear that yes, you can do that. So this means the three statements are equivalent.

Suppose we are given a more complicated implication structure like the following:

How can we tell if all of these statements are logically equivalent? Well, one way is to just check one by one. Starting at $A$ , can I get to every other node? $B, C, D, F, E$ . So yes. Now starting at $B$ , … and so on. At the end you will get a yes or no answer (the answer is “no”).

But there is a better way to go about this, which is to detect subsets of the nodes which are logically equivalent, and then join them together into a single node. For instance, we can see immediately that $A$ and $B$ are logically equivalent, so we can join those two nodes together:

And now, we see that $A=B$ , $F$ , and $E$ form a cycle, so they are logically equivalent (starting from anywhere in a cycle, you can go around to reach each of the other spots). So we can join them together:

We can say we are done here, but notice that there are two ways to get from $A=B=E=F$ to $D$ : we can go directly or we can go via $C$ . We don’t really need the former arrow, since we can still get to $D$ even if we erase it. (On the other hand, we can’t get rid of the arrow pointing to $C$ , since then there would be no way to get to $C$ , so the implication structure will have changed.) So we can erase it to make the graph slightly cleaner:

Now it is pretty clear what is going on. The statements $A,B,E,F$ are all logically equivalent, and they are the strongest statements, because they imply everything else. Then comes $C$ , which implies $D$ but not the other statements. Finally there is $D$ , which does not imply any other the other statements.

Unlike the first method, which just gave a yes or no answer, this second method tells you more, because it gives you a subset of the statements which is logically equivalent, and also tells you the strengths of the statements more generally.

Model solution

Yes, this is enough to show that $X, Y, Z$ are all logically equivalent. If $X$ is true, then $Y$ is true. And since $Y$ is true, we see that $Z$ is true. Thus whenever $X$ is true, the other two statements are also true. Similarly, we can show that whenever $Y$ is true, $Z$ and $X$ are also true, and that whenever $Z$ is true, $X$ and $Y$ are also true. This means that whenever one of the statements is true, the other two are both true.

If $X$ is false, then $Z$ is false (if $Z$ were true, then $X$ would have to be true, which would contradict the fact that $X$ is false). And since $Z$ is false, we see that $Y$ is false. Thus whenever $X$ is false, the other two statements are also false. A similar reasoning shows that whenever one of the statements is false, the other two are also false.

Solutions

Exercise A.1.5

April 14, 2020 Issa Rice 1 Comment

Exercise statement

Suppose you know that $X$ is true if and only if $Y$ is true, and you know that $Y$ is true if and only if $Z$ is true. Is this enough to show that $X, Y, Z$ are all logically equivalent? Explain.

Hints

None.

How to think about the exercise

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

Model solution

Yes, $X, Y, Z$ are all logically equivalent. If $X$ is true, then $Y$ is true since $X\iff Y$ . And since $Y$ is true, $Z$ is true since $Y \iff Z$ . Thus if $X$ is true, then both of the other two statements are true. We can use similar reasoning to show that if $Y$ is true, then both of the other two statements are true, and if $Z$ is true, then both of the other two statements are true. Thus, if one of the statements is true, then the other two are also true.

If $X$ is false, then $Y$ is false since $X \iff Y$ . And since $Y$ is false, $Z$ is false since $Y\iff Z$ . Thus if $X$ is false, then the other two statements are false. We can use similar reasoning to show that if any of the statements is false, then the other two must also be false.

The three statements are logically equivalent, since whenever one of them is true, the other two are also true, and whenever one of them is false, the other two are also false.

Solutions

Exercise A.1.4

April 14, 2020 Issa Rice 3 Comments

Exercise statement

Suppose that you have shown that whenever $X$ is true, then $Y$ is true, and whenever $Y$ is false, then $X$ is false. Have you now demonstrated that $X$ is true if and only if $Y$ is true? Explain.

Hints

None.

How to think about the exercise

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

Model solution

No, we have not demonstrated that $X$ is true if and only if $Y$ is true. We are given $X \implies Y$ and $\neg Y \implies \neg X$ . But $\neg Y \implies \neg X$ is logically equivalent to $X\implies Y$ (since the latter is just the contrapositive). In other words, we are only given that $X \implies Y$ , so there is no way to conclude that $X \iff Y$ .

Here is an example that shows that we can satisfy both of the conditions in the exercise statement, but still have $X$ and $Y$ not be logically equivalent: Let $x$ be a real number, let $X$ be the statement $x > 0$ , and let $Y$ be the statement $x \geq 0$ . So if $X$ is true, then $Y$ is true (since every positive real number is non-negative). Also, whenever $Y$ is false, then $X$ is false (since every negative number is not positive). But it is not the case that $X$ is true if and only if $Y$ is true, since for $x=0$ we see that $X$ is false and $Y$ is true.

Solutions

Exercise A.1.3

April 14, 2020 Issa Rice Leave a comment

Exercise statement

Suppose that you have shown that whenever $X$ is true, then $Y$ is true, and whenever $X$ is false, then $Y$ is false. Have you now demonstrated that $X$ and $Y$ are logically equivalent? Explain.

Hints

None.

How to think about the exercise

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

Model solution

Yes. We will show that $X$ is true if and only if $Y$ is true. If $X$ is true, then $Y$ is true by what was given in the exercise statement. Conversely, suppose $Y$ is true. We need to show that $X$ is true. Suppose for sake of contradiction that $X$ is false. Then by what was given in the exercise statement, we see that $Y$ is false. But now $Y$ is both true and false, a contradiction. Thus the assumption that $X$ is false was wrong, so $X$ must be true.

Another way to see this is that we are given that $X \implies Y$ and $\neg X \implies \neg Y$ . But the contrapositive of $\neg X \implies \neg Y$ is $Y \implies X$ . Since the contrapositive of an implication is logically equivalent to it, this means that we have both $X\implies Y$ and $Y\implies X$ , i.e. $X \iff Y$ .