Solutions

Exercise 5.1.1

March 23, 2020 Issa Rice 1 Comment

Exercise statement

Prove Lemma 5.1.15.

Lemma 5.1.15 (Cauchy sequences are bounded). Every Cauchy sequence $(a_n)_{n=1}^\infty$ is bounded.

Hints

Use the fact that $a_n$ is eventually $1$ -steady, and thus can be split into a finite sequence and a $1$ -steady sequence. Then use Lemma 5.1.14 for the finite part. Note that there is nothing special about the number $1$ used here; any other positive number would have sufficed.
You might want to use the triangle inequality.

How to think about the exercise

I think this is a pretty straightforward exercise, especially given the hints.

Model solution

Let $(a_n)_{n=1}^\infty$ be a Cauchy sequence of rational numbers. By Definition 5.1.8, $(a_n)_{n=1}^\infty$ is eventually $\varepsilon$ -steady for every rational $\varepsilon > 0$ , so in particular for $\varepsilon = 1$ it is eventually $1$ -steady. This means that there exists an $N \geq 1$ such that $|a_j - a_k| \leq 1$ for all $j,k \geq N$ .

Since $N \geq N$ , we may take $k$ to be $N$ . Thus for all $j \geq N$ we have $|a_j - a_N| \leq 1$ . By Proposition 4.3.3(b) with $x := a_j - a_N$ and $y := a_N$ we have $|x+y| - |y| \leq |x|$ , i.e. $|a_j| - |a_N| \leq |a_j - a_N| \leq 1$ . Thus we have $|a_j| \leq 1 + |a_N|$ for all $j \geq N$ , so we have bounded the infinite tail of the sequence.

By Lemma 5.1.14, the finite sequence $a_1, \ldots, a_{N-1}$ is bounded by some number $M \geq 0$ .

So now we can take the bound over the entire sequence to be $M' := M + 1 + |a_N|$ . If $1 \leq n < N$ , then $|a_n| \leq M \leq M'$ , and if $n \geq N$ then $|a_n| \leq 1 + |a_N| \leq M'$ .

Solutions

Exercise 4.1.8

March 22, 2020 Issa Rice 4 Comments

Exercise statement

Show that the principle of induction (Axiom 2.5) does not apply directly to the integers. More precisely, give an example of a property $P(n)$ pertaining to an integer $n$ such that $P(0)$ is true, and that $P(n)$ implies $P(n{{+}\!{+}})$ for all integers $n$ , but that $P(n)$ is not true for all integers $n$ . Thus induction is not as useful a tool for dealing with the integers as it is with the natural numbers. (The situation becomes even worse with the rational and real numbers, which we shall define shortly.)

Hints

I can’t think of a good hint for this exercise. Try reading the next section paragraph by paragraph (stopping after each paragraph to attempt the exercise again).

How to think about the exercise

Exercises that ask you to find an example come with an associated extra question of “What must the solution space look like?” Is there some simple characterization of every property $P$ that works as a solution to this exercise? Another way to think about this is to ask the following: for any $P$ that is a solution to this exercise, what does $\{n \in \mathbf Z : P(n)\}$ look like? Let’s try to think this through.

First, if $P(0)$ is true, and if $P(n)$ implies $P(n{{+}\!{+}})$ for all integers $n$ , then it must also be the case that $P(n)$ implies $P(n{{+}\!{+}})$ for all natural numbers $n$ . So any $P$ that we give must be true for all natural numbers.

But we also know that $P$ cannot hold for all integers. In other words, we want to find a $P$ that holds for all natural numbers, but where there is also a negative integer $-n$ such $P(-n)$ is false. This is a necessary condition, but not necessarily a sufficient condition. Is it also a sufficient condition? It is not: consider $P(n)\equiv$ “ $n$ is not equal to $-1$ ”. This is true for all natural numbers and fails for $n=-1$ , but it also fails the inductive hypothesis, since for $n=-2$ , we see that $P(n)$ does not imply $P(n{{+}\!{+}})$ .

So we want some stronger necessary condition, which we hope will also be a sufficient condition. It’s not obvious what thought to think next. So let’s just think concretely. We already know $P(0), P(1), \ldots$ must all be true. What about $P(-5)$ ? Well, that could be true or false. What if it’s true? Then the inductive hypothesis says that $P(-4)$ is true, so $P(-3)$ must be true, and so on. Once we get to $P(0)$ , we already know that the rest is true. What if $P(-5)$ is false? Could $P(-6)$ be true? No, because if $P(-6)$ then the inductive hypothesis tells us $P(-5)$ is true! So if $P(-5)$ is false, then $P(-6)$ is also false, which means $P(-7)$ is also false, and so on.

