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.

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.

Exercise statement

Hints

How to think about the exercise

Model solution

Exercise statement

Hints

How to think about the exercise

Model solution

Exercise statement

Hints

How to think about the exercise

Model solution

Exercise statement

Hints

How to think about the exercise

Model solution

Exercise statement

Hints

How to think about the exercise

Model solution

Exercise statement

Hints

How to think about the exercise

Model solution

Exercise statement

Hints

How to think about the exercise

Model solution

Exercise statement

Hints

How to think about the exercise

Model solution 1

Model solution 2