Preparatory Matters

A (binary) relation on a set \(X\) is an equivalence relation iff it is reflexive on \(X\), symmetric, and transitive. In this article, we explore the interactions of these properties and their roles in building an equivalence relation. While there are already many online references about these properties, none of them has quite what I was interested in finding (namely, the Cayley table for the semigroup generated by the closure operators)...so here I am writing it up for myself.

(An aside: In the spirit of my Getting It Right collection, I note that equivalence relations Get It Right. They are based on partitions and the three axioms are exactly what's needed to define the equivalence classes that replicate a given partition.)

An easy result is:

Proposition. Any intersection (as a set of ordered pairs) of reflexive relations on \(X\) is reflexive on \(X\). Similarly for symmetric and transitive relations and hence also for equivalence relations. Any union of reflexive (resp. symmetric) relations on \(X\) is reflexive on \(X\) (resp. symmetric). Any nested union of transitive (resp. equivalence) relations is transitive (resp. an equivalence relation).

Thus, given any (binary) relation on a set \(X\), we may define its closure under each of these four properties as the intersection of all extending relations with the property:

Definition. Let \(Q\) be a binary relation on a set \(X\). The reflexive closure \(R(Q)\) of \(Q\) in \(X\) = the intersection of all reflexive binary relations on A that extend \(Q\) = \(\bigcap\left\{P: Q\subseteq P\subseteq X\times X\ \&\ P\mbox{ is reflexive}\right\}\). Similarly for the symmetric closure \(S(Q)\), transitive closure \(T(Q)\), and equivalence closure \(E(Q)\) of \(Q\) in \(X\).

In other words, \(R(Q)\) is a reflexive relation on \(X\) that refines \(Q\) and all other reflexive relations on \(X\) refining \(Q\) refine \(R(Q)\); equivalently, \(R(Q)\) is the initial object in the category of reflexive relations on \(X\) refining \(Q\). Similarly for \(S(Q)\) and \(T(Q)\).

Proposition. (Monotonicity) If \(Q\subseteq Q'\) then \(R(Q)\subseteq R(Q')\). Similarly for \(S(Q)\) and \(T(Q)\).

What are the relationships among these closures? If we apply them in succession, does the order matter? We will see that the order sometimes matters. Our main result will be that \(E=TSR\). Ideally, we will find the semigroup the four closures generate.

Constructing the Closures

It will help to have each closure characterized in a bottom-up, constructive manner as well as the top-down form of the definition. The reflexive closure is easy:

Proposition. (Construction of \(R\)) Let \(Q\) be binary relation on a set \(X\). Then \(R(Q)=Q\cup \{\langle a,a\rangle:a\in X\}\), i.e., to form \(R(Q)\), we simply augment it by \(A\)'s diagonal.

Proof: Let \(Q\) be binary relation on a set \(X\).

- \(Q\cup \{\langle a,a\rangle:\ a\in X\}\) is manifestly reflexive on \(X\).
- All reflexive relations on \(X\) extending \(Q\) must include \(X\)'s diagonal as well as \(Q\).

Clearly, \(Q\cup \{\langle a,a\rangle:a\in X\}\) is the smallest such set, hence it equals \(R(Q)\), as promised.

Symmetric closure next: Let \(Q^<\) denote the converse of \(Q\).

Proposition. (Construction of \(S\)) \(S(Q)=Q\cup Q^<\).

Proof: Similar to the reflexive case.

- \(Q\cup Q^<\) is manifestly symmetric.
- All symmetric relations extending \(Q\) must include both \(Q\) and \(Q^<\).

\(Q\cup Q^<\) is clearly the smallest such set, hence it equals \(S(Q)\), as promised.

The transitive closure is more delicate. We must build up the transitive closure in stages using the notion of the composite of binary relations, Actually, we need only the composite of a relation with itself:

