Tao Analysis I - 2.3.5

Exercise 2.3.5

Prove Proposition 2.3.9. (Hint: fix q and induct on n.)

 

 Let's write out Proposition 2.3.9.

Proposition 2.3.9 (Euclid’s division lemma). 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$.

 

Let's follow the hint and prove this by induction. Before we dive in, it is worth noting the point of the proof is to show existence, which can make the proof easier.

Let the proposal $P(n)$ tate that there exist natural numbers $m$, $r$ such that $0 \leq r < q$ and $n = mq + r$.

The inductive hypothesis is that $P(n)$ is true. 

The base case is $P(0)$. That is, there exist natural numbers $m$, $r$ for

$$0 = mq + r$$

where $0 \leq r < q$.

One solution is $m=0$ and $r=0$. The existence of one solution is all we need to show the base case is true. As it happens, it is the only possible solution, but that is not required here.

The inductive step requires us to show that $P(n++)$ is true. That is, there exist natural numbers $m'$, $r'$ for

$$n++ = m'q + r'$$

where $0 \leq r < q'$.

Let's start with the inductive hypothesis.

$$n = mq + r$$

Incrementing both sides,

$$\begin{align} n++ &= (mq + r)++ \\ \\ &= mq + (r++) \\ \\ &= m'q + r' \end{align}$$

The simplest case is where $m'=m$ and $r'=r++$, as long as $r' < q$, that is $r++ < q$.

However, since $r < q$ means $r++ \leq q$ by Proposition 2.2.12, it is possible that $r++ = q$. In this case, using the distributivity of multiplication Proposition 2.3.4,

$$\begin{align} n++ &= mq + q \\ \\ &= (m+1)q + 0\\ \\ &= m'q + r' \end{align}$$

where $m'=m+1$ and $q=0$.

We have shown that $m'$ and $r'$ can always exist for $n++ = m'q + r'$, where $0 \leq r' < q$. This completes the induction step.

By showing the base case $P(0)$ is true, and that $P(n) \implies P(n++)$, by induction we have shown $P(n)$ holds for all natural numbers $n$. That is there exist natural numbers $m$, $r$ such that $0 \leq r < q$ and $n = mq + r$. $\square$

Tao Analysis I - 2.3.4

Exercise 2.3.4

Prove the identity $(a + b)^2 = a^2 + 2ab + b^2$ for all natural numbers $a$, $b$.

We want to show the following.

$$((a++) + b)^2 = (a++)^2 + (2 \times (a++) \times b) + b^2$$

Let's expand the LHS using the Definition 2.3.11 of exponentiation that $x^2=x^1 \times x$,  and the distributive law of Proposition 2.3.4 twice,

$$\begin{align}((a++) + b)^2 &= ((a++) + b) \times ((a++) + b) \\ \\ &= [((a++) + b)\times (a++)] + [((a++)+b) \times b)] \\ \\  &= (a++)^2 + (b \times (a++)) + ((a++)\times b) + b^2\end{align}$$

We now use commutivity of multiplication of Lemma 2.3.2,

$$\begin{align}((a++) + b)^2 &= (a++)^2 + (b \times (a++)) + ((a++)\times b) + b^2 \\ \\ &= (a++)^2 + (b \times (a++)) + (b \times (a++)) + b^2 \\ \\ &= (a++)^2 + (2 \times (a++) \times b) + b^2 \end{align}$$

The last step uses Definition 2.3.1 that $2 \times m = 0 + m + m$.

The final expression is the RHS, and so we have shown that for all natural numbers $(a + b)^2 = a^2 + 2ab + b^2$. $\square$

Tao Analysis I - 2.3.3

Exercise 2.3.3

Prove Proposition 2.3.5. (Hint: modify the proof of Proposition 2.2.5 and use the
distributive law.)

Let's write down 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)$.

The question hints that we should modify the proof of Proposition 2.2.5 regarding the associatibity of addition.

Let's use induction on $a$. The proposal $P(a)$ says that $(a \times b) \times c = a \times (b \times c)$

The induction hypothesis is that $P(a)$ is true. That is

$$(a \times b) \times c = a \times (b \times c)$$

The base case $P(0)$ is

$$(0 \times b) \times c = 0 \times (b \times c)$$

We can use Definition 2.3.1, $0 \times m:= 0$, to simplify

$$(0) \times c = 0 \times (b \times c)$$

This simplifies again to $0 = 0$ which is true. So the base case $P(0)$ is true.

The inductive step requires us to show $P(a++)$ is true. That is

$$((a++) \times b) \times c = (a++) \times (b \times c)$$

Let's consider the LHS and use Definition 2.3.1, $( n ++ ) \times m : = ( n \times m ) + m$, and then the distributive law of Proposition 2.3.4.

$$\begin{align}((a++) \times b) \times c &= ((a \times b) + b) \times c \\ \\ &= ((a \times b) \times c) + (b \times c)\end{align}$$

Let's now consider the RHS and use Definition 2.3.1, and the inductive hypothesis,

$$\begin{align}(a++) \times (b \times c) &= (a \times (b \times c)) + (b \times c) \\ \\ &= ((a \times b)\times c)) + (b \times c)\end{align}$$

The LHS and RHS are equivalent, so the inductive step succeeds.

We have shown the base case $P(0)$ is true, and that $P(a) \implies P(a++)$, and so by induction, $(a \times b) \times c = a \times (b \times c)$ is true for all natural numbers $a$. $\square$

Tao Analysis I - 2.3.2

Exercise 2.3.2

Prove Lemma 2.3.3. (Hint: prove the second statement first.)

Let's write down 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.

It is worth recalling the definition of a positive number.

Definition 2.2.7 (Positive natural numbers). A natural number $n$ is positive
iff it is not equal to 0.

 

Let's take the hint and prove the second statement first. Let's do it by inducting on $n$ and fixing $m$.

Inductive hypothesis: $(n > 0) \land (m > 0) \implies (nm > 0)$

Base case: $n=0$ give us

$$(0 > 0) \land (m > 0) \implies (0 \times m > 0)$$

This simplifies to $\text{false} \implies \text{false}$, which is true, and so the base case is true.

Although not necessary, it is insightful to see what happens with $n=1$. This gives us

$$(1 > 0) \land (m > 0) \implies (1 \times m > 0)$$

This simplifies to $(m > 0) \implies (m > 0)$, which is also true.

Now let's turn to the induction step. We need to show that

$$((n++) > 0) \land (m > 0) \implies ((n++)\times m > 0)$$

Now, we know that if $n>0$ then $n++ > 0$, because by definition $n = 0 + d$ and  so $n++ = 0 + (d++)$ where $d \neq 0$. 

This gives us

$$(m > 0) \implies ((n++)\times m > 0)$$

Let's focus on $(n++) \times m$. By Definition 2.3.1 this is $nm + m$. And so if $nm > 0$, then $(n++) \times m = nm + m > 0$, because $m>0$ by inductive hypothesis.

