Category Archives: Solutions

Exercise A.1.1

April 13, 2020 Issa Rice 1 Comment

Exercise statement

What is the negation of the statement “either $X$ is true, or $Y$ is true, but not both”?

Hints

None.

How to think about the exercise

Tao does not discuss truth tables, but I think they are the easiest way to work through these kinds of exercises systematically. For this exercise, we have:

X	Y	X or Y but not both	negation of previous column
T	T	F	T
T	F	T	F
F	T	T	F
F	F	F	T

So as you can see, the negation of the statement in question is true when both $X$ and $Y$ are true, or when both $X$ and $Y$ are false. This is the same thing as saying $X \iff Y$ .

The alternative way to do this exercise is to make use of your verbal abilities. We want to negate “either $X$ is true, or $Y$ is true, but not both”. This is the same as saying ( $X$ is true or $Y$ is true) and not ( $X$ is true and $Y$ is true). So negating this, we have: ( $X$ is false and $Y$ is false) OR (both $X$ and $Y$ are true). In other words, both $X$ and $Y$ are false, or both $X$ and $Y$ are true, i.e. $X$ and $Y$ must have the same truth value.

Model solution

Here are two natural ways to state the negation:

$X$ is true if and only if $Y$ is true.
$X$ and $Y$ have the same truth value.

Solutions

Exercise 4.2.2

April 12, 2020 Issa Rice Leave a comment

Exercise statement

Prove the remaining components of Lemma 4.2.3.

Lemma 4.2.3. The sum, product, and negation operations on rational numbers are well-defined, in the sense that if one replaces $a//b$ with another rational number $a'//b'$ which is equal to $a//b$ , then the output of the above operations remains unchanged, and similarly for $c//d$ .

Hints

You might want to review the proofs for Lemma 4.1.3 and Exercise 4.1.2.

How to think about the exercise

I don’t think Tao’s book ever gives an example of an operation which is not well-defined. (I didn’t check all parts of the book, so I might be wrong about this.) Assuming there is no such example, I think this is a pedagogical mistake, so I want to correct that here (partly because it’s especially easy to give an example of an ill-defined operation on the rationals). Why would I do this? There are two reasons:

It’s good to see both positive and negative examples.
From doing exercises like this one, you might get the mistaken impression that basically all operations are well-defined, and that checking well-definedness is a trivial bureaucratic activity.

So with that out of the way, here is my example: Let $a//b$ and $c//d$ be rational numbers. Then we define their component-wise sum to be $(a//b) \oplus (c//d) := (a+c)//(b+d)$ . In other words, the component-wise sum of two rational numbers is the sum of the numerators “divided by” the sum of the denominators. (Remember, this definition is ill-defined, so no such operation actually exists!)

First, let’s quickly check that this definition is ill-defined. We have $1//2 = 2//4$ but $(1//2) \oplus (1//3) = 2//5$ and $(2//4) \oplus (1//3) = 3//7$ . Are these two rationals equal? Well, $2\times 7 = 14 \ne 15 = 3\times 5$ . Even a single example where the outputs are different proves that the operation is not well-defined.

Now, we can try a different approach. Let’s try to prove that component-wise addition is well-defined. Since component-wise addition is not well-defined, we must get stuck somewhere in the proof. The upshot is that checking an operation is well-defined (such as for addition and multiplication) is not trivial: there is something real happening there, which can’t happen for bogus operations like component-wise addition.

Ok, let’s go: Suppose $a//b = a'//b'$ , so that $ab' = a'b$ . Now $(a//b) \oplus (c//d) = (a+c)//(b+d)$ and $(a'//b') \oplus (c//d) = (a'+c)//(b'+d)$ . To show that these are equal, we must show $(a+c)(b'+d) = (a'+c)(b+d)$ . Expanding this, we have $(a+c)(b'+d) = ab' + ad + cb' + cd$ and $(a'+c)(b+d) = a'b + a'd + cb + cd$ . The first term in each is the same, since $ab' = a'b$ . Also, the final term in each is $cd$ . So it suffices to show that $ad + cb' = a'd + cb$ . How can we do this? We can’t! There is nothing in our assumption $ab' = a'b$ or in the properties of the integers that allows us to conclude this. We are stuck, and for a good reason (since the operation is ill-defined).