Definition. Let \(P\) be a binary relation on a set \(X\). Define the composite \(P\circ P\) of \(P\) with itself by \(P\circ P=\{\langle a,b\rangle\in X\times X:\ (\exists\hspace{-4pt}\exists c\in X)\ \langle a,c\rangle, \langle c,b\rangle\in P\}\). Define the composite successor \(cs(P)=P\cup (P\circ P)\).

Remark. If P is reflexive on \(X\), then \(cs(P)=P\circ P\). Simplifies things if applicable.

We now define the stages that build the transitive closure serially:

Definition. Let \(Q\) be a binary relation on \(X\). For any whole number \(n\), define \(T_n\) by \(T_0(Q)=Q\) and \(T_{n+1}(Q)=cs(T_n(Q))\). (In some sense, \(T_n=cs^n\)). Temporarily let \(T_\omega(Q)=\bigcup\{T_n(Q):n\in{\Bbb N}\}\).

Proposition. (Construction of \(T\)) Let \(Q\) be a binary relation on \(X\). Then \(T_\omega(Q)=T(Q)\), the transitive closure of \(Q\).

Proof: (mostly baby set theory definition-chasing) Let \(Q\) be a binary relation on \(X\). We will show the double-inclusion.

- \((T_\omega(Q)\subseteq T(Q))\) We will show by induction that each \(T_n(Q)\) is a subset of \(T(Q)\).
  - Base Case, \(n=0\): \(T_n(Q)=T_0(Q)=Q\), which is certainly a subset of \(T(Q)\).
  - Inductive Case: Suppose \(T_n(Q)\subseteq T(Q)\) for some \(n\). We must show that \(T_{n+1}(Q)\subseteq T(Q)\). Recall that \(T_{n+1}(Q)=cs(T_n(Q))=T_n(Q)\cup (T_n(Q)\circ T_n(Q))\). We show that each component is a subset of \(T(Q)\).
    - By inductive hypothesis, \(T_n(Q)\subseteq T(Q)\).
    - Now for the composite part. Suppose \(\langle a,b\rangle\in T_n(Q)\circ T_n(Q)\). By definition, there is some \(c\in X\) for which \(\langle a,c\rangle,\ \langle c,b\rangle \in T_n(Q)\). By inductive hypothesis, both of these pairs are in \(T(Q)\), which is transitive. Thus, \(\langle a,b\rangle\in T(Q)\). This establishes that \(T_n(Q)\circ T_n(Q)\subseteq T(Q)\).
    - It follows that \(T_{n+1}(Q)\subseteq T(Q)\). That completes the inductive case.
  - By induction, we have \(T_n(Q)\) is a subset of \(T(Q)\) for all whole numbers \(n\), whence \(T_\omega(Q)\subseteq T(Q)\).
- \((T(Q)\subseteq T_\omega(Q))\) We will show that \(T_\omega(Q)\) is a transitive binary relation extending \(Q\) and hence must include \(T(Q)\).
  - Well, \(T_\omega(Q)\) is clearly a binary relation extending \(Q\). We must show it is transitive. (Make this a lemma?)
  - Suppose \(\langle a,c\rangle, \langle c,b\rangle\in T_\omega(Q)\). Then \(\langle a,c\rangle, \langle c,b\rangle\in T_n(Q)\) for some \(n\) (and hence for all larger indices, not that we need it). By construction, \(\langle a,b\rangle\in T_{n+1}(Q)\subseteq T_\omega(Q)\). This establishes that \(T_\omega(Q)\) is transitive.
  - (As an aside: Because \(T_\omega(Q)\) is transitive, the tower stabilizes, so there is no point in forming \(T_{\omega+1}(Q)\), etc.)
  - We have shown that \(T_\omega(Q)\) is a transitive binary relation extending \(Q\). Thus, it must include \(T(Q)\) (because \(T(Q)\) is the smallest such).

We have shown the double-inclusion. Thus \(T_\omega(Q)=T(Q)\), as promised.