Generalizing the previous paragraph, let $m$ be an integer. If $P(m)$ is true, then the inductive hypothesis says that $P(m+1), P(m+2), \ldots$ are all true. And if $P(m)$ is false, then the inductive hypothesis tells us that $P(m-1), P(m-2), \ldots$ are all false.

We are given that $P$ should be false for some integer. Call this integer $r$ . By the reasoning in the previous paragraph, we see that $P(r), P(r-1), P(r-2), \ldots$ are all false. And of course, $P(0), P(1), P(2), \ldots$ are all true. So that leaves the integers $r+1, r+2, \ldots, -2, -1$ . We don’t know if $P$ holds for these numbers. But there is only a finite list of these numbers, so there must be some least number among them for which $P$ is true, or else $P$ is false for all of them. To see this, visualize the number line $\ldots, -1, 0, 1, \ldots$ and then visualize below that the list $\ldots, P(-1), P(0), P(1), \ldots$ . The latter list looks like …, false false false, ?, ?, …, ?, ?, true, true true, … . Either all of the question marks turn out to be false, or one of the question marks will be the smallest one which turns out to be true. (If this still confuses you, consider the following: take some children and line them up by their birth date. Either all of the children are girls, or there will be a boy, in which case one of the boys will be the youngest.) If all of the question marks are false, then the set $\{n \in \mathbf Z : P(n)\}$ is equal to $\{n \in \mathbf Z : n \geq 0\}$ . If one of the question marks turns out to be true, call the smallest one $m$ . Then by the reasoning in the previous paragraph, everything to the right of $m$ (including $m$ ) is true, and everything to the left is false (since $m$ is the least number for which $P(m)$ is true). So the set $\{n \in \mathbf Z : P(n)\}$ is equal to $\{n \in \mathbf Z : n \geq m\}$ .

So a reasonable new candidate for a necessary condition is the following: if $P$ is a solution to the exercise, then $\{n \in \mathbf Z : P(n)\}$ is equal to $\{n \in \mathbf Z : n \geq m\}$ for some integer $m$ . Is this sufficient? No, because if our set was $\{n \in \mathbf Z : n \geq 5\}$ it wouldn’t be true for all natural numbers! So we must restrict $m \leq 0$ . Now is it a sufficient condition? Let’s try to prove it. Let $m \leq 0$ and suppose $P$ is a property such that $P(n) \iff n \geq m$ . We want to show that such a $P$ is a solution to the exercise. For the base case, we see that $P(0)$ is true since $0 \geq m$ . Now suppose $P(n)$ is true. Thus $n \geq m$ , and since $n{{+}\!{+}} \geq n$ , we see that $n{{+}\!{+}} \geq m$ , so $P(n{{+}\!{+}})$ is true. Finally, we must show that $P$ is false for some integer. Easy, just take $m-1$ .

What have we shown? We’ve shown that the properties $P$ which are a solution to this exercise are precisely those for which there exists an integer $m \leq 0$ such that $P(n) \iff n \geq m$ . Of course, $P(n)$ might not look like $n \geq m$ , but it must secretly encode such a relation. An example of this is $P(n) \iff n+n \geq n$ which is equivalent to just $n\geq 0$ .

Here’s a slightly different way to think about this exercise: suppose you have a bunch of cards labeled “FF”, “FT”, and “TT”. Your goal is to create an infinite line (extending both to the left and right) from these cards, but there are three rules: (1) there must be at least one F in the line; (2) the line must have an infinite number of Ts going off to the right; and (3) when you place a new card you place it either to the left or right of the existing line, and one of the letters on the new card has to match an existing letter (except for the very first time you place a card), where if you place a card to the right the left side of the new card must match the right end of the line, and if you place a card to the left the right side of the new card must match the left end of the line. An example should help. Suppose you start by placing TT. Then to the right of it you place another TT, so that the line looks like TTT (think of the matching letter as being covered up). Then to the left of the line you place FT, so the line looks like FTTT. And so on. What must the line look like, once you have placed an infinite number of cards? It must look like …FFFFTTTT… .

Model solution

Consider $P(n)$ defined as “ $n$ is non-negative”. By trichotomy of integers, $0$ is not negative, so $P(0)$ is true. Also if $n$ is non-negative, then $n{{+}\!{+}}$ is non-negative. Finally, $P$ is false for $-1$ .

Solutions

Exercise 4.1.6

March 21, 2020 Issa Rice 6 Comments

Exercise statement

Prove Corollary 4.1.9.

Corollary 4.1.9 (Cancellation law for integers). If $a,b,c$ are integers such that $ac = bc$ and $c$ is non-zero, then $a=b$ .

Hints

There are two ways to do this. One is to use Proposition 4.1.8 to conclude that $a-b$ must be zero. Another way is to combine Corollary 2.3.7 with Lemma 4.1.5.

How to think about the exercise

This is a straightforward exercise.

Model solution 1 (using Proposition 4.1.8)

