Why can we define the set of integers using equivalence relations?

[evinda]

Hi! (Smirk)

According to my lecture notes:

Constitution of integers

Equivalence relation $R$ on $\omega \times \omega$

For $\langle m,n \rangle \in \omega^2$ and $\langle k,l \rangle \in \omega^2$ we say that $\langle m,n \rangle R \langle k,l \rangle$ iff $m+l=n+k$.

First Step: $R$ is an equivalence relation.

Second step: We define $\mathbb{Z}=\omega^2 /_{ R}=\{ [\langle m, n \rangle]_{R}: m, n \in \omega\}$
Could you explain me why we can define the set of integers like that? (Thinking)

 

[Evgeny.Makarov]

If you have another definition of $\Bbb Z$, there is an isomorphism $f:\omega^2/R\to\Bbb Z$, $f(\langle m,n\rangle)=m-n$. This statement is not entirely precise, but it conveys the idea.

 

[evinda]

I haven't understood why we can identify $\mathbb{Z}$ with all the $[\langle m,n \rangle]$ such that $m+l=n+k$.. (Worried)

 

[Evgeny.Makarov]

I understood what you did not understand, and I responded to that in post #2. Now do some research, consider several pairs equivalent w.r.t. $R$ and make sure that the function I wrote is well-defined on $\omega^2/R$ (i.e., does not depend on the choice of a pair in the equivalence class). You need to understand the idea behind this correspondence.

 

[evinda]

So if we take for example $m=2, n=5$ then $f(\langle 2,5 \rangle)=2-5=-3$.

This would we mean that we identify $\mathbb{Z}$ with $\mathbb{Z}=\{\langle m,n \rangle \in \omega^2: m-n=3 \}$, right? Why can we do this? (Sweating)

 

[Evgeny.Makarov]

This would we mean that we identify $\mathbb{Z}$ with $\mathbb{Z}=\{\langle m,n \rangle \in \omega^2: m-n=3 \}$, right?

No. What made you think so?

 

[evinda]

No. What made you think so?

I don't know... I am confused now...
How do we use the function $f(\langle m,n \rangle)=m-n$?

 

[Evgeny.Makarov]

It's an isomorphism between $\omega^2/R$ and $\Bbb Z$. It identifies pairs of natural numbers with corresponding integers.

 

[evinda]

It's an isomorphism between $\omega^2/R$ and $\Bbb Z$. It identifies pairs of natural numbers with corresponding integers.

So you mean that it has the same function as the equivalence classes with which we define the set of integers?

 

[Evgeny.Makarov]

So you mean that it has the same function as the equivalence classes with which we define the set of integers?

I am not sure what the bold "it" in your quote refers to, and I don't know how equivalence classes can have a function ("has the same function as the equivalence classes"). Perhaps you need to review all the concepts involved here (equivalence relation, equivalence classes and so on) and see examples of them.

 

[evinda]

I am not sure what the bold "it" in your quote refers to, and I don't know how equivalence classes can have a function ("has the same function as the equivalence classes"). Perhaps you need to review all the concepts involved here (equivalence relation, equivalence classes and so on) and see examples of them.

With it I mean the function $f(\langle m,n \rangle)$.

Suppose that $R$ is an equivalence relation and $A=fld(R)$.
For all $a \in A$ we define the set $[a]_R=\{x: xRa \}$.In this case, we have $[\langle m,n \rangle]_R$.
So $[\langle m,n \rangle]$ contains all the ordered pairs $\langle x,y \rangle$ such that $\langle x,y \rangle R \langle m,n \rangle \leftrightarrow x+n=y+m$, right?

 

[Evgeny.Makarov]

Yes.

Note that $fld(R)$ is not a universally accepted notation or definition.

 

[evinda]

So if we consider $m=1, n=1$ then $\langle x,y \rangle \in [\langle 1,1 \rangle]_R \iff x+1=y+1 \Rightarrow x=y$.

If $m=3, n=5$ then $\langle x,y \rangle \in [\langle 3,5 \rangle]_R \iff x+3=y+5 \Rightarrow x=y+2$.

Right?

 

[Evgeny.Makarov]

So if we consider $m=1, n=1$ then $\langle x,y \rangle \in [\langle 1,1 \rangle]_R \iff x+1=y+1 \Rightarrow x=y$.

Yes.

If $m=3, n=5$ then $\langle x,y \rangle \in [\langle 3,5 \rangle]_R \iff x+3=y+5 \Rightarrow x=y+2$.

It should say $x+5=y+3$.