Remark. Note that \(\langle a,b\rangle\in T(Q)\) iff there is a "path" \(\langle a,x_1\rangle,\langle x_1,x_2\rangle,\dots,\langle x_n,b\rangle\in Q\) from \(a\) to \(b\).

We now have "bottom-up" constructions for the three closures. As we will see, applying them in succession in the order R, then S, then T, will yield the equivalence closure E. We will use these constructions to find the operators' "multiplication table".

Interrelationships among the R, S, T, and E Operators

More definition-chasing:

Not Even a Proposition. Each operator is idemsquare: \(RR=R\), \(SS=S\), \(TT=T\), and \(EE=E\). Applying \(E\) on the left or right always yields \(E\) Thus, \(ER=RE=E\), etc.

Proposition and Notation. The reflexive closure of a symmetric relation is symmetric. The symmetric closure of a reflexive relation is reflexive. Thus, the reflexive and symmetric closure operators commute with one another: \(RS=SR=\) any other serial composite of \(R\)s and \(S\)s. We could call this the reflexymmetric closure. We will denote it by \(A\).

Proposition and Notation. The reflexive closure of a transitive relation is transitive. The transitive closure of a reflexive relation is reflexive. Thus, the reflexive and transitive closure operators commute with one another: \(RT=TR=\) any other serial composite of \(R\)s and \(T\)s. We could call this the reflexitive closure. We will denote it by \(B\).

Remark. ("Redundant R") In any serial composite of \(R\)s, \(S\)s, and \(T\)s, we may collect all the \(R\)s at either end as a single \(R\).

Proposition. The composite successor of a symmetric relation is symmetric. Thus each \(T_n\) of a symmetric relation is symmetric and hence the transitive closure of a symmetric relation is symmetric. Thus, \(STS=TS=\) any other serial composite of \(S\)s and \(T\)s that has \(TS\) at its right end.

Proof: We start with the composite successor's preserving symmetry. Suppose \(Q\) is a symmetric relation and \(\langle a,b\rangle\in cs(Q)\), i.e., \(\langle a,b\rangle\in Q\cup Q\circ Q\), i.e., \(\langle a,b\rangle\in Q\) or \(\langle a,b\rangle\in Q\circ Q\). We show by cases that \(\langle b,a\rangle\in cs(Q)\):

- Case 1: Suppose \(\langle a,b\rangle\in Q\). Because \(Q\) is symmetric, \(\langle b,a\rangle\in Q\). Because \(Q\subseteq cs(Q)\),\(\langle b,a\rangle\in cs(Q)\).
- Case 2: Suppose \(\langle a,b\rangle\in Q\circ Q\). Then there is some \(x\in X\) for which \(\langle a,x\rangle, \langle x,b\rangle\in Q\). Because \(Q\) is symmetric, \(\langle x,a\rangle, \langle b,x\rangle\in Q\). Thus, \(\langle b,a\rangle\in Q\circ Q\), whence \(\langle b,a\rangle\in cs(Q)\).

Disjunctive syllogism on Cases 1 and 2 shows that the composite successor of a symmetric relation is symmetric. A simple induction shows that \(T_n\) of a symmetric relation is symmetric for all whole numbers \(n\). Because unions (of binary relations) preserve symmetry, the transitive closure of a symmetric relation is symmetric and hence \(STS=TS\).

Now suppose \(U_1U_2\ldots U_nU_{n+1}TS\) is any serial composite of \(S\)s and \(T\)s that has \(TS\) at its right end. Either \(U_{n+1}=S\) or \(U_{n+1}=T\). We show by cases that \(U_1U_2\ldots U_nU_{n+1}TS=U_1U_2\ldots U_n TS\):

- Case 1: Suppose \(U_{n+1}=S\) whence the operator is \(U_1U_2\ldots U_n STS\). Because \(STS=TS\), we have \(U_1U_2\ldots U_n STS=U_1U_2\ldots U_n TS\).
- Case 2: Suppose \(U_{n+1}=T\) whence the operator is \(U_1U_2\ldots U_n TTS\). Well, \(TT=T\) (It'd be a pretty poor closure operator if it weren't!), so \(U_1U_2\ldots U_n TTS=U_1U_2\ldots U_n TS\).