Let $a,b,c$ be integers such that $c$ is non-zero. Suppose $ac = bc$ . Then we can add $-(bc)$ to both sides of the equation to get

$ac + (-(bc)) = bc + (-(bc))$ . (*)

The right side of this equation (*) is $bc + (-(bc)) = 0$ by Proposition 4.1.6 (specifically, adding the negation of a number). To compute the left side of this equation (*), we first note that by Exercise 4.1.3, we have $-(bc) = (-1)(bc)$ . By Proposition 4.1.6 (specifically, associativity of multiplication), we have $(-1)(bc) = ((-1)b)c$ . And again by Exercise 4.1.3 we have $((-1)b)c = (-b)c$ . Chaining these equalities together, we have that $-(bc) = (-b)c$ . Now we can compute the left side of (*). We have $ac + (-(bc)) = ac + (-b)c = (a + (-b))c$ , where the last step uses Proposition 4.1.6 again (specifically, the distributive property). The left and right sides of (*) are equal, so combining our two computations, we have $(a + (-b))c = 0$ . Since $c \ne 0$ , we can use Proposition 4.1.8 to conclude that $a + (-b) = 0$ . Adding $b$ to both sides, we have $a + (-b) + b = b$ . By Proposition 4.1.6 again this implies $a = b$ .

(Thanks to Nam for pointing out a flaw in an earlier version of the proof. This flaw has now been fixed in the proof shown above.)

Model solution 2 (using Corollary 2.3.7 and Lemma 4.1.5)

Let $a,b,c$ be integers such that $c$ is non-zero, and suppose $ac = bc$ . Since $a,b$ are integers, there exist natural numbers $a',a'', b',b''$ such that $a=a'{{-}\!{-}}a''$ and $b=b'{{-}\!{-}}b''$ . Also since $c$ is non-zero, by trichotomy of integers (Lemma 4.1.5) it is of the form $n{{-}\!{-}}0$ or $0{{-}\!{-}}n$ for some positive natural number $n$ .

Suppose first that $c = n{{-}\!{-}}0$ . Then the equation $ac = bc$ gives us

$(a'{{-}\!{-}}a'')\times (n{{-}\!{-}}0) = (b'{{-}\!{-}}b'')\times (n{{-}\!{-}}0)$

which simplifies to $na'{{-}\!{-}}na'' = nb'{{-}\!{-}}nb''$ , i.e. $na' + nb'' = nb' + na''$ . By the distributive law (Proposition 2.3.4), we have $n(a'+b'') = n(b'+a'')$ . Since $n \ne 0$ , we can use cancellation (Corollary 2.3.7) to get $a'+b'' = b'+a''$ , i.e. $a'{{-}\!{-}}a'' = b'{{-}\!{-}}b''$ .

Now we do the case where $c = 0{{-}\!{-}}n$ . The equation $ac = bc$ gives us

$(a'{{-}\!{-}}a'')\times (0{{-}\!{-}}n) = (b'{{-}\!{-}}b'')\times (0{{-}\!{-}}n)$

which simplifies to $na''{{-}\!{-}}na' = nb''{{-}\!{-}}nb'$ , i.e. $na'' + nb' = nb'' + na'$ . This is exactly what we had in the earlier case, so the rest is exactly the same.

Solutions

Exercise 4.1.5

March 20, 2020 Issa Rice 3 Comments

Exercise statement

Prove Proposition 4.1.8.

Proposition 4.1.8 (Integers have no zero divisors). Let $a$ and $b$ be integers such that $ab = 0$ . Then either $a=0$ or $b=0$ (or both).

Hints

While this proposition is not quite the same as Lemma 2.3.3, it is certainly legitimate to use Lemma 2.3.3 in the course of proving Proposition 4.1.8.
You might want to use Lemma 4.1.5.

How to think about the exercise

This is a good example of an exercise where doing the obvious thing leads to a difficulty, so then you need to backtrack and change your strategy.

Here’s my first approach, when I encounter this exercise. Since $a$ and $b$ are both integers, we can write them as $a = c{{-}\!{-}}d$ and $b=e{{-}\!{-}}f$ for natural numbers $c,d,e,f$ . By hypothesis $ab = 0$ , which means $(c{{-}\!{-}}d)\times (e{{-}\!{-}}f) = (ce + df){{-}\!{-}}(cf + de) = 0{{-}\!{-}}0$ . Now the definition of equality says that this means $ce + df = cf + de$ . From here, it is not at all clear how to show that $c=d$ or $e=f$ . (It turns out to be possible to force this into a proof, but the result is somewhat ugly; see model solution 3 below.)