We can plug in the numbers from above to check this. We have

$\begin{aligned}ab' + ad + cb' + cd &= 1\cdot 4 + 1\cdot 3 + 1\cdot 4 + 1\cdot 3 \\ &= 4 + 3 + 4 + 3\end{aligned}$

$\begin{aligned}a'b + a'd + cb + cd &= 2\cdot 2 + 2\cdot 3 + 1\cdot 2 + 1\cdot 3 \\ &= 4 + 6 + 2 + 3\end{aligned}$

So indeed the first and last terms are the same, and the middle two terms are totally different (even when added together).

Model solution

Sum: this was done in the book.

Product: Suppose $a//b = a'//b'$ , so that $b,b'$ are non-zero and $ab' = a'b$ . We want to show that $(a//b)\times (c//d) = (a'//b') \times (c//d)$ . The left side is $(ac)//(bd)$ and the right side is $(a'c)//(b'd)$ . So we want to show that $acb'd = a'cbd$ . But $ab' = a'b$ so multiplying by $cd$ we have $ab'cd = a'bcd$ , which is what we want (after reordering the factors). Similarly if $c//d = c'//d'$ then $cd' = c'd$ . Now $(a//b)\times (c//d) = (ac)//(bd)$ and $(a//b)\times (c'//d') = (ac')//(bd')$ so we want to show that $acbd' = ac'bd$ , which we have since $cd'=c'd$ .

Negation: Suppose $a//b = a'//b'$ , so that $ab' = a'b$ . We have $-(a//b) = (-a)//b$ and $-(a'//b') = (-a')//b'$ by definition of negation. We thus have to show that $(-a)//b = (-a')//b'$ , i.e. $(-a)b' = (-a')b$ . But this follows from multiplying both sides of the equation $ab' = a'b$ by $-1$ and using Exercise 4.1.3.

Solutions

Exercise 4.2.1

April 11, 2020 Issa Rice 2 Comments

Exercise statement

Show that the definition of equality for the rational numbers is reflexive, symmetric, and transitive.

Hints

For transitivity, use Corollary 4.1.9.
Corollary 4.1.9 only works when the number you are cancelling is non-zero!

How to think about the exercise

This is a pretty straightforward exercise. If this exercise feels difficult, you might want to review Exercise 4.1.1.

Model solution

Let $x,y,z$ be rational numbers. Thus there exist integers $a,b,c,d,e,f$ , with $b,d,f$ non-zero, such that $x = a//b$ , $y=c//d$ , and $z=e//f$ .

Reflexive: We must show $x=x$ , i.e. $a//b = a//b$ . But by definition of equality, $a//b = a//b$ means $ab=ab$ , which is the case since equality is reflexive for integers.

Symmetric: We must show that $x=y$ implies $y=x$ . So suppose $x=y$ . This means that $a//b = c//d$ , i.e. $ad = cb$ . To show $y=x$ we must show $c//d = a//b$ , i.e. $cb = ad$ . Since equality for integers is symmetric, we see that $ad = cb$ implies $cb=ad$ , so we are done.

