Example of a minimal equivalence relation on $A$ containing $R$

Question

Let $A$ be a non-empty set, and let $R$ be a relation on $A$. Define the minimal equivalence relation on $A$ containing $R$ to be the intersection of all equivalence relations on $A$ that contain $R$.

I understood this definition, but I’m not quite sure of how it works. Can someone provide some examples of a set $A$, a relation $R$ on $A$ and the minimal equivalence relation on $A$ containing $R$? So I can get to know how this works. Any example is welcome.

Thank you in advance!

Answer 1

Example 1: $A=\Bbb Z$, and $R=\{(m,m+1)\colon m\in \Bbb Z\}$, or in other words $mRn$ if and only if $n=m+1$. Then the minimal equivalence relation on $A$ containining $R$ is the universal equivalence relation $\{(m,n)\colon m,n\in\Bbb Z\}$, where every integer is related to every other integer.

Example 2: $A=\Bbb Z$, and $R=\{(m,m+2)\colon m\in \Bbb Z\}$, or in other words $mRn$ if and only if $n=m+2$. Then the minimal equivalence relation on $A$ containining $R$ is the equivalence relation where $m$ is related to $n$ if and only if $m$ and $n$ have the same parity.

Example 3: $A$ is any set and $R$ is any equivalence relation. Then the minimal equivalence relation containing $R$ is $R$ itself.

Example 4: $A$ is any set, and $R=\emptyset$ is the empty relation, where nothing is related to anything else. Then the minimal equivalence relation contining $R$ is the equality relation $\{(x,x)\colon x\in A\}$, where $x$ is related to $y$ if and only if $x=y$.

Answer 2

A common example is this: you have $B\subseteq A$ and you want all the elements of $B$ to be equivalent, but all the others to be equivalent only to themselves. This is achieved through the least equivalence $R_B$ such that $a R_B b$ for all $a,b\in B$. Id est:

$$x R_B y\Leftrightarrow ((x\in B\land y\in B)\lor (x=y))$$

You should check that the predicate on the RHS actually defines an equivalence, and convince yourself that it is the least equivalence containing $B\times B$.

Answer 3

Well, if all you want is an example...

Let $A = \mathbb Z$ and let $R = \{(3,7), (2,7)\}$. That is a relation on $\mathbb Z$ although it's a very boring and rather pointless. $3 R 7$ and $2 R 7$ but nothing else is related to anything.

This is obviously not an equivalence relation. It's not reflexive. There is no $a Ra$. It's not symmetric. $(3,7) \in R$ but $(7,3)\ne R$. Counterintuively it is transitive as there are no pair of $(a,b)$ AND $(b,c) \in R$.

Now to make it an equivalence relation we must add some $(a,b)$. But which ones and how few can we get away with.

To make it reflexive we must add every $(a,a)$ where $a \in \mathbb Z$.

To make it symmetric, because it has $(3,7)$ and $(2,7)$ we must add $(7,3)$ and $(7,2)$.

Now we have $(3,7),(7,3),(2,7),(7,2)$ and to make it transitive as we have $(3,7),(7,2)$ (and $(7,3),(3,2)$) we need $(3,2)$ and $(2,3)$.

So now we have $S = \{(a,a)|a\in Z\}\cup {(2,3),(2,7),(3,2),(3,7),(7,2),(7,3)\}$.

That is

1. $S$ is an equivalence relationship on $\mathbb Z$>
2. $R = \{(3,7),(2,7)\} \subset S$
3. $S$ is the smallest equivalence on $\mathbb Z$ that contains $R$.