The key is to backtrack, and try a different strategy. In this case, you want to simplify the problem by breaking down into cases. For instance, if you know that $a$ is positive, then you can write $a=c{{-}\!{-}}0$ , which simplifies the expressions. But how do you arrive at this thought of “oh, I should prove by cases”? I think the general algorithm is to think something along the lines of: I can’t figure out how to prove this in the general case; is there a more restricted case where I can prove it? For instance, can I prove it if $a$ is a positive integer?

Model solution 1

By trichotomy of integers (Lemma 4.1.5), we can split into the following three cases: $a$ is zero, $a$ is equal to a positive natural number, or $a$ is equal to the negation of a positive natural number.

In the first case, $a$ is zero, so the result is immediate.

Now suppose $a$ is equal to a positive natural number $n$ , so that $a = n{{-}\!{-}}0$ . Since $b$ is an integer, $b=e{{-}\!{-}}f$ for some natural numbers $e,f$ . Thus $(n{{-}\!{-}}0)\times (e{{-}\!{-}}f) = (ne){{-}\!{-}}(nf) = 0$ , which means that $ne = nf$ . Since $n$ is non-zero, Corollary 2.3.7 tells us that $e=f$ , i.e. $e+0 = f+0$ , which means that $b=0$ .

Finally suppose $a$ is equal to the negation of a positive natural number $n$ , so that $a = 0{{-}\!{-}}n$ . Write $b=e{{-}\!{-}}f$ , so that $(0{{-}\!{-}}n)\times (e{{-}\!{-}}f) = (nf){{-}\!{-}}(ne) = 0$ . This means that $nf=ne$ , so by Corollary 2.3.7 again we have $f=e$ . Hence $b=0$ .

Model solution 2

We prove the contrapositive, i.e. we suppose that $a\ne 0$ and $b\ne 0$ , and we show that $ab\ne 0$ .

So suppose $a\ne0$ and $b\ne0$ . By trichotomy of integers, we have four cases:

$a$ and $b$ are both positive: In this case, we can write $a=n{{-}\!{-}}0$ and $b=m{{-}\!{-}}0$ for positive natural numbers $n,m$ . Thus $ab = (n{{-}\!{-}}0)\times (m{{-}\!{-}}0) = (nm + 0){{-}\!{-}}(0 + 0) = nm$ . By Lemma 2.3.3, $nm$ is positive, so by Lemma 4.1.5 it cannot equal zero.
$a$ and $b$ are both negative: We can write $a=0{{-}\!{-}}n$ and $b=0{{-}\!{-}}m$ for positive natural numbers $n,m$ . Thus $ab = (0{{-}\!{-}}n)\times (0{{-}\!{-}}m) = (0 + nm){{-}\!{-}}(0+0) = nm$ . By Lemma 2.3.3, $nm$ is positive, so by Lemma 4.1.5 it cannot equal zero.
$a$ is positive and $b$ is negative: We can write $a=n{{-}\!{-}}0$ and $b=0{{-}\!{-}}m$ for positive natural numbers $n,m$ . Thus $ab = (n{{-}\!{-}}0)\times (0{{-}\!{-}}m) = (0 + 0){{-}\!{-}}(nm + 0) = 0{{-}\!{-}}(nm)$ . This is the negation of a positive natural number $nm$ (by Lemma 2.3.3), so by trichotomy of integers it cannot equal zero.
$a$ is negative and $b$ is positive: This is the same as the previous case (just relabel $a$ and $b$ ).

In all four cases $ab \ne 0$ , so we are done.

Model solution 3

Since $a$ and $b$ are both integers, we can write them as $a = c{{-}\!{-}}d$ and $b=e{{-}\!{-}}f$ for natural numbers $c,d,e,f$ . By hypothesis $ab = 0$ , which means $(c{{-}\!{-}}d)\times (e{{-}\!{-}}f) = (ce + df){{-}\!{-}}(cf + de) = 0{{-}\!{-}}0$ . Now the definition of equality says that this means $ce + df = cf + de$ .

By the embedding of the natural numbers within the integers, this means

$(ce{{-}\!{-}}0) + (df{{-}\!{-}}0) = (cf{{-}\!{-}}0) + (de{{-}\!{-}}0)$

By the laws of algebra for integers (Proposition 4.1.6) we have

$(ce{{-}\!{-}}0) + (0{{-}\!{-}}cf) = (de{{-}\!{-}}0) + (0{{-}\!{-}}df)$

which implies

$(ce{{-}\!{-}}cf) = (de{{-}\!{-}}df)$

by Definition 4.1.2.

By definition of multiplication, $(c{{-}\!{-}}0) \times (e{{-}\!{-}}f) = (ce{{-}\!{-}}cf)$ and $(d{{-}\!{-}}0)\times (e{{-}\!{-}}f) = (de{{-}\!{-}}df)$ so we have

$(c{{-}\!{-}}0) \times (e{{-}\!{-}}f) = (d{{-}\!{-}}0)\times (e{{-}\!{-}}f)$

