Exercise 5.3.1

March 26, 2020 Issa Rice Leave a comment

Exercise statement

Prove Proposition 5.3.3.

Proposition 5.3.3 (Formal limits are well-defined). Let $x = \mathrm{LIM}_{n \to \infty} a_n$ , $y = \mathrm{LIM}_{n \to \infty} b_n$ , and $z = \mathrm{LIM}_{n \to \infty} c_n$ be real numbers. Then, with the above definition of equality for real numbers, we have $x=x$ . Also, if $x=y$ , then $y=x$ . Finally, if $x=y$ and $y=z$ , then $x=z$ .

Hints

You may find Proposition 4.3.7 to be useful.

How to think about the exercise

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

Model solution

To show that $x=x$ we need to show that $(a_n)_{n=1}^\infty$ is equivalent to $(a_n)_{n=1}^\infty$ . So let $\varepsilon > 0$ . Then for $N:=1$ we have $|a_n - a_n| = 0 < \varepsilon$ for every $n\geq N$ , so $x=x$ as desired.

To show that $x=y$ implies $y=x$ , suppose $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ are equivalent. This means that for every $\varepsilon > 0$ there is some $N\geq1$ such that for all $n\geq N$ we have $|a_n-b_n| \leq \varepsilon$ . By Proposition 4.3.3(d) we know that $|a_n-b_n| = |b_n-a_n|$ , so the above is actually also saying that $(b_n)_{n=1}^\infty$ and $(a_n)_{n=1}^\infty$ are equivalent. More formally, let $\varepsilon > 0$ . Then by the equivalence of $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ we are given some $N\geq 1$ . Then for $n\geq N$ we have $|b_n-a_n| = |a_n-b_n| \leq \varepsilon$ .

Finally suppose $x=y$ and $y=z$ . This means that $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ are equivalent, and that $(b_n)_{n=1}^\infty$ and $(c_n)_{n=1}^\infty$ are equivalent. Let $\varepsilon >0$ be given. Then there exists $N_1 \geq 1$ such that $a_n$ is $\varepsilon/2$ -close to $b_n$ for all $n\geq N_1$ , and there exists $N_2\geq 1$ such that $b_n$ is $\varepsilon/2$ -close to $c_n$ for all $n\geq N_2$ . So if we pick $N:=\max(N_1,N_2)$ then for $n\geq N$ we have both $n\geq N_1$ and $n\geq N_2$ . Thus by Proposition 4.3.7(c) we see that $a_n$ and $c_n$ are $\varepsilon$ -close. Thus $x=z$ as required.

Solutions

Exercise 5.2.2

March 25, 2020 Issa Rice 13 Comments

Exercise statement

Let $\varepsilon > 0$ . Show that if $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ are eventually $\varepsilon$ -close, then $(a_n)_{n=1}^\infty$ is bounded if and only if $(b_n)_{n=1}^\infty$ is bounded.

Hints

Use the triangle inequality.

How to think about the exercise

This exercise is similar to both Exercise 5.1.1 and Exercise 5.2.1. I don’t have anything to add beyond what I said in those posts.

Model solution

Suppose $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ are eventually $\varepsilon$ -close, and suppose $(a_n)_{n=1}^\infty$ is bounded. Since $(a_n)_{n=1}^\infty$ is bounded, there exists a number $M_1 \geq 0$ such that $|a_n| \leq M_1$ for all $n \geq 1$ . Since $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ are eventually $\varepsilon$ -close, there exists $N \geq 1$ such that $|a_n - b_n| \leq \varepsilon$ for all $n \geq N$ . By the triangle inequality we have $|b_n| - |a_n| \leq |a_n - b_n|$ (to get this, you can start with the ordinary triangle inequality $|x+y| \leq |x| + |y|$ and then substitute $x:= a_n$ and $y := b_n - a_n$ ), so $|b_n| \leq |a_n| + \varepsilon \leq M_1 + \varepsilon$ for all $n \geq N$ . This bounds the sequence $(b_n)_{n=N}^\infty$ (i.e. the infinite tail of $(b_n)_{n=1}^\infty$ ). By Lemma 5.1.14, the finite sequence $b_1, \ldots, b_{N-1}$ is also bounded, say by the number $M_2 \geq 0$ . Thus we can take $M := M_1 + M_2 + \varepsilon$ as a bound on $(b_n)_{n=1}^\infty$ .

