Exercise 4.1.1

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

4 thoughts on “Exercise 4.1.1”

Pingback: Exercise 4.2.1 | Tao Analysis Solutions

I think you are wrong when you think that x=y means that x is the same as y. Tao teaches us to make correct definitions in mathematics that obey the laws of logic. Let’s say we want to redefine integers. Let a—b = c—d if and only if a = d. We can notice that our definition of equality is ill-defined. Why? The law of symmetry, for example, does not hold. Let a—b = c—d <=> a=d and let c not equal b. Suppose that c—d = a —b, then the statement is equivalent to the statement c= b. Contradiction! So c—d is not equal to a—b. That is, the law of symmetry does not hold for all integers. It’s the same with addition. . Let’s define equality correctly from the point of view of the laws of logic. Let a—b = c—d if and only if a=c. Let’s define addition as follows (a—b) + (c—d) = b+d. Take a certain a’—b’ = a—b, where b’ is not equal to b, these two numbers are equal since a’=a. Then (a’—b’) + (c—d) = b’+d. Suppose (a—b) + (c—d) = (a’—b’) + (c—d). Then b+d = b’+d. Let’s use the cancellation law for natural numbers: b=b’. Contradiction! So the statement (a—b) + (c—d) = (a’—b’) + (c—d) is false.The law of the substitute failed!

LikeLike

Issa Rice says:

September 23, 2023 at 7:49 pm

I don’t disagree with anything you said. But you seem to be talking about a different thing than what I was talking about in the post. My point was a pedagogical one: it’s confusing for students to have new meanings for the equality symbol introduced, and things would be much clearer if we distinguished between equality and equivalence.

LikeLike

I probably understood you. I think Tao just didn’t give an explicit hint regarding the fact that the symbol “=” should be perceived purely mathematically. Although in set theory it already meant something more than in the chapter about natural numbers. ∀a∀b([a∈A => a∈B] /\ [b = B => b = A]) <=> A=B. (Tao: A = B if and only if every element x of A belongs also to B, and every element y of B belongs also to A.) After he asks to check the symmetry, reflexivity, etc. Tao noticed that {a,a} = {a}. That is, already here we see that “=” is something else. “=” already in chapter 3 does not imply “the same”. Perhaps Tao should have dedicated two sentences with regard to “=”, but I think this is not necessary at all. But I’m not completely sure I’m right. It seems to me, on the contrary, I would be confused if we didn’t use “=” initially. Perhaps you know better.

LikeLike

Leave a comment Cancel reply

Pingback: Exercise 4.2.1 | Tao Analysis Solutions
Vsevolod says:

September 23, 2023 at 3:48 pm

I think you are wrong when you think that x=y means that x is the same as y. Tao teaches us to make correct definitions in mathematics that obey the laws of logic. Let’s say we want to redefine integers. Let a—b = c—d if and only if a = d. We can notice that our definition of equality is ill-defined. Why? The law of symmetry, for example, does not hold. Let a—b = c—d <=> a=d and let c not equal b. Suppose that c—d = a —b, then the statement is equivalent to the statement c= b. Contradiction! So c—d is not equal to a—b. That is, the law of symmetry does not hold for all integers. It’s the same with addition. . Let’s define equality correctly from the point of view of the laws of logic. Let a—b = c—d if and only if a=c. Let’s define addition as follows (a—b) + (c—d) = b+d. Take a certain a’—b’ = a—b, where b’ is not equal to b, these two numbers are equal since a’=a. Then (a’—b’) + (c—d) = b’+d. Suppose (a—b) + (c—d) = (a’—b’) + (c—d). Then b+d = b’+d. Let’s use the cancellation law for natural numbers: b=b’. Contradiction! So the statement (a—b) + (c—d) = (a’—b’) + (c—d) is false.The law of the substitute failed!

LikeLike

1. Issa Rice says:
  
  September 23, 2023 at 7:49 pm
  
  I don’t disagree with anything you said. But you seem to be talking about a different thing than what I was talking about in the post. My point was a pedagogical one: it’s confusing for students to have new meanings for the equality symbol introduced, and things would be much clearer if we distinguished between equality and equivalence.
  
  LikeLike
Vsevolod says:

September 23, 2023 at 10:17 pm

I probably understood you. I think Tao just didn’t give an explicit hint regarding the fact that the symbol “=” should be perceived purely mathematically. Although in set theory it already meant something more than in the chapter about natural numbers. ∀a∀b([a∈A => a∈B] /\ [b = B => b = A]) <=> A=B. (Tao: A = B if and only if every element x of A belongs also to B, and every element y of B belongs also to A.) After he asks to check the symmetry, reflexivity, etc. Tao noticed that {a,a} = {a}. That is, already here we see that “=” is something else. “=” already in chapter 3 does not imply “the same”. Perhaps Tao should have dedicated two sentences with regard to “=”, but I think this is not necessary at all. But I’m not completely sure I’m right. It seems to me, on the contrary, I would be confused if we didn’t use “=” initially. Perhaps you know better.

LikeLike