Why is this an equivalence relation, and what does the equivalence classes contain?

Question

I'm doing some discrete mathematics exercises, but I can't seem to wrap my head around this relation:

$$R(x, y) \text{ if } \exists z(\text{LiesInPart}\circ\text{LiesInCountry}(x,z) \wedge \text{LiesInPart}\circ\text{LiesInCountry}(y,z))$$

These are the sets and relations used in the relation:

$\begin{align*} \text{Countries} & = \text{Set of all countries in the world}\\ \text{Cities} & = \text{Set of all cities in the world}\\ \text{Parts of the world} & = \{\text{Africa}, \text{Americas}, \text{Asia}, \text{Australia}, \text{Europe}\} \\ \text{LiesInCountry} & \subset \text{Cities} \times \text{Countries} \\ \text{LiesInCountry}(x,y) & :\Leftrightarrow \text{City } x \text{ lies in Country } y \\ \text{LiesInPart} & \subset \text{Countries} \times \text{Parts} \\ \text{LiesInPart}(x,y) & :\Leftrightarrow \text{Country } x \text{ lies in part of the world } y \end{align*}$

My main problem is really trying to understand what the relation I first posted means. I'm quite new to discrete mathematics. If anyone can make me understand the relation, or explain why this is an equivalence relation and what the equivalence classes contain, I would be very grateful.

Answer 1

To keep the notation simple, let

$$S=\text{LiesInPart}\circ\text{LiesInCountry}\;,$$

so that $R(x,y)$ if and only if $\exists z\big(S(x,z)\text{ and }S(y,z)\big)$. Let’s see what $S$ actually means first.

$S(x,z)$ is true if and only if there is a $u$ such that

$$\operatorname{LiesInCountry}(x,u)\text{ and }\operatorname{LiesInPart}(u,z)\;,$$

meaning that there is some country $u$ such that the city $x$ is in $u$, and the country $u$ is in the part $z$. In other words, if $x$ is a city and $z$ is a part of the world, $S(x,z)$ just says that $x$ is in some country that is in the part $z$. Assuming every city is in some country, this basically just says that $x$ is in the part of the world $z$.

Now we’ll get back to $R$: A city $x$ is $R$-related to a city $y$ if and only if there is some part of the world $z$ such that $x$ and $y$ are both in $z$. Once you realize this, checking reflexivity, symmetry, and transitivity should be very easy, and it should be just about as easy to identify the equivalence classes.

Answer 2

The relation $R$ can be worded as "City $x$ is in the same part of the world as city $y$".

If we define a more compact notation as $A = \text{Cities}, B = \text{Countries}, C = \text{Parts}$ and name the relations $\in_B = \text{LiesInCountry}$ and $\in_C = \text{LiesInPart}$, we get $$R \subset A\times A \\ xRy \Leftrightarrow \exists z\in C \exists m,n\in B (x \in_B m \in_C z \wedge y\in_B n\in_C z)$$ The $m,n$ part of this notation comes from the composition: $$\in_C \circ \in_B (x,y) :\Leftrightarrow \exists m\in B : x\in_B m \in_C y$$ In words: "City $x$ is in part of the world $y$ iff there exists a country $m$ such that $x$ is in the country $m$ and $m$ is in the part $y$".