Disjunctive syllogism on Cases 1 and 2 shows that \(U_1U_2\ldots U_nU_{n+1}TS=U_1U_2\ldots U_n TS\). An easy induction establishes that any other serial composite of \(S\)s and \(T\)s that has \(TS\) at its right end = \(TS\), as promised.

However...

Proposition. The symmetric closure of a transitive relation is not necessarily transitive.

Proof by counterexample: Let \(Q=\{\langle1,2\rangle,\langle2,3\rangle,\langle1,3\rangle,\langle1,4\rangle\}\). Then \(Q\) is transitive and \(S(Q)=\{\langle1,2\rangle,\langle2,3\rangle,\langle1,3\rangle,\langle1,4\rangle,\langle2,1\rangle,\langle3,2\rangle,\langle3,1\rangle,\langle4,1\rangle\}\). \(S(Q)\) is not transitive: Not only does \(S(Q)\) omit all the diagonal pairs \(\langle1,1\rangle,\ldots,\langle4,4\rangle\) but it also omits \(\langle3,4\rangle\) despite containing \(\langle3,1\rangle\) and \(\langle1,4\rangle\). Even if we took the reflexive closure of \(Q\) before the symmetric closure, \(SR(Q)\) is still not transitive. In any case, the symmetric closure of a transitive relation is not necessarily transitive, as promised.

It follows that \(ST\) and \(TS\) are distinct operators on the set of binary relations on \(X\) (if \(X\) has at least 4 members). This is disappointing. Nonetheless, we can show that \(ST(Q)\subseteq TS(Q)\). It will follow that \(TST=TS\).

Proposition. For any binary relation \(Q\) on \(X\), \(ST(Q)\subseteq TS(Q)\), i.e., \(TS(Q)\) is a refinement of \(ST(Q)\).

Proof: We demonstrate the inclusion. Suppose \(\langle a,b\rangle\in ST(Q)\). Then, by construction of \(S\), either \(\langle a,b\rangle\in T(Q)\) or \(\langle b,a\rangle\in T(Q)\).

- Case 1: Suppose \(\langle a,b\rangle\in T(Q)\). By construction of \(T\), there exist \(x_1,\ldots,x_n\in X\) for which \(\langle a,x_1\rangle,\langle x_1,x_2\rangle,\dots,\langle x_n,b\rangle\in Q\). By construction of \(S\), we have \(\langle x_1,a\rangle,\langle x_2,x_1\rangle,\dots,\langle b,x_n\rangle\in S(Q)\), whence \(\langle b,a\rangle\in TS(Q)\). Because the transitive closure of a symmetric relation is symmetric, get \(\langle a,b\rangle\in TS(Q)\), finishing Case 1.
- Case 2: Suppose \(\langle b,a\rangle\in T(Q)\). Apply the same argument as in Case 1 except you don't need to invoke symmetry of the transitive closure at the end.

By the disjunctive syllogism, \(\langle a,b\rangle\in TS(Q)\) whenever \(\langle a,b\rangle\in ST(Q)\). whence \(ST(Q)\subseteq TS(Q)\), as promised.

We may now show that

Proposition. \(TST=TS\) and hence equals any other serial composite of \(S\)s and \(T\)s that has \(TS\) at its left end.

Proof: Let \(Q\) be any binary relation. We will show that \(TST(Q)=TS(Q)\) by double inclusion.

- \((TS(Q)\subseteq TST(Q))\) Well, \(Q\subseteq T(Q)\), so \(S(Q)\subseteq ST(Q)\) by monotonicity of \(S\), whence \(TS(Q)\subseteq TST(Q)\) by monotonicity of \(T\).
- \((TST(Q)\subseteq TS(Q))\) The previous proposition yields \(ST(Q)\subseteq TS(Q)\), By monotonicity of \(T\), we have \(TST(Q)\subseteq TTS(Q)\). Because \(TT=T\), we get \(TST(Q)\subseteq TS(Q)\).