For the other direction, just interchange $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ in the above.

Solutions

Exercise 5.2.1

March 24, 2020 Issa Rice 5 Comments

Exercise statement

Show that if $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ are equivalent sequences of rationals, then $(a_n)_{n=1}^\infty$ is a Cauchy sequence if and only if $(b_n)_{n=1}^\infty$ is a Cauchy sequence.

Hints

Try to use the triangle inequality.

How to think about the exercise

The intuition for this exercise is simple: eventually all of the $a$ s are close to each other, and the $b$ s are close to the $a$ s, so all of the $b$ s must be close to each other as well.

For this kind of exercise I immediately know that I’m going to be juggling a bunch of $\varepsilon$ s and $N$ s and stringing everything together using the triangle inequality somehow. Why do I know this? Mainly because I’ve worked enough such exercises before.

We’re going to be assuming that $(a_n)_{n=1}^\infty$ is Cauchy and showing that $(b_n)_{n=1}^\infty$ is Cauchy, so the end result is that we want to show for every $\varepsilon > 0$ there is some $N\geq 1$ such that $|b_j - b_k| \leq \varepsilon$ for every $j,k \geq N$ . This means that we will have to find some $N$ that will work, and this $N$ will somehow have to come from the fact that $(a_n)_{n=1}^\infty$ is Cauchy and/or the fact that $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ are equivalent sequences. Since at the moment it’s not clear what $N$ could possibly work, I find it easiest with this kind of exercise to just forget about all of the quantifiers and see what we would need at the very end.

Well, we want to show $|b_j - b_k| \leq \varepsilon$ . And by the end of the proof, we will have something like $|a_j - a_k| \leq \varepsilon$ to work with (because $(a_n)_{n=1}^\infty$ is Cauchy), and also something like $|a_n - b_n| \leq \varepsilon$ to work with (because $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ are equivalent). So we need to bridge the gap between the inequalities we have and the inequality we want, and that is where the triangle inequality will come in. We want to write $|b_j - b_k|$ as $|b_j - a_j + a_j - a_k + a_k - b_k|$ by adding and subtracting the same terms. How did I figure this out? Again, it’s mostly from doing similar exercises before. I needed to combine various inequalities, so I wanted to add and subtract some term, but I just didn’t know which. To figure out which term, I knew that either the index had to match (to make use of the sequence equivalence property) or I need to have two $a$ s with different indexes (to make use of the Cauchy property). So a moment-by-moment thought process might look something like this:

write $|b_j$
there is a $b_j$ so I need to match the index with $-a_j$
since I wrote $-a_j$ now I need to cancel this out with $+a_j$ , so that I am effectively adding $0$
that still leaves $-b_k$ hanging there
to balance the $-b_k$ I need to match the index with $+a_k$
since I wrote $+a_k$ now I need to cancel this out with $-a_k$
that leaves $+a_j -a_k$ in the middle—how convenient!

Model solution

Let $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ be equivalent sequences of rational numbers. Suppose $(a_n)_{n=1}^\infty$ is Cauchy. We want to show that $(b_n)_{n=1}^\infty$ is Cauchy. So let $\varepsilon > 0$ be given. Since $(a_n)_{n=1}^\infty$ is Cauchy, we have some $N_1 \geq 1$ such that $|a_j - a_k| \leq \varepsilon/3$ for all $j,k \geq N_1$ . Also, since $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ are equivalent, there is some $N_2 \geq 1$ such that $|a_n - b_n| \leq \varepsilon/3$ for all $n \geq N_2$ . Pick $N := \max(N_1,N_2)$ , and let $j,k \geq N$ . Since $j,k \geq N_1$ we have $|a_j - a_k| \leq \varepsilon/3$ . Also since $j,k \geq N_2$ we have $|b_j - a_j| \leq \varepsilon/3$ and $|a_k - b_k| \leq \varepsilon/3$ . By the triangle inequality we have $|b_j - b_k| \leq |b_j - a_j| + |a_j - a_k| + |a_k - b_k| \leq \varepsilon$ as required.

For the other direction of the implication, we can just repeat the proof above by switching the places of $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ .

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