Transitive: Suppose $x=y$ and $y=z$ . We must show that $x=z$ . Since $x=y$ we see that $a//b = c//d$ , i.e. $ad = cb$ , and since $y=z$ we see that $c//d = e//f$ , i.e. $cf = ed$ . By multiplying the first equality by $cf$ we have $(ad)(cf) = (cb)(cf)$ , and by multiplying the second equality by $cb$ we have $(cb)(cf) = (cb)(ed)$ . Since equality on the integers is transitive, we have $adcf = cbed$ . But $d$ is non-zero, so by Corollary 4.1.9 we have $acf = cbe$ . Now we have two cases. If $c\ne 0$ , we can use Corollary 4.1.9 again to obtain $af = eb$ , i.e. $a//b = e//f$ . On the other hand, if $c=0$ then $ad=cb$ so $ad=0$ , and since $d\ne 0$ , Proposition 4.1.8 implies that $a=0$ . Similarly, $cf=ed$ so $c=0$ means that $ed=0$ , so $e=0$ since $d$ cannot be zero. Thus $af = 0 = eb$ , which means $a//b = e//f$ . In either case, $x=z$ , so we are done.

Solutions

Exercise 4.1.7

April 10, 2020 Issa Rice 3 Comments

Exercise statement

Prove Lemma 4.1.11.

Lemma 4.1.11 (Properties of order). Let $a, b, c$ be integers.

(a) $a>b$ if and only if $a-b$ is a positive natural number.
(b) (Addition preserves order) If $a>b$ , then $a+c > b+c$ .
(c) (Positive multiplication preserves order) If $a>b$ and $c$ is positive, then $ac > bc$ .
(d) (Negation reverses order) If $a>b$ , then $-a<-b$ .
(e) (Order if transitive) If $a>b$ and $b>c$ , then $a>c$ .
(f) (Order trichotomy) Exactly one of the statements $a>b$ , $a<b$ , or $a=b$ is true.

Hints

Use the first part of this lemma to prove all the others.
You might find Exercise 4.1.3 helpful.

How to think about this exercise

This is a straightforward exercise as long as you follow the hints.

Model solution

(a) Suppose $a>b$ . This means that $a\geq b$ and $a\ne b$ . Since $a\geq b$ , we have $a = b+n$ for some natural number $n$ . Add $-b$ to both sides of this equation to obtain $a-b = b+n + (-b) = b+ (-b) + n = n$ , where the last two equalities follow from the laws of algebra (Proposition 4.1.6). Thus $a-b$ is equal to a natural number. If $n=0$ , then $a-b=0$ so $a=b$ , a contradiction. Thus $n\ne 0$ , which means $a-b$ is a positive natural number.

Now suppose $a-b$ is a positive natural number. Thus $a-b = n$ , where $n\ne 0$ is a natural number. By adding $b$ to both sides we obtain $a-b + b = n+b$ , i.e. $a = b+n$ . Thus $a\geq b$ . If $a=b$ then we would have $0=a-b = n$ , which contradicts the fact that $n\ne 0$ . Thus $a\ne b$ , which together with $a\geq b$ implies that $a>b$ .

(b) Suppose $a>b$ . By part (a), this means $a-b$ is a positive natural number. By the laws of algebra, $a-b = a-b + c + (-c) = (a+c) + (-b) + (-c)$ . By Exercise 4.1.3, $-b = (-1)b$ and $-c = (-1)c$ . Thus $(-b) + (-c) = (-1)b + (-1)c = (-1)(b+c) = -(b+c)$ , where we have used the distributive law. We thus have $a-b = (a+c) - (b+c)$ . Since this is a positive natural number, by part (a) again we see that $a+c > b+c$ .

(c) Suppose $a>b$ and $c$ is positive. By part (a), we see that $a-b$ is positive. Thus by Lemma 2.3.3 we see that $(a-b)c$ is positive. We have $(a-b)c = (a + (-b))c = ac + (-b)c = ac + (-1)bc = ac-bc$ , where we have used the distributive law and Exercise 4.1.3. Since $ac-bc$ is positive, by part (a) again we see that $ac > bc$ .

(d) Suppose $a>b$ . Thus by part (a) we see that $a-b$ is positive. To show that $-a < -b$ , we need to show that $(-b) - (-a)$ is positive. But $(-b) - (-a) = (-b) + (-1)(-1)a = (-1)(-1)a + (-b)$ . We have $(-1)(-1) = (0{{-}\!{-}}1)(0{{-}\!{-}}1) = 1{{-}\!{-}}0 = 1$ . Thus $(-1)(-1)a + (-b) = a-b$ . Since $a-b$ is positive, and $a-b = (-b)-(-a)$ , we see that $(-b)-(-a)$ is positive as required.

