# 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.

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.

-
No, $E$ is not in general the only equivalence relation containing $C$; it’s the intersection of all equivalence relations containing $C$. As long as $E\ne S\times S$, $S\times S$ is a strictly larger equivalence relation containing $C$. –  Brian M. Scott Nov 6 '12 at 22:08
@BrianM.Scott, would you care to give a full answer explaining all of this? I do not particularly see how $S\times S$ is an equivalence relation containing $C$, and I don't see how $S\times S$ can contain $C$ since $S\times S$ would be 4-tuples and $C$ is a binary relation. Are you saying that, in this case, $C$ relates 4-tuples rather than 1-tuples (as in $(a,b,c,d)C(e,f,g,h)$ versus $sCt$)? Sorry if I've misunderstood you completely. –  000 Nov 6 '12 at 22:14
I’m in the process of writing up an answer. For the immediate issue, however, $S\times S$ is not a set of $4$-tuples: it’s a set of ordered pairs. It is the trivial relation on $S$ by which every $s\in S$ is related to every $s\in S$: $S$ is just one big equivalence class. –  Brian M. Scott Nov 6 '12 at 22:21
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! :P –  000 Nov 6 '12 at 22:23

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$.

-
This is great, but there's just a few typographical errors: You put a . whether a , should go in bullet 1 and you typed $y$ instead of $t$ in bullet 2. Though this is a really great answer, I have just a few questions: Why did you use $\langle$ and $\rangle$? Was it a matter of convenience and clarity or is there a particular notational thing going on here? Also, what do you specifically mean by, ". . . transitivity, strictly speaking, gives the result only when $n=2$."? Thanks for the great help! –  000 Nov 6 '12 at 22:55
@Limitless: Sorry about the typos; my arthritis is acting up a little. Like many people with a set-theoretic background, I use angle brackets for ordered pairs and $n$-tuples. It’s just a notational preference; you can replace them with plain parentheses if you prefer. Transitivity just says that if $s_0\sim s_1$ and $s_1\sim s_2$, then $s_0\sim s_2$; if you want to go from $s_0\sim s_1\land s_1\sim s_2\land s_2\sim s_3$ to $s_0\sim s_3$, you have to use transitivity twice. Thus, it’s really a theorem that if $s_0\sim s_1\sim\ldots\sim s_n$, then $s_0\sim s_n$, proved by induction on $n$. –  Brian M. Scott Nov 6 '12 at 23:02
Ah, I see what you mean now. Thanks for everything! –  000 Nov 6 '12 at 23:12
@Limitless: You’re welcome! –  Brian M. Scott Nov 6 '12 at 23:13