In general, $\langle x,y\rangle\in[\langle m,n\rangle]_R\iff x-y=m-n$. That is, if we consider natural numbers as integers. Otherwise, we cannot subtract natural numbers. That's why the relation $R$ is defined using addition and not subtraction.

 

[evinda]

So does this mean that the set of integers is a set of ordered pairs of which the elements belong to $\omega$ ? (Thinking)

 

[Evgeny.Makarov]

So does this mean that the set of integers is a set of ordered pairs of which the elements belong to $\omega$ ?

If that were so, than post #1 would define $\Bbb Z$ as $\omega^2$. As it is, it defines $\Bbb Z$ as $\omega^2/R$.

 

[evinda]

If that were so, than post #1 would define $\Bbb Z$ as $\omega^2$. As it is, it defines $\Bbb Z$ as $\omega^2/R$.

Isn't $\{ [\langle m,n \rangle]_R:m,n \in \omega \}$ a set of ordered pairs with the following property?$$\langle x,y \rangle \in \{ [\langle m,n \rangle]_R:m,n \in \omega \} \leftrightarrow x-y=m-n$$

Or have I understood it wrong? (Worried)

 

[Evgeny.Makarov]

Isn't $\{ [\langle m,n \rangle]_R:m,n \in \omega \}$ a set of ordered pairs with the following property?$$\langle x,y \rangle \in \{ [\langle m,n \rangle]_R:m,n \in \omega \} \leftrightarrow x-y=m-n$$

Or have I understood it wrong?

You have understood it wrong. A set cannot have additional conditions on being a member. That is, you cannot declare a set $\{x\mid P(x)\}$ and then add an additional requirement $x\in A\leftrightarrow Q(x)$. No, $x\in A\leftrightarrow P(x)$, period. I am not sure, but you seem to be doing this with your phrase "a set of ordered pairs with the following property" (but I may be mistaken). In fact, your additional condition does not makes sense because the left-hand side does depend on $m$ and $n$ (their scope is limited to curly braces and they are not visible from outside), while the right-hand side refers to $m$ and $n$. Most importantly, $\{ [\langle m,n \rangle]_R:m,n \in \omega \}$ is not a set of pairs, but a set of equivalence classes, where each class is in turn a set of pairs.

Perhaps you need to review all the concepts involved here (equivalence relation, equivalence classes and so on) and see examples of them.

Also, I wish you were more open about your doubts regarding definitions and basic theory. You seem to be hiding that behind details of concrete examples (though this is a common problem). It should not take 17 posts to figure out that the problem lies in a misunderstanding of a definition.

 

[evinda]

So, is $\{ [\langle m,n \rangle ]_R: m, n \in \omega \}$ the set that contains all the possible results from the difference of two natural numbers?

 

[Evgeny.Makarov]

If by the "result from the difference" of $m$ and $n$ you mean $m-n$, then of course not. As I said, this set contains not numbers and not pairs of numbers, but sets of pairs of numbers. The definition of the set does not use subtraction at all.

 

[evinda]

It contains all the equivalence classes modulo $R$..
These are equal to the difference of two natural numbers, but we cannot use this fact since we haven't defined subtraction of natural numbers, right?

 

[Evgeny.Makarov]

It contains all the equivalence classes modulo $R$..
These are equal to the difference of two natural numbers

Are you saying that each equivalence class is equal to the difference of some natural numbers? This is comparing apples to oranges. An equivalence class is a set. Of pairs. Of natural numbers. While the difference of two natural numbers is a single integer.

Edit: They are, in fact, equal if you define integers as in post #1, i.e., as some sets of pairs of natural numbers. But if you have some other definition of integers or consider them axiomatically (as some objects that satisfy certain axioms), then it is important to understand the difference.

 

[evinda]

I see... What is the main difference between the operation: $\langle m,n \rangle+ \langle k,l \rangle:= \langle m+k, n+l \rangle$ and this one: $[\langle m,n \rangle]_R+[\langle k,l \rangle]_R=[\langle m+k, n+l \rangle]_R$, where $\langle m,n \rangle, \langle k,l \rangle \in \omega^2$ ?

 

[Evgeny.Makarov]

One operation is defined on pairs, the other on sets of pairs.