So finally $((n++) > 0) \land (m > 0) \implies ((n++)\times m > 0)$ reduces to $\text{true} \implies \text{true}$, which is true, and so the inductive step succeeds.

 By induction, we have shown  $(n > 0) \land (m > 0) \implies (nm > 0)$. $\square$

Now we need to prove the first statement in Lemma 2.3.3, which is

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

We need to prove this in both directions.

Let's consider left to right, $(n \times m = 0) \implies (n=0) \lor (m=0)$. The contrapositive which is equivalent to the original statement.

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

This simplifies to

$$ (n >0) \land (m > 0) \implies (n \times m > 0)$$

This is precisely what we have just proved above.

Let's consider right to left.

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

This covers three cases:

• $n=0$ which gives $0 \times m$ which by Definition 2.3.1 is 0.
• $m=0$ which gives $n \times 0$ which by commutativity of multiplication (Lemma 2.3.2) is also 0.
• $n=m=0$ which is covered by the $n=0$ case.

By proving both directions, we have shown $(n \times m = 0) \iff (n=0) \lor (m=0)$. $\square$

Tao Analysis I - 2.3.1

Thisset of of exercises is about multiplication.

Before we dive in, let's write out the minimal definitions we're given about multiplication.

Definition 2.3.1 (Multiplication of natural numbers). Let $m$ be a natural number. To multiply zero to $m$, we define $0 \times m := 0$. Now suppose inductively that we have defined how to multiply $n$ to $m$. Then we can multiply $n++$ to $m$ by defining $( n ++ ) \times m : = ( n \times m ) + m$. 

We can see this mirrors the definition for addition.

 

Exercise 2.3.1

Prove Lemma 2.3.2. (Hint: modify the proofs of Lemmas 2.2.2, 2.2.3 and Proposition 2.2.4)

Let's write out Lemma 2.3.2.

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

There are many parallels to the provided proof that addition is commutative, hence the suggestion to modify the proofs of Lemmas 2.2.2, 2.2.3 and Proposition 2.2.4. So let's develop our parallel lemmas based on those.

 

Lemma 1: For any natural number $n$, $n \times 0=0$.

Despite appearing obvious, we need to show it is true because the definition we have is $0 \times m := 0$.

We use induction. The induction hypothesis is that $n \times 0=0$.

The base case $n=0$ gives us $0 \times 0 = 0$. We can use $0 \times m := 0$ from the Definition 2.3.1 with $m=0$ to confirmt the base case is true.

Now let's consider the induction step. We want to show that $(n++) \times 0 = 0$ using the inductive hypothesis. By Definition 2.3.1 $(n++) \times 0 = (n \times 0) + 0$. Now, $(n \times 0)=0$ is the inductive hypothesis, so we have $(n++) \times 0 = 0 + 0 = 0$. So the induction step suceeds. 

Using induction, we have shown $n$, $n \times 0=0$. $\square$

Lemma 2: For any natural numbers $n$ and $m$, $n \times (m++)=(n \times m)+n$.

Despite appearing obvious, we do need to show it, because the definition only gives us $( n ++ ) \times m : = ( n \times m ) + m$.

We induct on $n$ keeping $m$ fixed. The induction hypothesis is $n \times (m++)=(n \times m)+n$.

The base case $n=0$ is $0 \times (m++)=(0 \times m)+0$. The LHS is 0 by Definition 2.3.1. The RHS also uses Definition 2.3.1 to give $(0) +0 = 0$. So the base case is true.

Now let's consider the induction step. We need to show that

$$(n++) \times (m++)=((n++) \times m)+(n++)$$

Let's start with the LHS, and use Definition 2.3.1, and then the induction hypothesis.

$$\begin{align}(n++) \times (m++) &= (n \times m++) + (m++) \\ \\ &= (n \times m) + n + (m++) \\ \\ &= (n \times m) + (n + m)++ \end{align}$$

Now consider the RHS, and use Definition 2.3.1.

$$\begin{align}((n++) \times m)+(n++) &= (n \times m) + m + (m++) \\ \\ &= (n \times m) + (n + m)++ \end{align}$$

The LHS and RHS are equivalent.  And so the induction step succeeds.

By induction we have shown that $n \times (m++)=(n \times m)+n$. $\square$

Lemma 2.3.2

We can now finally establish Lemma 2.3.2 that $n \times m = m \times n$.

Again we use induction on $n$, keeping $m$ fixed.

The induction hypothesis is that $n \times m = m \times n$ for natural numbers $m$ and $n$.

The base case $n=0$ gives us $0 \times m = m \ times 0$. The LHS is 0 by Definition 2.3.1. The RHS is 0 by Lemma 1, proved above. Thus the base case is true.

The induction step requires us to show that

$$(n++) \times m = m \times (n++)$$

Let's consider the LHS.

By Definition 2.3.1 we have

$$(n++) \times m =(n \times m) + m$$

Let's now consider the RHS, and apply Lemma 2, proved above, and then the induction hypothesis.

$$\begin{align}m \times (n++) &= (m \times n) + m \\ \\ &= (n \times m) + m\end{align}$$

The LHS and RHS are equivalent, so the induction step succeeds.

By induction we have shown that multiplication of natural numbers is commutative, $n \times m = m \times n$. $\square$

 

Tao Analysis I - 2.2.7

Exercise 2.2.7

Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m)$ is true, $P(m++)$ is true. Show that if $P(n)$ is true, then $P(m)$ is true for all $m \geq n$. (This principle is sometimes referred to as the principle of induction starting from the base case $n$.)

This looks easier than the last two exercises - let's hope it is!

 

Approach

The first thing to notice is that this scenario is very similar to the standard induction scenario, with the only difference beting that the variable is shifted up, from $m \geq 0$ to $m \geq n)$. This suggests we can reformulate the problem into the standard scenario by variable substitution.

 

Proof

Let's set

$$q = m-n$$

Here $n$ is fixed, and $m$ is free, and both are natural numbers.

If we can show that

• $P(q) \implies P(q++)$
• $P(q=0)$ is true

Then by the induction principle Axiom 2.5, we can say $P(q)$ is true for all natural numbers $q$.

Let's first consider $P(q) \implies P(q++)$. This is true because we are given that $P(m) \implies P(m++)$. The only constraint is that $q$ must be a natural number like $m$, which it is for $m \geq n$.

Let's now consider $P(q=0)$. Setting $q=0$ means $0 = m-n$, that is $n=m$. We are assuming that $P(n)$ is true. So $P(q=0)$ is true.

So we have established that for natural number $q$

• $P(q) \implies P(q++)$
• $P(q=0)$ is true

This is simply Axiom 2.5, so $P(q)$ is true for all natural numbers $q$. That is $P(q \geq 0)$ is true.

Now translating from $q$ back to $m$.

$$P(q \geq 0) \; \text{is true}$$

is the same as

$$P(m-n \geq 0) \; \text{is true}$$

That is,

$$P(m \geq n) \; \text{is true}$$

Thus we have shown $P(m \geq n)$. $\square$

Tao Analysis I - 2.2.6

