0
$\begingroup$

Problem

The following is a problem from Jacobson's Basic Algebra I:

Let $C$ be a binary relation on $S$. For $r=1,2,3,\dots$ define $C^r=\{(s,t)|\text{ for some } s_1,\dots, s_{r-1}\in S,\text{ one has } sCs, s_1Cs_2,\dots, s_{r-1}Ct\}$. Let $E=1_{S}\cup(C\cup C^{-1})\cup(C\cup C^{-1})^2\cup(C\cup C^{-1})^3\cup\cdots.$ Show that $E$ is an equivalence relation, and that every equivalence relation on $S$ containing $C$ contains $E$. ($E$ is called the equivalence relation generated by $C$.)

My Question

I am having issues with showing that every equivalence relation on $S$ containing $C$ contains $E$. I am also uncertain about my work on the first part.

Partial Answer

An equivalence relation must be reflexive, symmetric, and transitive.

The first set of elements, $1_{S}$, ensures the property of reflexivity via the definition of $1_{S}$: $1_{S}=\{(s,s): s \in S\wedge sCs\}$. Since $E$ is a union of $1_{S}$ and the other sets, all elements in $E$ must satisfy the property that they are in $S$ and related to themselves via $C$.

The second set of elements, $(C\cup C^{-1})$, ensures the property of symmetry. This is because $ \begin{align} (C\cup C^{-1})&=\{(s,t):s,t\in S\wedge sCt\}\cup\{(t,s):t,s\in S\wedge tCs\}\\ &=\{(s,t):s,t \in S\wedge sCt\wedge tCs\}. \end{align} $ In other words, $E$ contains all $(s,t)$ such that $sCt$ and $tCs$.

The rest of the sets of elements, $\bigcup_{i \ge 2}(C\cup C^{-1})^i$, ensures transitivity. I felt this part was difficult because it relies on realizing that the three-part statement of the law of transitivity is an intentional simplification. That is, the statement $aCb \wedge bCc \Rightarrow aCc$ is equivalent to the more long and indefinite statement $aCb_1\wedge b_1Cb_2\wedge b_3Cb_4\wedge \dots \wedge b_nCc \Rightarrow aCc$.

In our case, we have that $\bigcup_{i \ge 2}(C\cup C^{-1})^i$ is the inclusion of all elements such that $sCs_1\wedge s_1Ct$, $sCs_1\wedge s_1Cs_2\wedge s_2Ct$, . . . and so forth. (With, of course, $s,s_1,\dots$ and $t$ in $S$.) This inclusion allows $E$ to be transitive since any given indefinite statement (such as shown above) is true regardless of length.

What I don't understand is how to show that every equivalence relation on $S$ containing $C$ contains $E$. Is this a trick question in the sense that $E$ is the only such equivalence relation on $S$ containing $C$? My understanding of equivalence relations in general is not strong enough to fully envision this question's vast generality.

Thank you for your time.

  • 0
    Oh! Right. I mistakenly thought $((s,t),(x,y))=(s,t,x,y)$. I wasn't thinking properly; thank you for correcting me. As for how $S\times S$ now contains an equivalence relation, that makes perfect sense. Thank you. I await your answer with hope! :P2012-11-06

1 Answers 1

2

This $E$ is in general not the only equivalence relation containing $C$. Consider the relation $C=\{\langle 1,1\rangle\}$ on the set $S=\{1,2\}$. Then $E$ turns out to be the identity (equality) relation, $\{\langle 1,1\rangle,\langle 2,2\rangle\}$, but $S\times S=\{\langle 1,1\rangle,\langle 1,2\rangle,\langle 2,1\rangle,\langle 2,2\rangle\}$ is also an equivalence relation containing $C$. In fact, no matter what relation $C$ is, $S\times S$ is an equivalence relation containing $C$.


The basic idea is that $E$ is formed from $C$ by adding to $C$ only those ordered pairs that are absolutely required in order to expand $C$ to an equivalence relation. We throw in $C^{-1}$ to make the relation symmetric. We then throw in the powers of $C\cup C^{-1}$ as the minimal addition that will make it transitive. And finally we throw in $1_S$ to make the relation reflexive. It’s a definition from the inside out, so to speak: what do I have to add to $C$ to make it an equivalence relation. This same $E$ can also be defined from the outside in, as the intersection of all equivalence relations on $S$ that contain $C$; what you’re doing in this problem is the hard part of proving that these two definitions are equivalent, i.e., that they define the same $E$. And here’s the argument that you need.

Suppose that $C\subseteq R$, where $R$ is an equivalence relation on $S$; we want to show that $E\subseteq R$, so let $\langle s,t\rangle\in E$. There are a couple of cases.

  • $\langle s,t\rangle\in 1_S$: $R$ is reflexive, so $1_S\subseteq R$, and therefore $\langle s,t\rangle\in R$.

  • $\langle s,t\rangle\in\left(C\cup C^{-1}\right)^n$ for some $n\ge 1$: Then there are $s_0,s_1,\dots,s_{n-1},s_n\in S$ such that $s=s_0$, $t=s_n$, and $\langle s_i,s_{i+1}\rangle\in C\cup C^{-1}$ for $i=0,\dots,n-1$. $R$ is symmetric, and $C\subseteq R$, so $C^{-1}\subseteq R$ as well. Thus, $\langle s_i,s_{i+1}\rangle\in R$ for $i=0,\dots,n-1$. Finally, $R$ is transitive, so $\langle s,t\rangle=\langle s_0,s_n\rangle\in R$. (Note: This conclusion really requires a proof by induction on $n$, since transitivity, strictly speaking, gives the result only when $n=2$.)

In both cases we find that $\langle s,t\rangle\in R$, so $E\subseteq R$.

  • 0
    @Limitless: You’re welcome!2012-11-06