(e) Suppose $a>b$ and $b>c$ . Thus by part (a), we see that $a-b$ and $b-c$ are positive. By Proposition 2.2.8, we thus see that $(a-b) + (b-c) = a-c$ is a positive number. By part (a) again, we thus see that $a>c$ as desired.

(f) We first show that at least one of $a>b$ , $a<b$ , or $a=b$ is true. Consider the integer $a-b$ . By trichotomy (Lemma 4.1.5) it is zero, positive, or negative. If $a-b=0$ then $a=b$ . If $a-b$ is positive then by part (a), we have that $a>b$ . If $a-b$ is negative, then $a-b = -n$ for some positive natural number $n$ , so $-(a-b) = n$ is positive. But $-(a-b) = b-a$ , so by part (a) we have $b > a$ .

Now we show that at most one of $a>b$ , $a<b$ , or $a=b$ is true. If $a>b$ and $a<b$ then $a-b$ and $b-a = -(a-b)$ are both positive. But if $-(a-b)$ is positive then $-(a-b) = n$ for positive natural number $n$ , so $a-b = -n$ , i.e. $a-b$ is negative. Thus $a-b$ is both positive and negative, which contradicts the trichotomy of integers. If $a>b$ and $a=b$ then we have both $a\ne b$ and $a=b$ , a contradiction. Similarly we cannot have both $a<b$ and $a=b$ .

Solutions

Exercise 4.1.4

April 9, 2020 Issa Rice 2 Comments

Exercise statement

Prove the remaining identities in Proposition 4.1.6.

Proposition 4.1.6 (Laws of algebra for integers). Let $x,y,z$ be integers. Then we have

$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$

Hints

One can save some work by using some identities to prove others. For instance, once you know that $xy=yx$ , you get for free that $x1=1x$ , and once you also prove $x(y+z) = xy+xz$ , you automatically get $(y+z)x = yx + zx$ for free.

How to think about the exercise

This is the sort of exercise where, even if you know exactly what you are doing, you might slip up and make a mistake shuffling symbols around. I would say to not worry about making small errors like that, as long as you can get most of them right. I checked my work a couple of times, but it’s possible that I’ve made such errors below.

Model solution

Write $x = (a{{-}\!{-}}b)$ , $y=(c{{-}\!{-}}d)$ , and $z = (e{{-}\!{-}}f)$ .

First we show that $x+y = y+x$ . We have $x+y = (a{{-}\!{-}}b)+(c{{-}\!{-}}d) = (a+c){{-}\!{-}}(b+d)$ and $y+x = (c{{-}\!{-}}d)+(a{{-}\!{-}}b) = (c+a){{-}\!{-}}(d+b) = (a+c){{-}\!{-}}(b+d)$ , where the last equality follows from the commutativity of addition on the natural numbers. Thus one sees that $x+y=y+x$ .

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

$\begin{aligned}(x+y) + z &= ((a{{-}\!{-}}b) + (c{{-}\!{-}}d)) + (e{{-}\!{-}}f) \\ &= ((a+c){{-}\!{-}}(b+d)) + (e{{-}\!{-}}f) \\ &= (a+c+e){{-}\!{-}}(b+d+f)\end{aligned}$

$\begin{aligned}x + (y+z) &= (a{{-}\!{-}}b) + ((c{{-}\!{-}}d) + (e{{-}\!{-}}f)) \\ &= (a{{-}\!{-}}b) + ((c+e){{-}\!{-}}(d+f)) \\ &= (a+c+e){{-}\!{-}}(b+d+f)\end{aligned}$

Thus we see that $(x+y) + z = x + (y+z)$ .