Now suppose $b \ne 0$ ; we must show that $a = 0$ . By trichotomy of integers, $b$ is equal to a positive natural number, or equal to the negation of one. If $b$ is positive then we can write $e{{-}\!{-}}f$ as $n{{-}\!{-}}0$ for positive natural number $n$ . Thus we have $cn=dn$ , which by Lemma 2.3.3 means $c=d$ so that $a=0$ . Similarly if $b$ is negative then we can write $e{{-}\!{-}}f$ as $0{{-}\!{-}}n$ , so that $0{{-}\!{-}}cn = 0{{-}\!{-}}dn$ , which means that $dn=cn$ . Again, this means $a=0$ .

Solutions

Exercise 4.1.3

March 19, 2020 Issa Rice 6 Comments

Exercise statement

Show that $(-1) \times a = -a$ for every integer $a$ .

Hints

Use Definition 4.1.4 and Definition 4.1.2.

How to think about the exercise

This exercise is a simple application of the definitions.

Model solution 1

Let $a$ be an integer. Thus there exist natural numbers $b,c$ such that $a = b{{-}\!{-}}c$ . We have $(-1) \times a = (0{{-}\!{-}}1) \times (b{{-}\!{-}}c) = (0b + 1c){{-}\!{-}}(0c + 1b)$ by Definition 4.1.4 and Definition 4.1.2. By the definition of multiplication for natural numbers (Definition 2.3.1), both $0b$ and $0c$ are $0$ , and $1c$ and $1b$ are $c$ and $b$ respectively. Thus $(-1)\times a = c{{-}\!{-}}b$ . By Definition 4.1.4, $-a = -(b{{-}\!{-}}c) = c{{-}\!{-}}b$ . Thus, both $(-1) \times a$ and $-a$ are equal to $c{{-}\!{-}}b$ .

Model solution 2

(Thanks to penguin22 for the idea of this proof.)

The result we are trying to show, $(-1) \times a = -a$ , turns out to be true in any ring (the integers are an example of a ring; see Remark 4.1.7). So we can give a more general proof (meaning that the same proof will carry over to any ring) by making use of the laws of algebra. The proof of the laws of algebra in Exercise 4.1.4 do not require the result of this exercise, so there is no circularity in doing the exercises out of order and then making use of the laws of algebra here.

To show that $(-1) \times a = -a$ , we will first show $a + (-1)\times a = 0$ . We have $a + (-1)\times a = 1a + (-1)\times a = (1 + (-1))a = 0a$ by the laws of algebra (literally! We are not using any integer-specific properties here. Make sure you see how each equality follows from the laws of algebra). To show that $0a = 0$ , we can just compute using the definition of multiplication for integers. But in the spirit of this proof, let’s instead show this using just the laws of algebra. We have $0a = (0+0)a = 0a + 0a$ using the laws of algebra. Now we can add the additive inverse of $0a$ to both sides of the equation to get $-(0a) + 0a = -(0a) + 0a + 0a$ , which simplifies to $0 = 0a$ by the laws of algebra, as desired. Thus we have shown that $a + (-1)\times a = 0$ .

Now that we know $a + (-1)\times a = 0$ , we can add $-a$ to both sides of the equation, to get $-a + a + (-1)\times a = -a + 0$ . This simplifies to $(-1)\times a = -a$ as required.

Solutions

Exercise 4.1.1

March 18, 2020 Issa Rice 4 Comments

Exercise statement

Verify that the definition of equality on the integers is both reflexive and symmetric.

Hints

Read the proof of transitivity of equality in the book, which comes just after definition 4.1.1.

How to think about the exercise

This is a basic exercise that mostly tests your ability to write a proof similar to the one in the book. You don’t really need to understand what’s going on, as long as you can mimic example proofs.

I think that the book is somewhat confusing when it comes to talking about well-definedness/legitimacy of equality. In my preferred way of thinking about equality, the equality relation is automatically reflexive, symmetric, and transitive, because this is a fact about our language (mathematical English): when we write $x = y$ we mean that $x$ is the same thing as $y$ , so that obviously $y=x$ , because $y$ is the same thing as $x$ . So what I would do is introduce a separate relation symbol for the new notion of equality on the integers, such as $\sim$ , until we verify that this relation is reflexive, symmetric, and transitive. This is done in a footnote, but I wish it was done in the main text.