Exercise 2.2.6

Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m++)$ is true, then $P(m)$ is true. Suppose that $P(n)$ is also true. Prove that $P(m)$ is true for all natural numbers $m ≤ n$; this is known as the principle of backwards induction. (Hint: apply induction to the variable $n$.)

The proposal seems intuitively correct and obvious, so the challenge is to prove it using only the building blocks provided by the text up to this point.

In case it isn't obvious, let's illustrate it. If the property $P(5)$ is true, the statement $P(m++) \implies P(m)$ tells us that $P(4)$ is also true. Now we know $P(4)$ is true, we can use $P(m++) \implies P(m)$ again to tell us $P(3)$ is true. We can keep going until we show $P(0)$ is true. So $P(0 \leq m \leq 5)$ is true.

Approach

We might be tempted to use soem form of induction that works backwards, but we can't do that. That is what we're being asked to prove, and we can only use the principle of induction as defined in Axiom 2.5, which goes forward, not backwards. 

As with the previous exercise, we transform the problem from one about $P(m)$ to one which is about $n$ by formulating a statement $Q(n)$. 

$$Q(n) : P(n) \implies P(m \leq n)$$

That is, $Q(n)$ says if $P(n)$ is true, then $P(m)$ is true for all natural numbers up to and including $n$.

 

Induction Proof

Now we can use standard induction on $n$, which we hope will show $Q(n)$ is true for all natural numbers $n$. Before we dive in, let's write out the known facts for clarity.

$$P(m++) \implies P(m)$$

$$P(n) \; \text{is true}$$

Inductive Hypothesis: $Q(n)$ is true.

Base Case: Consider $n=0$, which means

$$\begin{align}Q(0) &: P(0) \implies P(m \leq 0) \\ \\ Q(0) &: P(0) \implies P(0)\end{align}$$

$P(m \leq 0)$ is equivalent to $P(0)$ beccause only $m=0$ satisfies the inequality. 

$Q(0)$ is clearly true because $P(0) \implies P(0)$ is always true ... even if $P(n=0)$ were false, which it is not here.

Inductive Step: We need to show $Q(n) \implies Q(n++)$.

Let's start with $Q(n)$.

$$Q(n) : P(n) \implies P(m \leq n)$$

But we're given $P(n++) \implies P(n)$ so

$$P(n++) \implies P(n) \implies P(m \leq n)$$

We're almost there. $A \implies B$ is equivalent to $A \implies (B \land A)$. In plain English this is saying the implication of $A$ includes $A$. This gives us

$$\begin{align}P(n++) &\implies P(m \leq n) \land P(n++) \\ \\ P(n++) &\implies P(m \leq n++)\end{align}$$

This is $Q(n++)$.

By showing the base case $Q(0)$, and that $Q(n) \implies Q(n++)$, by the induction principle we have shown $Q(n)$ is true for all natural numbers $n$.

Translating back from $Q$ to $P$, we have $P(n) \implies P(m \leq n)$ if $P(n)$ is true, and $P(m++) \implies P(m)$. $\square$

Tao Analysis I - 2.2.5

Review: Weak & Strong Induction

Before we dive in, it is worth reviewing what standard "weak" and strong induction is. The following table summarises the difference (inspired by this).

Here $P(n)$ is a statement, or proposal, about a natural number $n$. For brevity, we've abused notation $P(m \leq n)$ to mean that $P(m)$ is true for all $m \leq n$. 

Weak Induction	Strong Induction
If $P(n_0)$ is true, And $P(n) \implies P(n+1)$ Then $P(n)$ is true for all $n \geq n_0$	If $P(n_0)$ is true, And $P(m \leq n) \implies P(n+1)$ Then $P(n)$ is true for all $n \geq n_0$

 

The only difference is that strong induction broadens the assumption that $P(n)$ is true to $P(m \leq n)$ is true. 

There is some confusion caused by the name "strong" because here it means broader assumptions, which to some ears (including mine), sounds like a weaker statement overall. To me, a theorem that makes fewer assumptions is stronger than an a theorem that requires lots of pre-requisites to be true.

The following visualises the difference between weak and strong induction.

 

Strong induction is used when $P(n)$ being true is insufficient to show $P(n+1)$ is also true. Let's look at an example of each.

Example: Weak Induction

This is the classic example used to illustrate standard, or weak, induction.

Aim: Prove that $1 + 2 + \ldots + n = \frac{n(n+1)}{2}$

Inductive Hypothesis: $P(n) : 1 + 2 + \ldots + n = \frac{n(n+1)}{2}$ is true.

Base Case:  LHS of $P(1)$ is 1. RHS of $P(1) = \frac{1(1+1)}{2}=1$.

Inductive Step: Consider $P(n+1)$. LHS is $1 + 2 + \ldots + n + (n+1)$. Using the inductive hypothesis, this is $\frac{n(n+1)}{2} + (n+1)$. Simple algebra leads to $\frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$. This is the RHS of $P(n+1)$. So $P(n) \implies P(n+1)$.

$P(1)$ being true, and $P(n) \implies P(n+1)$ means, by the principle of induction, $P(n)$ is true for all positive natural numbers $n$. $\square$

Note that we used the inductive hypothesis $P(n)$ to show $P(n+1)$ was true.

 

Example: Strong Induction

This is a classic example used to illustrate strong induction.

Aim: Prove that any natural number $n \geq 2$ is a product of primes. Note that a prime is considered to be a product of one prime.

Inductive Hypothesis: $P(n)$ : Every natural number less than or equal to $n$ is a product of primes.

Base Case: Consider $P(2)$. This states that 2 is a product of primes. We know 2 is a prime, and as such is a product of one prime. So $P(2)$ is true.

Inductive Step: Consider $m$ such that $2 \leq m \leq n$. We assume $P(m)$ is true. That is, we assume every natural number from 2 to $n$ is a product a primes. Now consider $P(n+1)$. Is $(n+1)$ a prime itself? There are two cases, yes and no. If yes, then $P(n+1)$ is true. If no, $(n+1)$ is not a prime, then it is a composite of 2 factors, $(n+1)=x \cdot y$ where $2 \leq x \leq n$ and $y$ are $2 \leq y \leq n$. The strong assumptions tell us that $x$ and $y$ are both products of one or more primes. Therefore $(n+1)$ is a product of primes too, and $P(n+1)$ is true in this second case.

With the base case $P(2)$ being true, and $P(2 \leq m \leq n) \implies P(n+1)$ being true, we have by strong induction shown that $P(n)$ is true for all positive natural numbers $n \geq 2$. 

Notice how we couldn't just use $P(n)$ to show $P(n+1)$. We needed $P(m)$ for $2 \leq m \leq n$.

Reference

This is a really clear summary of weak and strong induction with the classical examples.

• https://www.cs.cornell.edu/courses/cs2800/2011fa/Lectures/induction.pdf
  

 

Exercise 2.2.5

Prove Proposition 2.2.14. (Hint: 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 \leq m_0$.)

Let's write out 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$.

