0
$\begingroup$

I am familiar with all 3 of the entities I have listed in my question. I know the definitions of "reflexive", "symmetric", and "transitive". However, I am afraid I do not mechanistically understand the "flow" of how we ultimately generate equivalence classes from a particular relation that exhibits the 3 properties of equivalence.

To help illustrate my confusion, consider the following example:

$S=\{1,2,3,4,5,6\}$

Let $R_1$ be a relation on $S$ such that $x-y$ is divisible by $3$

So, firstly, from what I understand about relations, I am going to find all of the order pairs that satisfy this (these ordered pairs are a subset of the cartesian product $S$ x $S$).

$R_1 = \{(1,4) (2,5) (3,6) (4,1) (5, 2) (6, 3)(1,1)(2,2)(3,3)(4,4)(5,5)(6,6)\}$

Ok cool. These are all of the ordered pairs that "satisfy" or "make the $R_1$ relation true".

For this given relation, I can observe the following:

1 - The reflexive property is satisfied because of the presence of $(1,1), (2,2),\ etc$

1st question: If, for example (6,6) was not in this set, $R_1$ could not be deemed reflexive because $(3,6)$ and $(6,3)$ are present, correct? (i.e. because the element "6" shows up as as an ordered pair, $(6,6)$ MUST show up as well in order to declare this relation reflexive)

2 - The symmetric property is satisfied because of the presence of $(1,4) \& (4,1)$, $(2,5)\&(5,2),\ etc$

3 - The transitive property is satisfied because...

2nd question: I actually do not immediately see why the transitive property is satisfied (I believe that the transitive property should be satisfied because the "congruence modulo n" relation is an equivalence relation...and I'm fairly certain that the relation $R_1$ that I described is of that form). Is it just because my set is too small to see the transitive property in its stereotypical form?

So, assuming that this relation IS an equivalence relation (I believe that it is...for the reason mentioned above), I really do not understand how we go from this single set of ordered pairs to equivalence classes. From example videos I have seen, I know that a set of integers mod 3 will create three equivalence classes...namely, the integers with remainder 0, 1, and 2 when divided by 3.

3rd question: However, I do not really understand, mechanistically, how we "separate" these ordered pairs. All of the ordered pairs are initially grouped together. How do we decide, from this initial $R_1$ set, which ordered pairs belong to which equivalence class? Obviously, if you know how mod 3 works, you could sort of intuit that 1 and 4 go together because

$1 mod (3) = 4 mod (3)$

...however, if I knew nothing about how $mod (3)$ worked, how would I know how to make the appropriate partitions?

|cite|improve this question
$\endgroup$
1
$\begingroup$
  1. If $(6,6)\notin R_1$, then $R_1$ would not be reflexive simply because $R_1$ being reflexive means that $(\forall n\in\{1,2,3,4,5,6\}):(n,n)\in R_1$.
  2. It is transitive because if $3\mid x-y$ and $3\mid y-z$, then $3\mid(x-y)+(y-z)$. But this means that $3\mid x-z$. So, this proves that$$x\mathrel{R_1}y\text{ and }y\mathrel{R_1}z\implies x\mathrel{R_1}z.$$
  3. Consider the number $1$. For which numbers $n\in\{1,2,3,4,5,6\})$ do we have $1\mathrel{R_1}n$? It is easy to see that this occurs if and only if $n=1$ or $n=4$. So, the equivalence class of $1$ is $\{1,4\}$. Now take some element of $\{1,2,3,4,5,6\}\setminus\{1,4\}$. Suppose that you have taken $5$. For which numbers $n\in\{1,2,3,4,5,6\})$ do we have $5\mathrel{R_1}n$? It is easy to see that this occurs if and only if $n=2$ or $n=5$. So, the equivalence class of $5$ is $\{2,5\}$. And now you start all over again, taking some element from $\{1,2,3,4,5,6\}\setminus\bigl(\{1,4\}\cup\{2,5\}\bigr)$…
|cite|improve this answer
$\endgroup$
  • $\begingroup$ When you said $n=1$ and $n=2$, did you mean $n\equiv1$ and $n\equiv2\pmod3$? $\endgroup$ – J. W. Tanner Jul 21 at 16:40
  • $\begingroup$ No. I wrote what I meant to write. $\endgroup$ – José Carlos Santos Jul 21 at 16:43
  • $\begingroup$ $1\, R_1 \,n$ occurs iff $n=1$ or $4$ $\endgroup$ – J. W. Tanner Jul 21 at 16:45
  • 1
    $\begingroup$ @J.W.Tanner You are right… as always. I've edited my answer. Thank you. $\endgroup$ – José Carlos Santos Jul 21 at 16:47
  • $\begingroup$ Ohhh, thank you for the excellent answer...that makes the "purpose" of defining equivalence with the properties of reflexivity, symmetry, and transitivity sort of intuitive. $\endgroup$ – S.Cramer Jul 21 at 18:58
1
$\begingroup$

1. No. Without $(6,6)$ the relation would not be reflexive because $6\in S$. If you want to argue with $(6,3),(3,6)\in R$, you would show that $R$ is not transitive if $(6,6)$ is missing.

2. No, I'd rather say that the set is too big to see at once that all instances of transitivity are fulfilled. In principle (i.e., arguing only with the concrete elements of $R$, not algebraically), you'd have to check every pair of pairs in $R$, and if they are of the form $(a,b)$, $(b,c)$ verify that $(a,c)\in R$. That's a lot to check if the relation is uncomfortably big.

3. The equivalence classes do not consist of pairs $\in R$, but of elements $\in S$. We can build the classes successivley: What is the eequivalence class of $1\in S$? From $(1,4)\in S$, we see that $4$ is also in the equivalence class of $1$. As we do not find any additional relations involving $1$ and/or $4$ (apart from the corresponding reflexive and symmetric pairs) we conclude that the equivalence class of $1$ (as well as of $4$) is $\{1,4\}$. Similarly, we find the other equivalence classes $\{2,5\}$ and $\{3,6\}$. To emphasize that the classes are not pairs: Had $S$ been bigger, the equivalence class of $1$ might have been $\{1,4,7\}$.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

If you'd extend your set just a bit you'd see transitivity happen. Consider the set $\{1,2,3,4,5,6,7 \}$ for example. Now your $R_1$ contains $(1,4), (4,7)$ and $(1,7)$.

Once you know you have an equivalence relation you can just choose one representative, for example $1$, to represent the pairs $(1,4), (1,7)$ and also $(4,7)$ by transitivity.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.