Next we show that $x+0 = 0+x = x$ . We showed the commutativity of addition above, so $x+0 = 0+x$ . So we just need to show $0+x = x$ . We have $0+x = (0{{-}\!{-}}0)+(a{{-}\!{-}}b) = (0+a){{-}\!{-}}(0+b) = a{{-}\!{-}}b = x$ .

Next we show $x + (-x) = (-x) + x = 0$ . By commutativity of addition, we have $x + (-x) = (-x) + x$ . So we just need to show that $(-x) + x = 0$ . We have

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

But $(a+b){{-}\!{-}}(a+b) = (0{{-}\!{-}}0)$ since $(a+b)+0 = 0+(a+b)$ .

Next we show that $xy = yx$ . We have $xy = (a{{-}\!{-}}b)(c{{-}\!{-}}d) = (ac+bd){{-}\!{-}}(ad+bc)$ and

$\begin{aligned}yx &= (c{{-}\!{-}}d)(a{{-}\!{-}}b) \\ &= (ca+db){{-}\!{-}}(cb+da) \\ &= (ac+bd){{-}\!{-}}(ad+bc)\end{aligned}$

Thus the two sides are equal, and we have $xy=yx$ .

The associativity of multiplication, $(xy)z = x(yz)$ , was already shown in the book.

Next we show that $x1 = 1x = x$ . We have $x1 = 1x$ by the commutativity of multiplication, which was shown above. Thus we can just show $1x=x$ . We have $1x = (1{{-}\!{-}}0)(a{{-}\!{-}}b) = (a{{-}\!{-}}b) = x$ .

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

$\begin{aligned}x(y+z) &= (a{{-}\!{-}}b)((c{{-}\!{-}}d) + (e{{-}\!{-}}f)) \\ &= (a{{-}\!{-}}b)((c+e){{-}\!{-}}(d+f)) \\ &= (a(c+e) + b(d+f)){{-}\!{-}}(a(d+f) + b(c+e)) \\ &= (ac+ae+bd+bf){{-}\!{-}}(ad+af+bc+be)\end{aligned}$

$\begin{aligned}xy+xz &= (a{{-}\!{-}}b)(c{{-}\!{-}}d) + (a{{-}\!{-}}b)(e{{-}\!{-}}f) \\ &= ((ac+bd){{-}\!{-}}(ad+bc)) + ((ae+bf){{-}\!{-}}(af+be)) \\ &= (ac+bd + ae+bf){{-}\!{-}}(ad+bc + af+be) \\ &= (ac+ae+bd+bf){{-}\!{-}}(ad+af+bc+be)\end{aligned}$

The two sides are equal, so $x(y+z) = xy+xz$ .

Finally, we show that $(y+z)x = yx + zx$ . We have $(y+z)x = x(y+z) = xy+xz = yx+zx$ by the commutativity of multiplication, the distributive law, and commutativity again, all of which were shown earlier in the proof.

Solutions

Exercise 3.1.3

April 8, 2020 Issa Rice 10 Comments

Exercise statement

Prove the remaining claims in Lemma 3.1.13.

Lemma 3.1.13. If $a$ and $b$ are objects, then $\{a,b\} = \{a\} \cup \{b\}$ . If $A,B,C$ are sets, then the union operation is commutative (i.e., $A\cup B = B\cup A$ ) and associative (i.e., $(A\cup B)\cup C = A\cup (B\cup C)$ ). Also, we have $A\cup A = A\cup \emptyset = \emptyset \cup A = A$ .

Hints

None (this is a simple exercise).

How to think about the exercise

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

Model solution

First we show that $\{a,b\} = \{a\} \cup \{b\}$ . By Definition 3.1.4, we need to show that every element of $\{a,b\}$ is an element of $\{a\} \cup \{b\}$ , and vice versa. Suppose that $x$ is an element of $\{a,b\}$ . Then by Axiom 3.3 we see that $x=a$ or $x=b$ . If $x=a$ then $x$ is in $\{a\}$ . Thus by Axiom 3.4 we see that $x \in \{a\} \cup \{b\}$ . On the other hand if $x=b$ then $x \in \{b\}$ and so $x \in \{a\} \cup \{b\}$ . Now suppose $x$ is an element of $\{a\} \cup \{b\}$ . Then $x \in \{a\}$ or $x \in \{b\}$ . If $x \in \{a\}$ then $x=a$ so $x \in \{a,b\}$ . And if $x \in \{b\}$ then $x=b$ so again $x \in \{a,b\}$ .