By double inclusion, \(TST(Q)=TS(Q)\) for any \(Q\), whence \(TST=TS\). An easy induction parallel to the previous one for \(ST\) yields the assertion that any serial composite of \(S\)s and \(T\)s that has \(TS\) at its left end equals \(TS\), as promised.

With \(STS=TST=TS\), we almost have the complete "multiplication table" for \(A, B, C, D, E, R, S,\mbox{ and } T\) figured out. By the previous results and the "Redundant R", only \(RST\) and \(TSR\) remain. First, we check that

Lemma. For any binary relation \(Q\) on \(X\), \(TSR(Q)\) is an equivalence relation on \(X\) (that refines \(Q\)), Thus, \(E(Q)\subseteq TSR(Q)\).

Proof: \(TSR(Q)\) is reflexive on \(X\) because \(R(Q\) is reflexive on \(X\) and any refinement of a reflexive relation is reflexive. It is symmetric because \(SR(Q)\) is symmetric anf \(T\) preserves symmetry. It is transitive because that's what \(T\) does. Hence, \(TSR(Q)\) is an equivalence relation on \(X\) (that refines \(Q\)). Because \(E(Q)\) is the smallest such, we have \(E(Q)\subseteq TSR(Q)\), as promised.

Now for the converse inclusion, \(TSR(Q)\subseteq E(Q)\).

Lemma. \(TSR(Q)\subseteq E(Q)\).

Proof: Start with \(Q\subseteq E(Q)\).

- By monotonicity of \(R\), we get \(R(Q)\subseteq RE(Q)=E(Q)\) because \(E(Q)\) is already reflexive.
- By monotonicity of \(S\), we get \(SR(Q)\subseteq SE(Q)=E(Q)\) because \(E(Q)\) is already symmetric.
- By monotonicity of \(T\), we get \(TSR(Q)\subseteq TE(Q)=E(Q)\) because \(E(Q)\) is already transitive.

Thus, \(TSR(Q)\subseteq E(Q)\), as promised.

Theorem. \(TSR=E\).

Proof: The previous lemmata evince the double inclusion. Thus, \(TSR=E\), as promised.

Such a lot of work for so pedestrian a result! Only \(RST\) is left. It is not \(E\). Recall the counterexample \(Q=\{\langle1,2\rangle,\langle2,3\rangle,\langle1,3\rangle,\langle1,4\rangle\}\). Then \(RST(Q)\) is not transitive. (Briefly: \(RST(Q)= \{11,12,13,14,21,22,23,31,32,33,41,44\}\) and omits 24,34,42, and 43.) Although \(RST(Q)\) is symmetric and reflexive, it is strictly larger than \(SR(Q)\). It is also strictly larger than \(TR(Q)\) and \(ST(Q)\). This \(Q\) shows that \(RST\) is a new operator distinct from \(R, S, T, RS=SR=:A, RT=TR=:B, ST, TS\), and \(E=TSR\). Thus, the semigroup generated by the four closure operators has 9 elements and the following multiplication table. (The corresponding monoid has 10 elements; the tenth is the identity operator.) I can't say it's very interesting or worth all this trouble. In the table, the operators along the top are applied first, then the operator in the left column.

Cayley Table for the Closure Operators
	A	B	R	S	T	ST	TS	RST	E
A	A	RST	A	A	RST	RST	E	RST	E
B	E	B	B	E	B	E	E	E	E
R	A	B	R	A	B	RST	E	RST	E
S	A	RST	A	S	ST	ST	TS	RST	E
T	E	B	B	TS	T	TS	TS	E	E
ST	E	RST	RST	TS	ST	TS	TS	E	E
TS	E	E	E	TS	TS	TS	TS	E	E
RST	E	RST	RST	E	RST	E	E	E	E
E	E	E	E	E	E	E	E	E	E