Note that for the second operation to make sense, its result must be independent of the choice of particular elements from the two argument sets. Namely, the second operation proceeds as follows. Given two equivalence classes (i.e., sets of pairs) $A$ and $B$, choose some pair $\langle m,n\rangle$ from $A$ and some pair $\langle k,l\rangle$ from $B$ and return the equivalence class of $\langle m+k,n+l\rangle$. Once the choice of $\langle m,n\rangle$ and $\langle k,l\rangle$ is made, the pair $\langle m+k,n+l\rangle$ and its equivalence class are determined unambiguously. However, pairs from $A$ and $B$ can be chosen in many different ways. One needs to make sure that the result of this operation does not depend on that choice. That is, if we choose another pair $\langle m',n'\rangle$ from $A$ and another pair $\langle k',l'\rangle$ from $B$, the result is still $[\langle m+k,n+l\rangle]_R$. If one chooses $\langle m',n'\rangle$ and $\langle k',l'\rangle$, the definition says that the result is $[\langle m'+k',n'+l'\rangle]_R$.

Well, I realized that it would be too long to write the reasoning in full here since it is a standard topic in equivalence relations. See also Wikipedia. I am not even sure if this is new to you. If it is, I strongly recommend reading about it in your lecture notes or elsewhere and getting very comfortable with this. Functions on equivalence classes is a standard topic in mathematics.

 

[evinda]

I understand (Nod)

So if we take for example $m=5, n=3, k=6, l=16$ we will have that:

$$[\langle 5,3 \rangle]_R+[\langle 6,16 \rangle]_R=[\langle 11, 19 \rangle]_R$$

and that means that $(5-3)+(6-16)=(5+6)-(3+16)=11-19=-8$, right?

And if we take $m'=8, n'=6, k'=11, l'=21$ we don't have to calculate $[\langle 8,6 \rangle]_R+[\langle 11,21 \rangle]_R$ because we know that $m'-n' \equiv m-n \mod R,\ k-l\equiv k'-l' \mod R$, right?

 

[Evgeny.Makarov]

So if we take for example $m=5, n=3, k=6, l=16$ we will have that:

$$[\langle 5,3 \rangle]_R+[\langle 6,16 \rangle]_R=[\langle 11, 19 \rangle]_R$$

Yes.

and that means that $(5-3)+(6-16)=(5+6)-(3+16)=11-19=-8$, right?

That's the idea behind the definition. If you need anything more precise, you need to say in which sense the first equality "means" the second one.

And if we take $m'=8, n'=6, k'=11, l'=21$ we don't have to calculate $[\langle 8,6 \rangle]_R+[\langle 11,21 \rangle]_R$ because we know that $m'-n' \equiv m-n \mod R,\ k-l\equiv k'-l' \mod R$, right?

I am not sure what $m'-n' \equiv m-n \mod R$ means. It simply holds that $m'-n' = m-n$. The difficulty is proving the general fact that the original definition of addition on equivalence classes is well-defined. Once you know this, picking other representatives (pairs) does not indeed lead to a different result.

 

[evinda]

I am not sure what $m'-n' \equiv m-n \mod R$ means. It simply holds that $m'-n' = m-n$.

Yes, that's what I meant.. (Nod)

Could we show like that that $R$ is an equivalence relation? (Thinking)

Suppose that $\langle m,n \rangle \in \omega^2, \langle k,l \rangle \in \omega^2, \langle d,e \rangle \in \omega^2 $

We have that $m+n=m+n$ so $R$ is reflexive.

$\langle m,n \rangle R \langle k,l \rangle \leftrightarrow m+l=n+k \overset{\text{commutativity}}{\leftrightarrow} l+m=k+n \leftrightarrow \langle k,l \rangle R \langle m,n \rangle$

So $R$ is symmetric.

$\langle m,n \rangle R \langle k,l \rangle \wedge \langle k,l \rangle R \langle d,e \rangle \leftrightarrow m+l=n+k \wedge k+e=l+d \\ \leftrightarrow m+l+e=n+k+e \wedge k+e=l+d \leftrightarrow m+l+e=n+l+d \leftrightarrow m+e=n+d \leftrightarrow \langle m,n \rangle R \langle d,e \rangle$

Thus, $R$ is transitive.

 

[Evgeny.Makarov]

$\langle m,n \rangle R \langle k,l \rangle \wedge \langle k,l \rangle R \langle d,e \rangle \leftrightarrow m+l=n+k \wedge k+e=l+d \\ \leftrightarrow m+l+e=n+k+e \wedge k+e=l+d \leftrightarrow m+l+e=n+l+d \leftrightarrow m+e=n+d \leftrightarrow \langle m,n \rangle R \langle d,e \rangle$

I agree with the $\to$ direction. I don't think $\leftarrow$ always holds, but it is not needed. Good job!

 

[evinda]

I agree with the $\to$ direction. I don't think $\leftarrow$ always holds, but it is not needed. Good job!

(Happy)

Thank you very much!