To be concrete, I would define $a{{-}\!{-}}b$ as the set of all pairs of natural numbers related to $(a,b)$ , i.e. $\{(c,d) \in \mathbf N \times \mathbf N : (a,b) \sim (c,d)\}$ . So now what does it mean to show that $\sim$ is e.g. symmetric? We want to show that given $x,y \in \mathbf Z$ , if $x\sim y$ then $y \sim x$ . How would that work? Let $x,y \in \mathbf Z$ . Since $x$ and $y$ are integers, there exist natural numbers $a,b,c,d$ such that $x = a{{-}\!{-}}b$ and $y = c{{-}\!{-}}d$ . (It is very important that we are distinguishing between $=$ and $\sim$ here! The first is a part of our language and automatically has all the nice properties, while the second is a “foreign” relation that we aren’t sure is a good one.) Suppose $x \sim y$ . This means $(a{{-}\!{-}}b) \sim (c{{-}\!{-}}d)$ , so $a+d = c+b$ . We have $c+b=a+d$ , so $y = (c{{-}\!{-}}d) \sim (a{{-}\!{-}}b) = x$ .

Here is another way to state my concern with the book’s approach. When the book writes $a{{-}\!{-}}b := \{(c,d) \in \mathbf N \times \mathbf N : (a,b) \sim (c,d)\}$ in the footnote, that is using equality, but this equality is set-theoretic (i.e. mathematical) equality, not the equality over the integers. If we write something like $a{{-}\!{-}}b=c{{-}\!{-}}d$ , then which one do we mean? Do we mean to say that $\{(e,f) \in \mathbf N \times \mathbf N : (a,b) \sim (e,f)\}$ is the same set as $\{(e,f) \in \mathbf N \times \mathbf N : (c,d) \sim (e,f)\}$ (in which case trivially we have all of the properties of equality, since they are inherited from the properties of set-theoretic equality), or do we just mean that $a+d=c+b$ ? Of course, these turn out to be the same thing once you’ve proven that equality on the integers is legitimate, but until we do that we have two ideas competing for the same symbol.

If none of that made sense, no problem; I would recommend coming back to this exercise after you’ve finished with the whole book — it will probably make more sense then.

Model solution

Let $a,b,c,d$ be natural numbers. To show that equality is reflexive, we must show that $a{{-}\!{-}}b =a{{-}\!{-}}b$ , i.e. $a+b=a+b$ . But this is true since equality on natural numbers is reflexive.

To show that equality is symmetric, suppose $a{{-}\!{-}}b = c{{-}\!{-}}d$ , i.e. $a+d = c+b$ . By symmetry of equality on natural numbers, we have $c+b = a+d$ , i.e. $c{{-}\!{-}}d = a{{-}\!{-}}b$ .

Solutions

Exercise 4.1.2

March 17, 2020 Issa Rice 8 Comments

Exercise statement

Show that the definition of negation on the integers is well-defined in the sense that if $(a{{-}\!{-}}b)=(a'{{-}\!{-}}b')$ , then $-(a{{-}\!{-}}b)=-(a'{{-}\!{-}}b')$ (so equal integers have equal negations).

Hints

Review the proof of Lemma 4.1.3 and try to write a similar proof.

How to think about the exercise

This is a straightforward exercise that tests your ability to write a correct proof that something is well-defined.

Model solution

Let $a,b,a',b'$ be natural numbers, and suppose $(a{{-}\!{-}}b)=(a'{{-}\!{-}}b')$ . By definition of negation (definition 4.1.4), we have $-(a{{-}\!{-}}b) = (b{{-}\!{-}}a)$ and $-(a'{{-}\!{-}}b') = (b'{{-}\!{-}}a')$ . To show that $(b{{-}\!{-}}a) = (b'{{-}\!{-}}a')$ we must show that $b+a' = b'+a$ . But we already know that $(a{{-}\!{-}}b)=(a'{{-}\!{-}}b')$ , which means that $a+b' = a'+b$ . But now $b+a'$ equals $a'+b$ by commutativity of addition (proposition 2.2.4), which equals $a+b'$ from what we said above, which equals $b'+a$ by commutativity of addition again.

Solutions

Exercise 2.2.6

March 16, 2020 Issa Rice 6 Comments

Exercise statement

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 \leq n$ ; this is known as the principle of backwards induction.

Hints

Apply induction to the variable $n$ .
For the statement to prove via induction, use the following: if $P(n)$ is true, then $P(m)$ is true for all $m \leq n$ .

How to think about the exercise

For this kind of abstract exercise, it helps to have an example in mind. Unfortunately, I am not aware of a convincing application of backwards induction. Pete L. Clark’s notes use a very similar result (which he calls upward-downward induction) to prove the AM-GM inequality, but he also says “It is not every day that one proves a result by Upward-Downward Induction”.

However, we can still play around with this a little. Suppose $P(4)$ is true. Then $P(3)$ is also true, which means that $P(2)$ is also true, which means that $P(1)$ is also true, which finally means that $P(0)$ is true. In other words, we have shown that $P(m)$ is true for all $m \leq 4$ , which is exactly what backwards induction claims. What if $P(5)$ is true? Then $P(4)$ is true. We already showed that if $P(4)$ is true, then $P(m)$ is true for all $m \leq 4$ . This means that we have now shown that $P(m)$ is true for all $m \leq 5$ .