Next we show that the union operation is commutative. Suppose $x \in A\cup B$ . Thus by Axiom 3.4, $x \in A$ or $x \in B$ . If $x \in A$ , then $x \in B\cup A$ . And if $x \in B$ , then $x \in B\cup A$ . Thus in both cases $x \in B\cup A$ . A similar argument shows that every element of $B\cup A$ is in $A\cup B$ , so $A\cup B = B\cup A$ .

Finally, we show that $A\cup A = A\cup \emptyset = \emptyset \cup A = A$ . By Axiom 3.4:

$x \in A\cup A$ if and only if $x \in A$ or $x \in A$ ; but “ $x \in A$ or $x \in A$ ” is the same as just $x \in A$ , so $x \in A\cup A$ if and only if $x \in A$
$x \in A\cup \emptyset$ if and only if $x \in A$ or $x \in \emptyset$ ; but $x \in \emptyset$ is always false (by Axiom 3.2) so $x \in A\cup \emptyset$ if and only if $x \in A$
$x \in \emptyset \cup A$ if and only if $x \in A$ , by a similar argument to the previous bullet point

Thus we see that given an object $x$ , this object is in each set if and only if $x \in A$ . So if $x$ is in one of the sets, it is in all of them. This shows that all of the sets are equal.

Solutions

Exercise 3.1.2

April 7, 2020 Issa Rice 5 Comments

Exercise statement

Using only Definition 3.1.4, Axiom 3.1, Axiom 3.2, and Axiom 3.3, prove that the sets $\emptyset$ , $\{\emptyset\}$ , $\{\{\emptyset\}\}$ , and $\{\emptyset, \{\emptyset\}\}$ are all distinct (i.e., no two of them are equal to each other).

Hints

Just be very careful.

How to think about the exercise

This is a somewhat tedious exercise if you happen to know what you are doing. And if you don’t know what you are doing, then it’s one of those exercises where you might feel tempted to say “well obviously these sets are all different”. So the real point of this exercise is to convince yourself that actually, it’s not obvious why these sets are all different, that there is some work that must be done.

I don’t have much to say about the object-level exercise itself. It’s just a matter of very carefully applying all of the axioms and the definition.

Also just a small note: these sets might appear useless, but three of the sets appearing in this exercise are part of the von Neumann definition of ordinal numbers.

Model solution

We first show that the empty set is distinct from all the other sets. By Axiom 3.3, $\emptyset \in \{\emptyset\}$ . However, $\emptyset \notin \emptyset$ by Axiom 3.2. Thus not every element of $\{\emptyset\}$ is an element of $\emptyset$ , so we conclude that $\emptyset \neq \{\emptyset\}$ . Similarly, $\{\emptyset\} \in \{\{\emptyset\}\}$ but $\{\emptyset\} \notin \emptyset$ , so $\emptyset \neq \{\{\emptyset\}\}$ . Also, $\emptyset \in \{\emptyset, \{\emptyset\}\}$ but $\emptyset \notin \emptyset$ , so $\emptyset \neq \{\emptyset, \{\emptyset\}\}$ .

