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

  • MHB
  • Thread starter evinda
  • Start date
  • Tags
    Integers
In summary: No, you have not misunderstood it. $\{ [\langle m,n \rangle]_R:m,n \in \omega \}$ is a set of ordered pairs with the following property: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 \leftright
  • #1
evinda
Gold Member
MHB
3,836
0
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)
 
Physics news on Phys.org
  • #2
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.
 
  • #3
I haven't understood why we can identify $\mathbb{Z}$ with all the $[\langle m,n \rangle]$ such that $m+l=n+k$.. (Worried)
 
  • #4
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.
 
  • #5
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)
 
  • #6
evinda said:
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?
 
  • #7
Evgeny.Makarov said:
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$?
 
  • #8
It's an isomorphism between $\omega^2/R$ and $\Bbb Z$. It identifies pairs of natural numbers with corresponding integers.
 
  • #9
Evgeny.Makarov said:
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? :confused:
 
  • #10
evinda said:
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.
 
  • #11
Evgeny.Makarov said:
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?
 
  • #12
Yes.

Note that $fld(R)$ is not a universally accepted notation or definition.
 
  • #13
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?
 
  • #14
evinda said:
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.

evinda said:
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.
 
  • #15
So does this mean that the set of integers is a set of ordered pairs of which the elements belong to $\omega$ ? (Thinking)
 
  • #16
evinda said:
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$.
 
  • #17
Evgeny.Makarov said:
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)
 
  • #18
evinda said:
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.

Evgeny.Makarov said:
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.
 
  • #19
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?
 
  • #20
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.
 
  • #21
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?
 
  • #22
evinda said:
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.
 
  • #23
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$ ?
 
  • #24
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.
 
  • #25
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?
 
  • #26
evinda said:
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.

evinda said:
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.

evinda said:
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.
 
  • #27
Evgeny.Makarov said:
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.
 
  • #28
evinda said:
$\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!
 
  • #29
Evgeny.Makarov said:
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!
 

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

1. What is an equivalence relation?

An equivalence relation is a relation between two objects that satisfies three properties: reflexivity, symmetry, and transitivity. This means that for any given set of objects, the relation must be reflexive (each object is related to itself), symmetric (if object A is related to object B, then object B is also related to object A), and transitive (if object A is related to object B and object B is related to object C, then object A is also related to object C).

2. How does an equivalence relation define a set of integers?

An equivalence relation can be used to partition a set into different equivalence classes. In the case of integers, an equivalence relation can be defined as the relation of 'having the same remainder when divided by a certain number'. This means that all integers that have the same remainder when divided by this number will be in the same equivalence class. This allows us to define the set of integers as a collection of these equivalence classes.

3. Why is it useful to define the set of integers using equivalence relations?

Defining the set of integers using equivalence relations allows us to organize the integers into distinct groups based on a specific property. This can make it easier to study and understand the properties and relationships between integers. It also allows us to use techniques from set theory and equivalence relations to prove mathematical theorems and solve problems involving integers.

4. Can other sets be defined using equivalence relations?

Yes, other sets can also be defined using equivalence relations. For example, the set of rational numbers can be defined as equivalence classes of ordered pairs of integers with a common denominator. This allows us to compare and order rational numbers using the same techniques used for integers.

5. Are there other ways to define the set of integers?

Yes, the set of integers can also be defined using other mathematical structures such as the Peano axioms or the successor function. However, using equivalence relations is one of the most common and useful ways to define the set of integers.

Similar threads

Replies
5
Views
2K
Replies
0
Views
435
Replies
1
Views
1K
Replies
6
Views
2K
Replies
3
Views
3K
Replies
1
Views
2K
Replies
2
Views
1K
Replies
3
Views
4K
Back
Top