I also like to translate these kinds of problems into formal logic notation, because otherwise it’s difficult to see with mathematical English where the parentheses are supposed to be. This exercise is asking us to prove the following: if $\forall m(P(m{{+}\!{+}}) \implies P(m)) \wedge P(n)$ then $\forall m (m \leq n\implies P(m))$ . For this kind of exercise, I encourage you to work with the formal logic notation as you’re solving the exercise, but make sure to convert back to mathematical English when writing up the exercise.

As with some induction problems, one thing you need to do is to decide on the statement you want to prove via induction. One mistake you could make is to show that $P(n)$ is true for all $n$ . This is not what you want to do! In fact, given just the information in the exercise statement, it is impossible to show that $P(n)$ is true for all $n$ . Another possibility is to use the statement “If $P(n)$ is true and $P(m{{+}\!{+}})$ implies $P(m)$ for all $m$ , then $P(m)$ is true for all $m \leq n$ .” This will work. However, it turns out that including the “ $P(m{{+}\!{+}})$ implies $P(m)$ for all $m$ ” part is not necessary — you can just assume it once at the start of the exercise, so that the actual induction step will be slightly cleaner.

Model solution 1

Let $P$ be a property pertaining to the natural numbers such that whenever $P(m{{+}\!{+}})$ is true, $P(m)$ is true.

Let $Q(n)$ be the following statement: if $P(n)$ is true, then $P(m)$ is true for all $m \leq n$ .

We shall show that $Q(n)$ is true for all $n$ using induction. For the base case, we must show $Q(0)$ . So suppose that $P(0)$ is true. We want to show that $P(m)$ is true for all $m \leq 0$ . By definition of inequality (definition 2.2.11), $m \leq 0$ means that $0 = m+a$ for some natural number $a$ . By corollary 2.2.9, we have $m=0$ . In other words, $m \leq 0$ implies $m=0$ , so showing that $P(m)$ for all $m \leq 0$ is equivalent to showing $P(0)$ , which we already know. This completes the base case.

Now suppose $Q(n)$ is true. We must show that $Q(n{{+}\!{+}})$ is true. By definition of $Q$ , $Q(n{{+}\!{+}})$ is the statement “if $P(n{{+}\!{+}})$ is true, then $P(m)$ is true for all $m \leq n{{+}\!{+}}$ ”, so suppose that $P(n{{+}\!{+}})$ is true. We need to show that $P(m)$ is true for all $m \leq n{{+}\!{+}}$ . We know that whenever $P(m{{+}\!{+}})$ is true, $P(m)$ is true, so for $m=n$ in particular this means that if $P(n{{+}\!{+}})$ is true then $P(n)$ is true. Since $P(n{{+}\!{+}})$ is true, we see that $P(n)$ is true. By the induction hypothesis we thus have $P(m)$ for all $m \leq n$ . Now let $m \leq n{{+}\!{+}}$ . We want to show that $P(m)$ is true. If we can show that $m \leq n$ or $m=n{{+}\!{+}}$ , then we will be done, because in either case we have already shown that $P(m)$ is true. To show that $m \leq n$ or $m=n{{+}\!{+}}$ , we will show that $m\ne n{{+}\!{+}}$ implies $m \leq n$ . Suppose $m \ne n{{+}\!{+}}$ . This means $m < n{{+}\!{+}}$ by definition 2.2.11. By proposition 2.2.12(e), we have $m{{+}\!{+}} \leq n{{+}\!{+}}$ , i.e. $m+1 \leq n+1$ . By proposition 2.2.12(d) this means $m\leq n$ as required. This closes the induction.

Now let $n$ be a natural number, and suppose $P(n)$ is true. By our work above, we know that $Q(n)$ is true. This means that $P(m)$ is true for all natural numbers $m \leq n$ as required.

Model solution 2

Thanks to Charlene for this solution.

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. We want to show that $P(m)$ is true for all $m \leq n$ .

Let $Q(k)$ be the statement: for all natural numbers $m$ , if $m+k = n$ then $P(m)$ is true. (The intuition here is that $Q(k)$ is basically the statement that $P(n-k)$ is true. But we can’t say $P(n-k)$ since we haven’t defined subtraction yet! So that’s why we do some first-order logic trickery to say what we want given our current tools. We know that $P(n-0)$ is true by assumption, and the rule that whenever $P(m{{+}\!{+}})$ is true, then $P(m)$ is true, means that we can go from $P(n-0)$ to $P(n-1)$ , from $P(n-1)$ to $P(n-2)$ , and so on, all the way to $P(n-n)$ .)