Next we show that $\{\emptyset\}$ and $\{\{\emptyset\}\}$ are distinct. By Axiom 3.3, we see that $\emptyset \in \{\emptyset\}$ . Also by Axiom 3.3, we see that $y \in \{\{\emptyset\}\}$ if and only if $y = \{\emptyset\}$ . Considering the case $y = \emptyset$ , it follows that if we can show that $\emptyset \neq \{\emptyset\}$ , this will mean $\emptyset \notin \{\{\emptyset\}\}$ . But we already showed in the previous paragraph that $\emptyset \neq \{\emptyset\}$ . Thus $\emptyset \notin \{\{\emptyset\}\}$ , and it follows that not every element of $\{\emptyset\}$ is an element of $\{\{\emptyset\}\}$ , so $\{\emptyset\} \neq \{\{\emptyset\}\}$ .

Now we show that $\{\{\emptyset\}\}$ and $\{\emptyset, \{\emptyset\}\}$ are distinct. By Axiom 3.3, we have $\emptyset \in \{\emptyset, \{\emptyset\}\}$ . Also by Axiom 3.3, we see that $y \in \{\{\emptyset\}\}$ if and only if $y = \{\emptyset\}$ . Considering the case $y = \emptyset$ , we see that $\emptyset \in \{\{\emptyset\}\}$ if and only if $\emptyset = \{\emptyset\}$ . Since we showed in the first paragraph that $\emptyset \neq \{\emptyset\}$ , it follows that $\emptyset \notin \{\{\emptyset\}\}$ . Thus we have found an element, namely $\emptyset$ , which is in $\{\emptyset, \{\emptyset\}\}$ but not in $\{\{\emptyset\}\}$ , so the two sets are distinct.

Finally we show that $\{\emptyset\}$ and $\{\emptyset, \{\emptyset\}\}$ are distinct. By Axiom 3.3, we see that $\{\emptyset\} \in \{\emptyset, \{\emptyset\}\}$ . Also by Axiom 3.3, we see that $\{\emptyset\} \in \{\emptyset\}$ if and only if $\{\emptyset\} = \emptyset$ . But by the first paragraph of this proof, $\{\emptyset\} \neq \emptyset$ . Thus $\{\emptyset\} \notin \{\emptyset\}$ , which means that we have found an element, namely $\{\emptyset\}$ , which is in $\{\emptyset, \{\emptyset\}\}$ but not in $\{\emptyset\}$ , so the two sets are distinct.

Solutions

Exercise 3.1.1

April 6, 2020 Issa Rice Leave a comment

Exercise statement

Show that the definition of equality in Definition 3.1.4 is reflexive, symmetric, and transitive.

Hints

None (I can’t think of any hint to give).

How to think about the exercise

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

Model solution

Let $A,B,C$ be sets.

Reflexive: We must show $A=A$ . But every element $x$ of $A$ belongs to $A$ , so $A=A$ as desired. More formally, we might say that for any object $x$ , we have $x \in A$ if and only if $x \in A$ (because the two statements are literally identical), and so $A=A$ .

Symmetric: Now suppose $A=B$ . Then if $x \in B$ we see that $x \in A$ , and if $y \in A$ then $y \in B$ , so $B=A$ . Symbolically, we are given $\forall x (x \in A \iff x \in B)$ and we want to show $\forall x (x \in B \iff x \in A)$ . The result follows because $x \in A \iff x \in B$ and $x \in B \iff x \in A$ are logically equivalent.

Transitive: Now suppose $A = B$ and $B = C$ . We want to show that $A = C$ . Let $x \in A$ . Then since $A=B$ we see that $x \in B$ , and since $B=C$ we see that $x \in C$ . Similarly, if $y \in C$ , then $B=C$ tells us that $y \in B$ , and $A=B$ tells us that $y \in A$ . Thus $A$ and $C$ have exactly the same elements, so $A=C$ .

Solutions

Exercise 2.3.5

April 5, 2020 Issa Rice 7 Comments

Exercise statement

Prove Proposition 2.3.9.

Proposition 2.3.9 (Euclidean algorithm). Let $n$ be a natural number, and let $q$ be a positive number. Then there exist natural numbers $m,r$ such that $0 \leq r < q$ and $n = mq + r$ .

Hints

Fix $q$ and induct on $n$ .

How to think about the exercise