This is probably the first exercise we encounter in Tao's analysis I which looks difficult (as opposed looking easy but turning out to be difficult). So it is worth taking a step back and thinking about what approach we'll be taking before diving in.

Approach. The question hint suggests we use weak induction to prove strong induction. We want to reformulate strong induction in terms of weak induction. That is, we're solving a more challenging problem by reformulating into a more familiar problem.

Let's rewrite our previous table in terms of the variables given by the question. Note the different endpoints for the range of $m'$.

Weak Induction	Strong Induction
If $Q(n_0)$ is true, And $Q(n) \implies Q(n+1)$ Then $Q(n)$ is true for all $n \geq n_0$	If $P(m_0)$ is true, And $P(m_0 \leq m' < m) \implies P(m)$ Then $P(m)$ is true for all $m \geq m_0$

Before we dive in, let's be clear about what we need to prove, and what we can assume to be true:

• We need to find a base case for $Q(n_0)$ which is true.
• We need to show that if $Q(n)$ is true, then so is $Q(n+1)$.
  
• We can assume $P(m_0)$ is true for the purposes of proving strong induction.
• We can assume  $P(m_0 \leq m' < m) \implies P(m)$ is true for the purposes of proving strong induction.
  

Let's follow the standard template for weak induction over $n$, here using $Q(n)$. 

Inductive Hypothesis: $Q(n)$ is true.  

Let's write what this means in terms of $P(m')$.

$$Q(n) : P(m_0 \leq m' < n)$$

Inductive Step: $Q(n) \implies Q(n+1)$.

Since $P(m_0 \leq m' < n) \implies P(n)$, we have $P(m_0 \leq m' \leq n)$.

This means $Q(n+1)$ is true, because

$$Q(n+1) : P(m_0 \leq m' < n+1) = P(m_0 \leq m' \leq n)$$

So $Q(n) \implies Q(n+1)$.

Base Case: Consider $Q(m_0)$.

$$Q(m_0) : P(m_0 \leq m' < m_0)$$

This is vacuously true since no $m'$ satisfies $m_0 \leq m' < m_0$. 

By weak induction (Axiom 2.5), having shown the base case $Q(m_0)$ to be (vacuously) true, and that $Q(n) \implies Q(n+1)$, we can conclude $Q(n)$ is true for all $n \geq m_0$. 

What does this mean? Referring back to the definition of $Q(n)$,

$$Q(n) : P(m_0 \leq m' < n)$$

$Q(n)$ is true for all $n \geq m_0$ means

$$Q(n \geq m_0) : P(m_0 \leq m')$$

So we have shown $P(m)$ is true for all natural numbers $m \geq m_0$. $\square$

Tao Analysis I - 2.2.4

Exercise 2.2.4

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

Let's follow the provided proof of Proposition 2.2.13 and fill in the gaps.

Proposition 2.2.13 (Trichotomy of order for natural numbers). Let $a$ and $b$ be natural numbers. Then exactly one of the following three statements is true: 

• $a < b$
• $a = b$
• $a > b$.

The proof is in two parts:

• Part 1 - showing that not more than one of the three statements can hold at the same time
• Part 2 - showing at least one of the three statements must be true
  

Although it feels unusual, proving both of these things is sufficient to show that only one of the three statements can be true.

 

Part 1

Let's work through the cases.

• If $a<b$ then by definition 2.2.11, $a \neq b$. This leaves the possibility of $a>b$.
• If $a>b$ then by definition 2.2.11, $a \neq b$. This leaves the possibility of $a<b$.
• If $a=b$ then by definition 2.2.11, $a \nless b$ and $a \ngtr b$.

We're left to explore the possibility of $a<b$ and $a>b$ both being true. Proposition 2.2.12(c) says that if $a \leq b$ and $a \geq b$, then $a=b$. Our strict inequalities are a special case, and so we are led to $a=b$. But this is a contradiction! So we conclude not more than one of the cases can be simultaneously true.

Part 2

The book uses induction to prove that at least one of the three statements must be true. It fixes $b$ and inducts on $a$. 

When $a=0$, then $0 \leq b$ for all $b$. We're asked why (1). This means either $0 = b$ or $0 < b$ (but not both). This is the induction base case $a=0$.

The inductive hypothesis is that for a given $a$, at least one of the three statements is true. We need to show that if this is true for $a$, then it is also true for $a++$.

• If $a>b$ then $a++ > b$. We're asked why (2).
• If $a=b$ then $a++ > b$. We're asked why (3).
• If $a<b$ then by Proposition 2.2.12(e) we have $a++ \leq b$.This means either $a++ = b$ or $a++ < b$ (but not both). 

This concludes the induction.

We now answer the why questions.

 

Why 1

When $a=0$, then $0 \leq b$ for all $b$. We're asked why. 

The variables $a$ and $b$ are independent of each other, so $a$ does not constrain $b$. 

By definition $b$ is a natural number so it can take values from $b=0$ upwards. This is why $0 \leq b$. $\square$

Some of the other solution sites answered this question by demonstrating why the inequality $0 \leq b$ holds for all natural numbers $b$. Definition 2.2.1 of addition states that $0 + m:=m$, so we have $0 + b = b$. This matches Definition 2.2.11 for order relations, where $b = 0 + b$ means $b \geq 0$, or equivalently $0 \leq b$.

Why 2

If $a>b$ then $a++ > b$. We're asked why.

Let's start with 

$$a>b$$

Proposition 2.2.12(d) that addition preserves order, give us

$$a++ > b++$$

Now $b++ = b + 1$, and $b++ \neq b$ (Axiom 2.4), so by Definition 2.2.11 of order relations gives us

$$b++ > b$$

Since order is transitive by Proposition 2.2.12(b), from

$$a++ > b++ > b$$

we finally have

$$a++ > b$$

 

Why 3

If $a=b$ then $a++ > b$. We're asked why.

Let's start with

$$a = b$$

and increment both sides

$$a++ = b++$$

which we can rewrite as

$$a++ = b + 1$$

This matches Definition 2.2.11 for order relations, giving us the desired

$$a++ > b$$

 

Note

In the last 2 answers we've used $n++ = n + 1$. Although trivially obvious, we might ask how we show it from the basic axioms and lemmas. 

It is a corollary of the following two lemmas

• Lemma 2.2.2 - For any natural number $n$, $n+0=n$.
• Lemma 2.2.3 - For any natural numbers $n$ and $m$, $n+(m++)=(n+m)++$.
  

Here we take $m=0$ so $n+(0++)=(n+0)++$ becomes the desired $n+1=n++$.

Tao Analysis I - A.7.1

Exercise A.7.1

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

Let's remind ourselves of the four equality axioms presented in the book:

• Reflexivity. $x=x$.
• Symmetry. If $x=y$, then $y=x$.
• Transitivity. If $x=y$ and $y=z$, then $x=z$.
• Substitution. If $x=y$, then $f(x)=f(y)$ for all functions or operations $f$. Similarly if $x=y$, then $P(x)=P(y)$ for property $P$.
  

To answer the question, we have to try hard not to fall back to school algebra. The challenge is to go back to fundamentals and only use the axioms given.

Let's start with the given facts.

$$\begin{align} a &= b \\ c &=d \end{align}$$

Now let's use substition on $a=b$ using the function $f(x) = x + d$. This gives us

$$\begin{align} f(a) &= f(b) \\ a + d &=  b + d \end{align}$$

We can use substitution on $c=d$ using the function $g(x) = b + x$. This gives us

$$\begin{align} g(c) &= g(d) \\ b + c &=  b + d \end{align}$$

In preparation for the next step, we use symmetry to say

$$b + c =  b + d \implies b +d = b + c$$

Finally we use transitivity,

$$  (a + d =  b + d) \land (b + d =  b + c)  \implies (a+d = b+c) $$

The proof is complete. $\square$

Tao Analysis I - A.5.1

This section in the book is about quantifiers, and in particular nested quantifiers. The idea is to understand the precise meaning of commonly used English phrases, such as "for all" and "there exists". The differences between two statements in written English can sometimes seem subtle, but the mathematical meaning can be drastically different.

This exercise is quite good at teasing out and surfacing these differences.

Exercise A.5.1

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

Before we dive in,  let's remind ourselves of the gaming metaphor. The idea is that we and an opponent are choosing values for variables like $x$ or $y.

• The opponent can choose any value, without constraint. Where possible, the opponent is minded to choose values which disprove the statement. The opponent is playing the role of the universal quantifier, "for all", or $\forall$.
• We can choose a specific value, often trying to meet certain criteria for that variable, with the aim of proving the statement. We are playing the role of an existential quantifier, "there exists", or $\exists$.
  

For each part of the question we will, (1) write the statement in precise symbolic form,  (2) write it in plain English, (3) state whether the statement is true or false, (4) and illustrate it with the game metaphor. I will be following the convention for the symbolic form set out in Keith Devlin's course, which focussed on clarity rather than brevity.

Note: the exercise doesn't state what domain the variables $x$ and $y$ are from, but assuming they are positive real numbers makes sense $x, y \in R^+$.

 

(a) For every positive number $x$ , and every positive number $y$ , we have $y^2 = x$.

In symbolic form, this is

$$(\forall x \; \forall y)\; [\;y^2 = x\;]$$

In plain English, this says that every possible combination of $x$ and $y$ satisfies $y^2=x$. 

The statement is false. A counter-example is $x=1, y=2$, which does not satisfy $y^2=x$. $\square$

In the gaming metaphor, the opponent is choosing both $x$ and $y$ without constraint.

(b) There exists a positive number $x$ such that for every positive number $y$, we have $y^2 = x$.

In symbolic form, this is

$$(\exists x \; \forall y)\; [\;y^2 = x\;]$$

In plain English, if we pick a specific $x$, then for any $y$, the relation $y^2=x$ is satisfied.

The statement is false. If we pick $x=4$, then almost every value of $y$ does not satisfy the relation. Sure, $y=2$ works, but the whole infinitude of other possible values for $y$ fail to satisfy the relation. $\square$

In the gaming metaphor, after we pick a value for x, the opponent can pick a value to ensure the relation $y^2=x$ doesn't hold.

 

(c) There exists a positive number $x$, and there exists a positive number $y$, such that $y^2 = x$.

In symbolic form, this is

$$(\exists x \; \exists y) \; [\;y^2 = x\;]$$

In plain English, this says there is a specific $x$ and there is a specific $y$, that satisfy the relation $y^2 =x$.

The statement is true. There are (infinitely) many examples, but one is $x=4, y=2$. Another example is $x=9, y=3$. We only need one example to show the statement is true. $\square$

In the gaming metaphore, we can choose specific values for $x$ and $y$ to ensure they satisfy the relation. The opponent is not involved, and therefore can't pick values trying to ruin the relation.

 

(d) For every positive number $y$, there exists a positive number $x$ such that $y^2 = x$.

In symbolic form, this is

$$(\forall y \; \exists x) \; [\;y^2=x\;]$$

In plain English, this says that for any value of $y$, we can always find an $x$ such that $y^2=x$.

The statement is true. It is in fact saying that every positive natural number has a square. Or more fundamentally, for any $y$, we can always evaluate $y^2$. $\square$

In the gaming metaphor, the opponent can pick any positive number, and our challenge is to find its square, something which is always possible.

 

(e) There exists a positive number $y$ such that for every positive number $x$, we have $y^2 = x$.

In symbolic form, this is

$$(\exists y \; \forall x) \; [\;y^2 = x\;]$$

In plain English, this says that for any specific value chosen for $y$, then any and every choice of value for $x$ satisfies $y^2=x$.

The statement is false. Consider choosing $y=9$. Here $y^2=81$. This does not equate to every possible choice for $x$, only $x=81$. $\square$

In the gaming metaphor, we first choose a $y$, and our opponent then choose an $x$ that does not satisfy the relation.

 

Thoughts - Left to Right

Terence Tao is very clear that the plain English phrases need to be read from left to right, and any variables instantiated in that order, left to right.

This is counter to my previous habit of reading such sentences and unconsciously re-ordering them in an attempt to make them make sense. For example, the last example (e) was being read as "for every $x$ there is a $y$.

Another way to think about these is to instantiate the left-most (outer-most) variable and see what the inside means. With example (b), if we instantiate $x=3$ in

$$(\exists x \; \forall y)\; [\;y^2 = x\;]$$

it becomes

$$(\forall y)\; [\;y^2 = 3\;]$$

which is must easier to read and see as false.

Tao Analysis I - A.1.6

Exercise A.1.6

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.

As usual with these questions, let's build a truth table.

X	Y	Z	X $\implies$ Y	Y $\implies$ Z	Z $\implies$ X	S
F	F	F	T	T	T	T
F	F	T	T	T	F	F
F	T	F	T	F	T	F
F	T	T	T	T	F	F
T	F	F	F	T	T	F
T	F	T	F	T	T	F
T	T	F	T	F	T	F
T	T	T	T	T	T	T

The fiurth, fifth and sixth columns represent the conditions set out in the question, $X \implies Y$, $Y \implies Z$, and $Z \implies X$.

The final column S is the conjunction of all these conditions, and we can immediately recognise it as the logical equivalence of all three variables X, Y and Z.

So, yes, the conditions are sufficient to show X, Y and Z are logicallally equivalent. $\square$

It is interesting, and perhaps a pleasant surprise, to note that this kind of circular network of implications leads to logical equivalance. We have seen it in the simple case of 2 variables, where $X \implies Y$ and $Y \implies X$, is equivalent to $X \iff Y$.

 

Aside

It might be interesting to consider a network of implications with one or more closed loops, with appendages that are not part of any closed loop, to see which nodes (variables) are logically equivalent to the rest.

The above network shows that all the variables A-H are logically equivalent, but X is excluded from this logical equivalence.

Tao Analysis I - A.1.5

Exercise A.1.5

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.

Let's develop the truth table for this statement, which we'll call S.

X	Y	Z	X $\iff$ Y	Y $\iff$ Z	S
F	F	F	T	T	T
F	F	T	T	F	F
F	T	F	F	F	F
F	T	T	F	T	F
T	F	F	F	T	F
T	F	T	F	F	F
T	T	F	T	F	F
T	T	T	T	T	T

The fourth column for $X \iff Y$ represents the first condition in the question "X is true if and only if Y is true". Similarlym the fifth column for $Y \iff Z$ represents the second condition "Y is true if and only if Z is true".

The column for S is the conjunction of the previous two conditions,

$$ S = (X \iff Y) \land (Y \iff Z) $$

which we recognise as logical equivalence between all three X, Y and Z, because it is only true when all three variables have the same value.

So, yes, the conditions re sufficient to show X, Y and Z are logically equivalent. $\square$

It is interesting to note that what we have obeserved is the transitivity of the $\iff$ relation.

Tao Analysis I - A.1.4

Exercise A.1.4

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.

This is similar to the previous exercise A.1.3 and the approach is the same, to enumerate the truth table for the given statements.

The following is the truth table for the first statement "whenever X is true, then Y is true", which is the implication $X \implies Y$.

X	Y	X $\implies$ Y
F	F	T
F	T	T
T	F	F
T	T	T

The following truth table is for the second statement "whenever Y is false, then X is false", which is the implication $\neg Y \implies \neg X$.

X	Y	$\neg Y$	$\neg X$	$\neg Y \implies \neg X$
F	F	T	T	T
F	T	F	T	T
T	F	T	F	F
T	T	F	F	T

We can see the truth values for $X \implies Y$ and its contrapositive $\neg Y \implies \neg X$ are the same. It is a well known fact that an implication and its contrapositive are logically equivalent.

Let's now consider the conjunction of these two statements.

X	Y	$X \implies Y$	$\neg Y \implies \neg X$	$(X \implies Y) \land (\neg Y \implies \neg X)$
F	F	T	T	T
F	T	T	T	T
T	F	F	F	F
T	T	T	T	T

Unsurprisingly the truth values of the conjunction are the same as the conjuncts.

Now to answer the question. The truth values are not the same as for logical equivalence, $\iff$.

So, no, we have not demonstrated that X and Y are logically equivaelent. $\square$

(Thanks to Issa Rice for advising the original answer was misguided.)

Tao Analysis I - A.1.3

Exercise A.1.3

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.

The complexity of statements risks an error in trying to reason this out using only plain English, so let's go straight to truth tables.

The following table fills the truth values for the statement S, which are the conditions provided by the question.

X	Y	S	X<=>Y
F	F	T	T
F	T	F	F
T	F	F	F
T	T	T	T

Let's talk through how we filled in S:

• Whenever X is true, Y is true. This gives us row 4 as true. It also gives us row 3 as false because it contradicts the statement.
  
• Whenever X is false, Y is false. This gives us row 1 as true. It also gives us row 2 as false because it contradicts the statement.
  

Looking at the column S we see that it is only true when X and Y both have the same value. We recognise this as the logical equivalent, or the "if and only if" relation from the previous two exercises.

So, yes, we have demonstrated that X and Y are logically equivaelent. $\square$

Tao Analysis I - A.1.2

Exercise A.1.2

What is the negation of the statement “X is true if and only if Y is true”? (There may be multiple ways to phrase this negation.)

This English statement can be interpreted in several ways if read informally. 

To a mathematician, the phrase "if and only if" has a precise meaning. It is the bi-conditional $X \iff Y$, which is the combination of two implications $(X \implies Y) \land (Y \implies X)$.

Let's try to negate the statement at an English level:

• "it is not the case that X is true if and only if Y is true"
• .. leads to "X is true if Y is false, and, Y is true if X is false"

It is not immediately apparent that this also means the statement is false when X and Y are both true, or both false. It needs some thinking. Due to this risk, it is good practice to write out the truth tables.

X	Y	X $\implies$ Y	Y $\implies$ X	X $\iff$ Y	$\neg$ (X $\iff$ Y)
F	F	T	T	T	F
F	T	T	F	F	T
T	F	F	T	F	T
T	T	T	T	T	F

Here we've used the truth value definition of implication, which itself is counter-intuitive and requires a separate blog post to discuss.

The truth table confirms the nation of the given statement is "at most one of X or Y is true", or "either X or Y is true, but not both", or simply the exclusive-or relation $(X \oplus Y)$. $\square$

Note that combining this result and the one from the last exercise A.1.1, we can see XOR and logical equivalence are negations of each other.

$$ \boxed{ \neg (X \oplus Y) = (X \iff Y) }$$

Tao Analysis I - A.1.1

Appendix A is about mathematical logic, which covers the meaning of specific English phrases, manipulation of logical statements and connectives, and the sturtcure of proofs.

Exercise A.1.1

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

It is possible to do these kinds of exercises by mechanistically applying transformation rules to the symbolic representation of these statements, but it is useful to think about their actual meaning.

Here the statement expresses an exclusive-or relation between X and Y. That means the statement is true only one of A and B is true, but not both. 

X	Y	XOR
F	F	F
F	T	T
T	F	T
T	T	F

We expect the negation to have the following truth table.

X	Y	¬ XOR
F	F	T
F	T	F
T	F	F
T	T	T

We can see that for the statement to be true, both X and Y have to be true or false.

So the negation of the statement is "X and Y are both false, or X and Y are both true". $\square$

Let's see if symbolic manipulation gives us a simpler result.

Let's write out the original statement symbolically,

$$(X \lor Y) \land \neg (X \land Y)$$

We mechanistically can negate this by negating each clause, and swapping the and/or connectives,

$$\neg(X \lor Y) \lor (X \land Y)$$

We can write this in English as "None of X or Y are true, or  both X and Y are true". $\square$

This is equivalent to the answer we arrived at, but is less readable.

We could continue the symbolic manipulation to see if it helps,

$$(\neg X \land \neg Y) \lor (X \land Y)$$

This can be read as "both X and Y are false, or both X and Y are true". $\square$

This is again equivalent and just as readable as the first solution.

Tao Analysis I - 2.2.3

Exercise 2.2.3

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

(a) (Order is reflexive) $a \geq a$.

(b) (Order is transitive) If $a \geq b$ and $b\geq c$, then $a \geq c$.

(c) (Order is antisymmetric) 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$.

 

(a) Order is reflexive) $a \geq a$

We'll be using Definition 2.2.11 which defines the greater-than-or-equal $\geq$ order relation. It says that $n$ is greater than or equal to $m$, that is $n \geq m$ , iff we have $n = m + a$ for some natural number $a$. 

Does this order relation hold between $a$ and itself? Let's write it down symbolically using Definition 2.2.11,

$$ a \geq a \iff a = a + k $$

where $k$ is some natural number. We know from Lemma 2.2.2 that $n+0=n$, so we can say that relation can hold if $k=0$. $\square$

 

(b) (Order is transitive) If $a \geq b$ and $b\geq c$, then $a \geq c$.

Again, let's write out these relations using Definition 2.2.11,

$$ \begin{align} a &= b + k_1 \\ b& = c + k_2 \end{align} $$

where $k_1$ and $k_2$ is a natural number. We can substitute for $b$,

$$ a = (c + k_2) + k_1 $$

Since addition is associative, Proposition 2.2.5, we can rearrange the brackets,

$$ a = c + (k_2 + k_1) $$

This matches Definition 2.2.11 for the order relation $\geq$ where $(k_2 + k_1)$ is a natural number, allowing us to conclude $ c \geq c$. $\square$

We've assumed $(k_2 + k_1)$ is a natural number. Interestingly the book doesn't have a lemma stating that the sum of two natural numbers is a natural number, and we could prove it from Axion 2.2 and induction.

 

(c) (Order is antisymmetric) If $a \geq b$ and $b \geq a$, then $a=b$.

Let write these out using Definition 2.2.11,

$$ \begin{align} a &= b + k_1 \\ b& = a + k_2 \end{align} $$

where $k_1$ and $k_2$ is a natural number.  Again we can substitute for $b$,

$$ a = (a+ k_2) + k_1 $$

Since addition is associative, Proposition 2.2.5, we can rearrange the brackets,

$$ a = a + (k_2 + k_1) $$

Lemma 2.2.2 that $n+0=n$ tells us that $(k_2 + k_1)$ must be 0. Corollary 2.2.9 tells us this means both $k_2$ and $k_1$ nust be $0$. If this feels counterintuitive then remember natural numbers can't be negative, so the only way the sum of two can be $0$ is if both are $0$.

This leaves us with

$$\begin{align} a &= b + 0 \\ b& = a  + 0 \end{align}$$

That is, $a=b$. $\square$.

(d) (Addition preserves order) $a \geq b$ if and only if $a+c\geq b+c$.

Here we must notice that "if and only if", or "iff", is a bidirectional implication, or biconditional.

$$ a \geq b \iff a +c \geq b + c $$

This means we need to prove this statement in both directions.

($\implies$). Let's start with the LHS and rewrite it using the order relation Definition 2.2.11.

$$ a = b + k$$

Now we increment both sides by $c$,

$$ a + c = (b + k) + c $$

Using Proposition 2.2.5 that addition is associative gives us,

$$ a + c = b + (k + c) $$

and Proposition 2.2.4 that addiiton is commutative gives us,

$$ a + c = b + (c + k) $$

Using Proposition 2.2.5 that addition is associative one more time gives us,

$$ (a + c) = (b + c) + k$$

This is the RHS, $a+c \geq b+c$.

($\impliedby$). Now we start from the RHS, and rewrite it using Definition 2.2.11,

$$ (a + c) = (b + c) + j $$

Using commutativity we get

$$ (c + a) = (c + b) + j$$

Using associativity we get

$$ c + a =  c + (b + j) $$

Now we can use the cancellation law of Proposition 2.2.6

$$ a = b + j$$

This matches the Definition 2.2.11 for order relations, giving us the LHS

$$ a \geq b $$

Since we have proved the implication in both directions, the proof is complete. $\square$

It is worth commenting that most people would have demonstrated the validity of the statement in 2 lines, but our objective is to prove the statement using only the basic axioms and the few lemmas that have been proven at this point. That is the challenge, not showing the truth of the statement in a way that would convince most people.

(e) $a <b$ if and only if $a++ \leq b$

Here we must be careful of the direction of the order relation, and also note the bidirectional implication.

As usual, let's write this out using Definitition 2.2.11, with $j$ and $k$ natural numbers,

$$b =  a + j \iff b = (a++) + k$$

where $b \neq a$ because $b > a$ by Definition 2.2.11 again.

($\implies$). Let's start with the LHS.

$$b = a + j $$

By definition, $b \neq a$. Lemma 2.2.2 says $n + 0 = n$. This means $j \neq 0$. If we set $h$ such that $h++ = j$, then $h$ can be any natural number, including $0$.

$$b = a + (h++)$$

Using commutativity, Proposition 2.2.4, we have

$$b = (h++) + a$$

Using the Definition 2.2.1 of addition, $(n++) + m := (n +m)++$,  we have,

$$b = (h + a)++$$

And again by commutativity,

$$b = (a + h)++$$

And finally Definition 2.2.1 again,

$$b = (a++) + h$$

This is the RHS, $b \geq a++$.

($\impliedby$). Now let's consider the RHS, and write it using Definition 2.2.11,

$$b = (a++) + k$$

where $k$ is a natural number.

Using the same process as above, we shift the increment from $a$ to $k$,

$$b = a + (k++)$$

Now consider a positive number $q$ such that $k++ = q$. 

$$b = a + q$$

Because $q \neq 0$, that means $b \neq a$, which matches the definition of the order relation $>$. That is $b > a$, the LHS.

Having proven the implication in both directions, the proof is complete. $square$

(f) $a < b$ if and only if $b=a+d$ for some positive number $d$.

Again, we note the bidirectional implication, and take care of the direction of the order relation.

($\implies$). Let's start with the LHS, and write it using the Definition 2.2.11,

$$ b = a + d$$

where $b \neq a$, and so $d \neq 0$ as argued above in (e).  That means $d$ is a positive number.

($\impliedby$). Now let's consider the RHS

$$ b = a + d$$

where $d$ is a positive number.  Since $d \neq 0$, that means $b \neq a$ and so by definition 2.2.11, we have a strict order relation, the RHS.

$$ b > a$$

Since we have proved the statement in both directions, the proof is complete. $\square$

 

Tao Analysis I - 2.2.2

Exercise 2.2.2

Prove Lemma 2.2.10. Let $a$ be a positive number. Then there exists exactly one natural number $b$ such that $b++ = a$.

We are required to do two things

• existence - show that there is a solution
• uniqueness - show that there is only one solution
  

Again, the challenge is to get past the obviousness of the statement and try to dispassionately show it is true using the axioms.

Axiom 2.2 says that if $n$ is a natural number, then $n++$ is also a natural number. We should take care to note this is a one-way implication. It doesn't say that if $b++$ is a natural number then so is $b$. Note also that in Tao's book natural numbers include $0$. 

Existence

The book encourages us to use induction.

Let the proposal $P(a)$ state that if $a$ is a positive number, then there exists a natural number $b$ such that $b++ = a$.  That is,

$$ a \in \mathbb{N^+} \implies \exists b \in \mathbb{N} : b++ = a $$

Let's consider the base case $P(1)$. The base case is not $P(0)$ because $a$ must be a positive number which is never $0$, as per Definition 2.2.7.

$$ 1 \in \mathbb{N^+} \implies \exists b \in \mathbb{N} : b++ = 1 $$

Is this true? It is because 1 is indeed a positive number, and there does exist a natural number $b$ such that $b++ = 1$. That $b$ is $0$.

The inductive hypothesis is that $P(a)$ is true,

$$ a \in \mathbb{N^+} \implies \exists b \in \mathbb{N} : b++ = a $$

We need to show that $P(a++)$ is true. I've used $c$ to avoid mixing up variables,

$$ (a++) \in \mathbb{N^+} \implies \exists c \in \mathbb{N} : c++ = (a++) $$

This says that if $(a++)$ is a positive number, then there exists a natural number $c$ such that $c++ = (a++)$.  Is it true?

Well, $(a++)$ is indeed a positive number, because it is not zero, by Axiom 2.3. 

Is there a $c++$ that is $(a++)$? If we set $c=a$ then because $a$ is a natural number, so is $c$, and so is its successor $c++$ by Axiom 2.2.

Note that we didn't actually use $P(a)$ to show $P(a++)$ is true. We showed $P(a++)$ is true directly. This doesn't invalidate the structure of a proof by induction. Strictly speaking, if the consequent of an implication is always true, the implication itself is true.

Summarising, we have shown:

• the base case $P(1)$ is true
• if $P(a)$ is true then $P(a++)$ is true
  

So by induction, the proposal P(a) is true for all positive numbers $a \in \mathbb{N^+}$. 

But we're not finished yet because the proposal $P(a)$ only says that a $b$ exists, not that it is unique.

Uniqueness

Imagine that there are two disctinct natural numbers $b$ and $c$ that satisfy the proposal.

$$\begin{align} b++ &= a \\ c++ &= a \end{align}$$

Axiom 2.4 says different natural numbers have different successors. Here $a$ and $b$ have the same successor, so they must not be different. That is, $a$ must be $b$. So $b$ in the proposal is unique.

Having shown existence and uniqueness, the Lemma 2.2.10 is proven. $\square$

Intro To Mathematical Thinking

As someone coming to mathematical topics like analysis and number theory from outside, I found I was really limited by not having been taught

1. the special use of English my mathematicians, eg "if and only if", "implies"
2. the structure of a good proof

I was recently recommended Keith Devlin's Introduction to Mathematical Thinking which addresses these directly. The course is free on coursera.

 

After working through it, I realised that I was not fully understanding what I had been reading previously - for years! It also helped me understand when a proof needed to show implication in two directions, to prove an "if and only if" statement, for example.

As an aside, it also got me thinking deeper about the truth table for implication, which I'm still working out in my head... that will come up again during the exercises.

Tao Analysis I - 2.2.1

It is important for the exercises in this section that we don't assume results or knowledge that we have held as obvious for most of our lives, like $a+b = b+a$. Here we need to prove results using only the given axioms and definitions.

Let's remind ourselves of these Peano axioms.

Axiom 2.1 0 is a natural  number.

Axiom 2.2 If $n$ is a natural number, then $n++$ (successor to $n$) is also a natural number.

Axiom 2.3 0 is not the successor of any natural number.

Axiom 2.4 Different natural numbers must have different successors.

Axiom 2.5 (Principle of mathematical induction). Let P(n) be any property of a natural number $n$. Suppose $P(0)$ is true. Suppose also that if $P(n)$ is true, then so is $P(n++)$. Then $P(n)$ is true for all natural numbers $n$.

Let's illustrate the use of these axioms to prove that "4 is not equal to 0". This may seem obviously true, but we need to justify it based on the axioms, and only the axioms. We can say that 4 is the successor to 3, that is $4=(3++)$. Axiom 2.3 says that 0 is not the successor if any natural number, including 3. So 0 is not 3++, that is 0 is not 4. $\square$

This may feel laborious, and it is, but it is the only way to answer really explain why "4 is not 0", in a way that can't be refuted if we agree on the minimal Peano axioms.

Addition is defined as follows.

Definition 2.2.1 (Addition of natural numbers). Let $m$ be a natural number. To add zero to $m$, we define $0 + m := m$. Now suppose inductively that we have defined how to add $n$ to $m$. Then we can add $(n++)$ to $m$ by defining $(n++) + m := (n + m)++$.

The symbol $:=$ means definition. To get a feel for how this definition works, let's ask what $2+m$ is. Using the Definition 2.2.1 we have $0 + m:=0$, then

$$1+m = (0++) + m := (0+m)++ = m++$$

We then have

$$2 + m = (1++) +m := (1 + m) ++$$

We now know $1+m=m++$ so

$$2+m = (m++)++$$

This allows us to say $3+m = ((m++)++)++$, that is, the third successor of $m$.

Let's practice using the definition of addition to show another apparently obvious statement that "$n+0=n$" for all natural numbers $n$. We might be tempted to say that this is actually in the definition, but it isn't. The definition defines $0+m$, not $m+0$. We haven't yet justified that addition is commutative. 

We'll use induction to show that $n+0=n$. Following the template for inductive proofs, we define the base case for $n=0$, that is $0+0=0$. Is this true? It is the definition which says $0+m:=m$ taken with $m=0$. 

Next is the inductive step. The inductive hypothesis is that the proposal $n+0=n$ is true for all natural numbers $n$. We have to use the inductive hypothesis to show that the proposal is true for $n++$,  that is $(n++) + 0 = (n++)$. We use Definition 2.2.1 with $m=0$ to say $(n++) + 0:= (n+0)++$. The inductive hypothesis says $n+0=n$ so we have $(n++) + 0 = (n++)$, showing the proposal is true for $n++$. Because we've shown the proposal is true for the base case $n=0$, and also shown that if it is true for $n$ then it is also true for $n++$. By induction, Axiom 2.5, the proposal is proven for all natural numbers $n$. $\square$

This all seems laborious, and it is. But experiencing how we can build up familiar, and seemingly obvious, mathematics from a minimal set of axioms is important.

Exercise 2.2.1

Prove addition is associative. For any natural numbers $a$, $b$, $c$, we have $(a+b)+c = a + (b+c)$.

We can't use our existing knowledge to justify this. We have to prove it using only the axioms and definition of addition.

Let's use induction. 

The proposal $P(a)$ says $(a+b)+c = a + (b+c)$.

The base case $P(0)$ is

$$(0+b) + c = 0 + (b+c)$$

From the definition of addition, we know that $)+m:=m$, which means

$$(b) + c = (b+c)$$

So $P(0)$ is true.

The inductive hypothesis is that $P(a)$ is true. That is

$$(a+b)+c = a + (b+c)$$

We need to show that $P(a++)$ is also true. That is, 

$$((a++) + b) + c = (a++) + (b + c)$$

Let's consider the LHS, and twice apply $(n++) + m := (n + m)++$ from the definition of addition.

$$\begin{align} ((a++) + b) + c &= ((a + b)++) + c \\ &= ((a+b) + c) ++  \end{align}$$

Now let's apply the inductive hypothesis,

$$((a++) + b) + c = (a + (b+c)) ++ $$

Finally, we can use the definition again

$$\begin{align} ((a++) + b) + c &= (a + (b+c)) ++  \\ &= ((a++) + (b+c)) \end{align}$$

This the the RHS of $P(a++)$.

To summarise, we have shown:

• the base case $P(0)$ is true
• if $P(a)$ is true, then $P(a++)$ is true

So by induction (Axiom 2.5) we can say the proposal is true for all natural numbers $a$. $\square$