We will show using induction that $Q(k)$ is true for all natural numbers $k$ . For the base case, $k=0$ , we want to show that for all $m$ , if $m+0=n$ then $P(m)$ is true. So let $m$ be a number, and suppose $m+0=n$ . Then we have $m=m+0=n$ . Since we assumed $P(n)$ is true, this means $P(m)$ is true as required.

Now suppose inductively that $Q(k)$ is true. We want to show that $Q(k{{+}\!{+}})$ is true. That is, we want to show that for all $m$ , if $m+(k{{+}\!{+}}) = n$ then $P(m)$ . So let $m$ be given, and suppose $m+(k{{+}\!{+}})=n$ . Thus we have $(m{{+}\!{+}}) + k = n$ . By our inductive hypothesis $Q(k)$ , this means that $P(m{{+}\!{+}})$ is true. We also know that whenever $P(m{{+}\!{+}})$ is true, then $P(m)$ is true. Thus $P(m)$ is true. This shows that $Q(k{{+}\!{+}})$ is true, and closes our induction.

Now suppose $m \leq n$ . We want to show that $P(m)$ is true. But $m \leq n$ means that there exists some $k$ such that $m+k=n$ . By what we showed above, we know that $Q(k)$ is true. And $Q(k)$ says that if $m+k=n$ , then $P(m)$ is true, as required.

Solutions

Exercise 2.2.2

March 16, 2020 Issa Rice 33 Comments

Exercise statement

Prove Lemma 2.2.10.

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

Hints

Use induction.

How to think about the exercise

This exercise asks us to show that it makes sense to talk about the predecessor of a positive number. For instance, the predecessor of $3$ is $2$ . Why is there a hypothesis that $a$ must be a positive number? Because by axiom 2.3 the number $0$ does not have a predecessor (within the set of natural numbers).

This exercise is almost a standard induction exercise, but not quite. The one subtlety is that the inductive hypothesis is never used. This might seem suspicious to you, but it’s actually harmless.

Model solution

Let $P(a)$ be the statement “If $a$ is positive, then there is a unique natural number $b$ such that $b{{+}\!{+}} = a$ .” We shall induct on $a$ . The base case is vacuously true, since $0$ is not a positive number (definition 2.2.7).

Now suppose inductively that $P(a)$ is true. We must show that $P(a{{+}\!{+}})$ is true. To show that $P(a{{+}\!{+}})$ is true, it suffices to show that there is a unique number $b$ such that $b{{+}\!{+}} = a{{+}\!{+}}$ (this is because given statements $p,q$ , if $q$ is true, then $p \implies q$ is also true no matter what $p$ says). To do this, we must show two things: (1) there is a natural number $b$ such that $b{{+}\!{+}} = a{{+}\!{+}}$ ; (2) if $c$ is a natural number such that $c{{+}\!{+}} = a{{+}\!{+}}$ , then $c=b$ . To show (1), let $b:=a$ . Then indeed we have $b{{+}\!{+}} = a{{+}\!{+}}$ . To show (2), let $c$ be a natural number such that $c{{+}\!{+}} = a{{+}\!{+}}$ . Then by axiom 2.4, we see that $c=a$ . But we also know $b=a$ , so $c=b$ as required. This closes the induction.

Solutions

Exercise 2.2.1

March 16, 2020 Issa Rice 8 Comments

Exercise statement

Prove Proposition 2.2.5.

Proposition 2.2.5 (Addition is associative). For any natural numbers $a,b,c$ , we have $(a+b)+c = a + (b+c)$ .

Hints

Fix two of the variables and induct on the third.

How to think about the exercise

This is a simple induction exercise; it just tests your ability to write an induction proof and make use of the definition of addition. This sort of exercise requires no thinking (once you get the hang of things): at each step, you just do the next obvious thing.

Model solution

We shall fix $b,c$ and induct on $a$ . For the base case, we want to show $(0+b)+c = 0 + (b+c)$ . By definition of addition, $0+b = b$ , so $(0+b)+c = b+c$ . Again by definition of addition, $0 + (b+c) = b+c$ . Thus, $(0+b)+c = 0 + (b+c)$ as required.

Now suppose inductively that $(a+b)+c = a + (b+c)$ . We wish to show that $((a{{+}\!{+}})+b)+c = (a{{+}\!{+}}) + (b+c)$ . By definition of addition, $((a{{+}\!{+}}) + b) + c = ((a + b){{+}\!{+}}) + c = ((a+b) + c){{+}\!{+}}$ . Similarly, $(a{{+}\!{+}}) + (b+c) = (a + (b+c)){{+}\!{+}}$ ; by the inductive hypothesis, this is $((a+b)+c){{+}\!{+}}$ . In other words, both $((a{{+}\!{+}}) + b)+c$ and $(a{{+}\!{+}}) + (b+c)$ are equal to $((a+b)+c){{+}\!{+}}$ . This closes the induction.