Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.


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.

share|improve this question
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
add comment

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.