Explicitly describing the equivalence relation generated by $R$

Question

Here is an explicit construction of the equivalence relation generated by a relation $R$ (found in Leinster's book):

First of all, I don't understand the highlighted part. Where does this zigzag come from? Why is having such a zigzag equivalent to $a\sim a'$?

Second, why is the $\sim$ defined at the end indeed the equivalence relation generated by $R$? What would a rigorous proof of this fact be? I'm not even sure I understand what lies behind this definition. For example the statement $(a_0,a_1)\in S$ says that either $a\sim_R a_1$ or $a_1\sim_R a$ for some $a_1\in A$, and I don't see how this is relevant to the equivalence relation generated by $R$.

Answer 1

The book writes $x\to y$ for $(x,y)\in R$. It also uses $x\gets y$ for $(y,x)\in R$.

Since we're assuming that $\sim$ is an equivalence relation containing $R$, necessarily $x\to y$ and $x\gets y$ imply $x\sim y$, because $\sim$ is by assumption symmetric.

We're also assuming that $\sim$ is transitive. The “zigzag” in the example means

suppose we have $a\to b$, $b\gets c$, $c\gets d$, $d\to e$, $e\gets a'$; then we must have $a\sim b$, $b\sim c$, $c\sim d$, $d\sim e$ and $e\sim a'$; since $\sim$ is transitive, we conclude that $a\sim a'$.

Thus every pair of elements “linked by a zigzag” must belong to $\sim$.

Now consider the set $\tilde{R}$ of pairs $(a,a')$ such that either $a=a'$ or there exist $a_0=a,a_1,\dots,a_{n-1},a_n=a'\in A$ with either $a_{k-1}\to a_k$ or $a_{k-1}\gets a_k$, for $k=1,2,\dots,n$ (with $n\ge1$). Note that “either $a_{k-1}\to a_k$ or $a_{k-1}\gets a_k$” is the same as “$(a_{k-1},a_k)\in S$”, in the book's notation.

Then prove that $\tilde{R}$ is an equivalence relation.

Since clearly $\tilde{R}$ contains $R$, it is the equivalence relation generated by $R$, because it just contains what it must contain, that is, the pairs of elements linked by a zigzag.

Note: here I use $n\ge1$ by clarity; the text uses also $n=0$, which accounts for the pairs $(a,a)$, but it's a bit of a stretch for beginners.

Answer 2

The idea is to add all the pair to $R$ that you have to in order to make it an equivalence relation. Say $R$ has $(1,2),(1,3)$. The first stage is to make it symmetric by adding the reverse of all the pairs you have, so $(2,1),(3,1)$. Now add all the pairs needed to make it transitive. As we have $(2,1)$ and $(1,3)$ we need $(2,3)$. Similarly, we need $(3,2)$ and $(1,1)$. The zigzag is just a chain of pairs that forces us to add another pair to make the relation transitive.

Answer 3

Recall that an equivalence relation $\sim$ on a set $A$ is essentially the same as a partition of $A$. In order to turn $R$ into an equivalence relation, we might just define a partition of $A$ such that if $a \to a'$, then $a$ and $a'$ belong to the same subset in the partition, which will be the equivalence class $[a]$ of $a$.

So, let $a \in A$. Which elements of $A$ should belong to $[a]$? Well, clearly $a \in [a]$. Then, if $a_1 \in A$ is such that $a \to a_1$ or $a \leftarrow a_1$, we also want that $a_1 \in [a]$, because the two elements are related. But then all the elements that are related to $a_1$ must belong to $[a]$ as well. And then the elements related to those elements, and so on.

In general, an element $a'$ will belong the same class as $a$ if we can construct a sequence such as the one given in the book: we start from $a$ and at each step we choose an element that is related to the previous one (i.e., there is an arrow between them).