Is $\rho$ equivalence relation and, if not, specify all the ways to expand it to the equivalence relation.

Question

On the set $\Bbb Z \times\Bbb Z$, the relation $\rho$ is given as it follows:

$(a,b) \rho (c,d) \iff (2 | (a-c) $ or $ 3|(b-d))$

Is $\rho$ equivalence relation and, if not, specify all the ways to expand it to the equivalence relation.

First, I checked if it's equivalence relation.

1. reflexivity

$(\forall a,b \in \mathbb Z )(a,b) \rho(a,b)$

This is true because $(2|(a-a)$ or $3|(b-b)) \iff(2|0$ or $3|0)$ is true.

2. symmetry

$(\forall a,b,c,d \in \mathbb Z )(a,b) \rho(c,d) \Rightarrow (c,d)\rho(a,b)$

Also true, $(a,b) \rho(c,d) \Rightarrow (2|(a-c)$ or $3|(b-d))\Rightarrow (2|(c-a)$ or $3|(d-b)) \Rightarrow (c,d)\rho(a,b)$.

3. transitivity

$(\forall a,b,c,d,e,f \in \mathbb Z )((a,b) \rho(c,d)$ and $(c,d) \rho(e,f)) \Rightarrow (a,b)\rho(e,f)$

Not true, for example while$(5,4) \rho (3,2)$ and $(3,2)\rho(2,-1)$ is true, $(5,4)\rho(2,-1)$ isn't.

Ok so now I have to expand this relation so that it can also be transitive. How do I do that?

Answer 1

The reason why transitivity would not hold can be put this way : given $(a,b) \rho (c,d)$ and $(c,d) \rho (e,f)$, since the equivalence condition requires a relationship between any one of the two coordinates (either $2 \mid a-c$ or $3 \mid b-d$), it's possible that the first relation is via the first coordinate, while the second relation is via the second coordinate. Therefore, when you take the elements $(a,b)$ and $(c,d)$, they are unrelated, since neither their first nor second coordinates are in control.

So how would we "expand" this equivalence relation. Clearly, this means we have to make it bigger, not smalller. However, if you were to make it smaller, you could replace "or" with "and" in the statement for equivalence, and you would actually get an equivalence relation, albeit a smaller one.

Since your relation is already symmetric and reflexive, there remains only one way to expand your relation, and that is by transitively closing it. This closure is unique, so there is exactly one expansion of the given relation. This I detail below.

To expand this relation, fix $(a,b) \in \mathbb Z^2$. We will find a relation, that expands our current relation $R$, but which will be transitive, aand therefore an equivalence relation. To do this, we basically repeat $R$ on $(a,b)$. In other words :

• Find all elements related to $(a,b)$ via $R$. Call this set $S$.

• Find all elements related to some element of $S$, via $R$. Call this set $T$.

• Find all elements related to some element of $T$, via $R$...

• Keep going until you feel that not too many elements are being added to $S$, $T$.

• Now, take a guess as to what the final relation could be, and see if you can prove it.

Here, let us say we start with $(0,0)$. I'll find all elements related to $(0,0)$.

Apparently, these are are of the form $(2k,l)$ and $(m,3j)$, for some $k,j,l,m \in \mathbb Z$. This is because, $(0,0) R (2k,l)$ as the difference between the first coordinates is a multiple of $2$. Similarly, $(0,0) R (m,3j)$ since the difference between the third coordinates is a multiple of $3$.

So, we would write $S = \{(2k,l)\} \cup \{(m,3j)\}$, where $k,l,j,m \in \mathbb Z$.

Now, which elements are related to some element of $S$?

• Anything related to $(2k,l)$ must either be of the form $(2n,p)$(first coordinates differ by multiple of $2$) or $(r,l+3q)$ (second coordinates differ by $3$) for some $n,r,p,q \in \mathbb Z$.

• Anything related to $(m,3j)$ must be of the form $(m + 2s,o)$(first coordinates differ by multiple of $2$) or $(v, 3u)$(third coordinates differ by multiple of $3$) for some $o,u,v,s \in \mathbb Z$.

Finally, we can write $T = \{(2n,p)\} \cup \{(r,l+3q)\} \cup \{(m+2s,o)\} \cup \{(v,3u)\}$ for all of the variables being integers.

I claim that $T = \mathbb Z \times \mathbb Z$.

Indeed, this is obvious : given $(a,b) \in \mathbb Z$, write $r = a$ and $b = l + 3q$ by letting $q$ be the quotient and $l$ the remainder when $b$ is divided by $3$.

For example, if $(a,b) = (3,1)$, then I would proceed this way: $(0,0) R (0,1)R (3,1)$ (in the first case, the first coordinates differ by a multiple of $2$, and in the second case, the second coordinates differ by a multiple of $3$).

Therefore, the transitive closure of $R$ is actually the relation where every element is related to one another.

This answer was elaborate for a reason : it shows you the main technique, in a general situation, of finding the transitive closure of any given relation.

Answer 2

I'm not sure what the question means by "all the ways" to make it an equivalence relation, however there is in general a way to make a symmetric, reflexive but not transitive $\rho$ into an equivalence relation.

Regardless of what $\rho$ is, we can define a new equivalence relation $\tilde{\rho}$ such that $x\tilde{\rho} y$ if and only if $x\rho y$ or there exists $z$ such that $x\rho z$ and $y\rho z$.

Note that symmetry and reflexivity of $\tilde{\rho}$ follow from symmetry and reflexivity of $\rho$.

In your case I would recommend writing explicitly what this $\tilde{\rho}$ is.

Answer 3

Hint: for any $a, b, c, d \in \mathbb{Z}$, we have $(a, b) \mathrel{\rho} (c, b)$ and $(c, b) \mathrel{\rho} (c, d)$.