Terminological note: Tao calls this result “Euclidean algorithm”, but Euclidean algorithm is most commonly used for a different algorithm. The common term used for the topic of this exercise seems to be Euclidean division.

For this exercise, the only slightly tricky part is proving the inductive step. Here, what turns out to work is to split into cases. But which cases? I think the easiest way to see is to look at some examples. Let’s take the following, where we fix $q=5$ and increment $n$ by one each time:

10 divided by 5 = 2 with remainder 0
11 divided by 5 = 2 with remainder 1
12 divided by 5 = 2 with remainder 2
13 divided by 5 = 2 with remainder 3
14 divided by 5 = 2 with remainder 4
15 divided by 5 = 3 with remainder 0

I hope you can see the pattern. At each increment of $n$ , either the remainder goes up by 1 (in which case $m$ stays the same) or the remainder resets to 0 (in which case $m$ goes up by 1). What distinguishes the two cases? Well, the reset only happens when the remainder on the previous step is one less than the number we are dividing by, i.e. when $r+1 = q$ . For example, suppose we are at “14 divided by 5 = 2 with remainder 4”. Then the remainder, 4, is one less than the number we are dividing by, which is 5.

Model solution

Let us fix $q$ and induct on $n$ . For the case $n = 0$ , we must show that there are natural numbers $m,r$ such that $0 \leq r < q$ and $0 = mq + r$ . We can take $m=0$ and $r=0$ . Indeed, we have $0 \leq 0 < q$ (since $q$ is positive) and $0 = 0\times q + 0$ .

Now suppose inductively that there are natural numbers $m,r$ such that $0 \leq r < q$ and $n = mq + r$ . We must show that there are natural numbers $m', r'$ such that $0 \leq r' < q$ and $n+1=m'q + r'$ .

We have two cases, $r+1 = q$ and $r+1 \ne q$ . If $r+1=q$ , we can take $m' := m+1$ and $r' := 0$ . Then $0 \leq r' = 0 < q$ and we have $m'q + r'$ equal to $(m+1)q + 0$ by definition of $m',r'$ , which equals $mq + q$ by the distributive law, which equals $mq + r + 1$ by using $q=r+1$ , which equals $n+1$ by the inductive hypothesis $n=mq+r$ . Thus $m'q + r' = n+1$ as required.

Now suppose $r+1\ne q$ . In this case, $r < q$ from the inductive hypothesis gives $r+1 \leq q$ , so $r+1 < q$ . So we can take $r' := r+1$ and $m' := m$ . Now $0 \leq r' < q$ by what we just showed, and $m'q + r' = mq + r+1 = n+1$ by definition of $m',r'$ and the inductive hypothesis $n=mq+r$ .

Solutions

Exercise 2.3.3

April 4, 2020 Issa Rice Leave a comment

Exercise statement

Prove Proposition 2.3.5.

Proposition 2.3.5 (Multiplication is associative). For any natural numbers $a,b,c$ , we have $(a\times b)\times c = a\times (b\times c)$ .

Hints

Modify the proof of Proposition 2.2.5 and use the distributive law.

How to think about the exercise

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

Model solution

We keep $b,c$ fixed and induct on $a$ . For the base case, we have to show $(0\times b) \times c = 0\times (b\times c)$ . The left hand side is $0\times c=0$ and the right hand side is $0$ so the two sides are equal.

Now suppose inductively that $(a\times b) \times c = a\times (b\times c)$ . We want to show that $((a{{+}\!{+}})\times b) \times c = (a{{+}\!{+}})\times (b\times c)$ . Starting from the left hand side, $((a{{+}\!{+}})\times b)\times c$ equals $(a\times b + b)\times c$ by the definition of multiplication, which equals $(a\times b)\times c + b\times c$ by the distributive law, which equals $a\times (b\times c) + b\times c$ by the inductive hypothesis, which equals $(a{{+}\!{+}})\times (b\times c)$ by the definition of multiplication. Thus, the two sides are equal, which closes the induction.