6. Equivalence relations

In principle, from now on we shall stop using bold-face italic letters to denote undetermined assemblies; the reader will be able to discern easily from the context the assertions which apply to undetermined letters or relations.

1. Definition of an equivalence relation

Let $R\{x, y\}$ be a relation, $x$ and $y$ being distinct letters. The relation $R$ is said to be symmetric (with respect to the letters $x$ and $y$) if

If so, by substituting for $x$ and $y$ two letters $x'$ and $y'$, distinct from each other and from all the letters which appear in $R$, and then by substituting $y$ and $x$ for $x'$ and $y'$, respectively, we see that

Hence $R\{x, y\}$ and $R\{y, x\}$ are equivalent.

¶ Let $z$ be a letter which does not appear in $R$. The relation $R$ is said to be transitive (with respect to the letters $x, y$) if we have

2. Equivalence classes ; quotient set

Let $f$ be a function, E its domain, F its graph. The relation "$x \in E$ and $y \in E$ and $f(x) = f(y)$" is an equivalence relation on E, called the equivalence relation associated with f. It is equivalent to the relation $(\exists z)((x, z) \in F$ and $(y, z) \in F)$, i.e., to $(\exists z)((x, z) \in F$ and $(z, y) \in \overset{-1}{F})$, and therefore its graph is $\overset{-1}{F} \circ F$.

¶ We shall now show that every equivalence relation $\mathrm{R}$ on a set $\mathrm{E}$ is of this type. Let $\mathrm{G}$ be the graph of $\mathrm{R}$. For each $x \in \mathrm{E}$ the (non-empty) set $\mathrm{G}(x) \subset \mathrm{E}$ is called the equivalence class of $x$ with respect to $\mathrm{R}$; it is thus the set of all $y \in \mathrm{E}$ such that $\mathrm{R}\{x, y\}$. Every set which can be written as $\mathrm{G}(x)$ for some $x \in \mathrm{E}$ is called an equivalence class (with respect to $\mathrm{R}$). An element of an equivalence class is called a representative of this class. The set of equivalence classes with respect to $\mathrm{R}$ (that is, the set of all objects of the form $\mathrm{G}(x)$ for some $x \in \mathrm{E}$) is called the quotient set of $\mathrm{E}$ by $\mathrm{R}$ and is denoted by $\mathrm{E}/\mathrm{R}$. The mapping $x \to \mathrm{G}(x)$ $(x \in \mathrm{E})$ whose domain is $\mathrm{E}$ and whose target is $\mathrm{E}/\mathrm{R}$ is called the canonical mapping of $\mathrm{E}$ onto $\mathrm{E}/\mathrm{R}$.

C55. Let $\mathrm{R}$ be an equivalence relation on a set $\mathrm{E}$, and let $p$ be the canonical mapping of $\mathrm{E}$ onto $\mathrm{E}/\mathrm{R}$. Then

With the notation above, let $x$ and $y$ be elements of $\mathrm{E}$ such that

Then $x \in \mathrm{E}$ and $y \in \mathrm{E}$; let us show that $\mathrm{G}(x) = \mathrm{G}(y)$. Since $y \in \mathrm{G}(x)$, we have (Proposition 1) $\mathrm{G}(y) \subset (\mathrm{G} \circ \mathrm{G})(x) = \mathrm{G}(x)$. On the other hand, we also have $(y, x) \in \mathrm{G}$, whence $\mathrm{G}(x) \subset \mathrm{G}(y)$ and therefore

i.e., $p(x) = p(y)$. Conversely, if $\mathrm{G}(x) = \mathrm{G}(y)$, we have $y \in \mathrm{G}(y) = \mathrm{G}(x)$, so that $(x, y) \in \mathrm{G}$. This completes the proof.

¶ A section of the canonical mapping $p$ of $\mathrm{E}$ onto $\mathrm{E}/\mathrm{R}$ (§ 3, no. 8, Definition 11) is called more briefly a section of $\mathrm{E}$ (with respect to the relation $\mathrm{R}$).

Examples

3. Relations compatible with an equivalence relation

Let $\mathrm{R}\{x,\ x'\}$ be an equivalence relation and let $\mathrm{P}\{x\}$ be a relation. The relation $\mathrm{P}\{x\}$ is said to be compatible with the equivalence relation $\mathrm{R}\{x,\ x'\}$ (with respect to $x$) if we have

where $y$ denotes a letter which appears neither in P nor in R.

For example, it follows from C43 (Chapter I, §5), no. 1) that every relation $\mathrm{P}\{x\}$ is compatible with the equivalence relation $x = x'$.

C56. Let $\mathrm{R}\{x,\ x'\}$ be an equivalence relation on a set E, and let $\mathrm{P}\{x\}$ be a relation which does not contain the letter $x'$ and is compatible (with respect to $x$*) with the equivalence relation* $\mathrm{R}\{x,\ x'\}$. Then, if $t$ does not appear in $\mathrm{P}\{x\}$, the relation "$t \in \mathrm{E}/\mathrm{R}$ and $(\exists x)(x \in t$ and $\mathrm{P}\{x\})$*" is equivalent to the relation "*$t \in \mathrm{E}/\mathrm{R}$ and $(\forall x)((x \in t) \Rightarrow \mathrm{P}\{x\})$*".*

Let $t \in \mathrm{E}/\mathrm{R}$. If there exists $a \in t$ such that $\mathrm{P}\{a\}$, then for each $x \in t$ we have $\mathrm{R}\{a,\ x\}$ and hence $\mathrm{P}\{x\}$. Hence $(\exists x)(x \in t$ and $\mathrm{P}\{x\})$ implies $(\forall x)((x \in t) \Rightarrow \mathrm{P}\{x\})$. The converse is obvious since $t \in \mathrm{E}/\mathrm{R}$ implies that $t \neq \emptyset$.

¶ The relation

is said to be induced by $P\{x\}$ on passing to the quotient (with respect to $x$) with respect to R. If this relation is denoted by $P'\{t\}$, and if $f$ is the canonical mapping of E onto E/R, then the relation

(where $y$ does not appear in $P\{x\}$) is equivalent to ( $y \in E$ and $P\{y\}$), as is immediately verified.

4. Saturated subsets

Let $R\{x, y\}$ be an equivalence relation on a set E, and let A be a subset of E. A is said to be saturated with respect to R if the relation $x \in A$ is compatible (with respect to $x$) with $R\{x, y\}$; or, equivalently, if for each $x \in A$ the equivalence class of $x$ is contained in A. In other words, a set is saturated with respect to R if and only if it is the union of a set of equivalence classes with respect to R.

¶ Let $f$ be the canonical mapping of E onto E/R. If A is saturated with respect to R, then the equivalence class of each $x \in A$, which is equal to $\overset{-1}{f}\langle\{f(x)\}\rangle$, is contained in A, and hence $\overset{-1}{f}\langle f\langle A\rangle\rangle \subset A$; since in any case we have $A \subset \overset{-1}{f}\langle f\langle A\rangle\rangle$, it follows that $\overset{-1}{f}\langle f\langle A\rangle\rangle = A$. Conversely, if $A = \overset{-1}{f}\langle f\langle A\rangle\rangle$, then for every $x \in A$ the equivalence class $K = f(x)$ of $x$ with respect to R is an element of $f\langle A\rangle$; and since $K = \overset{-1}{f}\langle\{K\}\rangle$, we have $K \subset \overset{-1}{f}\langle f\langle A\rangle\rangle = A$. Thus the subsets of E which are saturated with respect to R are precisely the subsets A of E such that $A = \overset{-1}{f}\langle f\langle A\rangle\rangle$. Equivalently, they are the subsets of E of the form $\overset{-1}{f}\langle B\rangle$, where $B \subset E/R$; for the relation $A = \overset{-1}{f}\langle B\rangle$ implies $B = f\langle A\rangle$, hence $A = \overset{-1}{f}\langle f\langle A\rangle\rangle$.

¶ If $(X_\iota)_{\iota \in I}$ is a family of saturated subsets of E, then the sets $\bigcup_{\iota \in I} X_\iota$ and $\bigcap_{\iota \in I} X_\iota$ are saturated (§4, Propositions 3 and 4). If A is a saturated subset of E, then so is $\complement_E A$ (§4, Proposition 6).

¶ Let A now be an arbitrary subset of E. Then the set $\overset{-1}{f}\langle f\langle A\rangle\rangle$ contains A and is saturated. Conversely, if A′ is a saturated subset of E which contains A, we have $f\langle A'\rangle \supset f\langle A\rangle$, so that

Hence we may say that $\overset{-1}{f}\langle f\langle A\rangle\rangle$ is the "smallest" saturated subset of E which contains A (cf. Chapter III); this set is called the saturation of A with respect to the relation R. It is immediately seen that the saturation of A is the union of the equivalence classes of the elements of A. If $(\mathrm{X}_\iota)_{\iota \in \mathrm{I}}$ is a family of subsets of E and if $\mathrm{A}_\iota$ is the saturation of $\mathrm{X}_\iota$ with respect to R, then the saturation of $\bigcup_{\iota \in \mathrm{I}} \mathrm{X}_\iota$ is $\bigcup_{\iota \in \mathrm{I}} \mathrm{A}_\iota$ (§4, Proposition 3).

5. Mappings compatible with equivalence relations

Let R be an equivalence relation on a set E, and let $f$ be a function with domain E. Then $f$ is said to be compatible with the relation R if the relation $y = f(x)$ is compatible (with respect to $x$) with the relation $\mathrm{R}\{x,\ x'\}$.

¶ It comes to the same thing to say that the restriction of $f$ to each equivalence class is a constant mapping, in which case we say that $f$ is constant on each equivalence class with respect to R. If $g$ is the canonical mapping of E onto E/R, an equivalent statement is that the relation $g(x) = g(x')$ implies $f(x) = f(x')$; hence (§3, Proposition 9) we have the following criterion :

C57. Let R be an equivalence relation on a set E, and let g be the canonical mapping of E onto E/R. Then a mapping f of E into F is compatible with R if and only if f can be put in the form h $\circ$ g, where h is a mapping of E/R into F. The mapping h is uniquely determined by f; if s is any section of g, we have h $= f \circ s$.

The mapping $h$ is said to be induced by f on passing to the quotient with respect to R.

¶ Let $f$ be a mapping of a set E into a set F, and let $\mathrm{A} = f\langle \mathrm{E}\rangle \subset \mathrm{F}$. Let R be the equivalence relation associated with $f$ (no. 2); it is clear that $f$ is compatible with R. Moreover, the mapping $h$ induced by $f$ on passing to the quotient is an injection of E/R into F : for if $t$, $t'$ are equivalence classes with respect to R such that $h(t) = h(t')$, we have $f(x) = f(x')$ for all $x \in t$ and $x' \in t'$, which implies $t = t'$ by the definition of R. Let $k$ be the mapping of E/R onto A which has the same graph as $h$; then $k$ is bijective. If $j$ is the canonical injection of A into F and if $g$ is the canonical mapping of E onto E/R, then we may write

This relation is called the canonical decomposition of f.

¶ Let $f$ be a mapping of a set E into a set F, let R be an equivalence relation on E, and let S be an equivalence relation on F. Let $u$ be the canonical mapping of E onto E/R, and let $v$ be the canonical mapping of $F$ onto $F/S$. The mapping $f$ is said to be compatible with the equivalence relations $R$ and $S$ if $v\mathbin{\circ}f$ is compatible with $R$; this means that the relation $x\equiv x'$ (mod $R$) implies $f(x)\equiv f(x')$ (mod $S$). The mapping $h$ of $E/R$ into $F/S$ induced by $v\mathbin{\circ}f$ on passing to the quotient with respect to $R$ is then called the mapping induced by $f$ on passing to the quotients with respect to $R$ and $S$; it is characterized by the relation $v\mathbin{\circ}f=h\mathbin{\circ}u$.

6. Inverse image of an equivalence relation; induced equivalence relation

Let $\varphi$ be a mapping of a set $E$ into a set $F$, and let $S$ be an equivalence relation on $F$. If $u$ is the canonical mapping of $F$ onto $F/S$, the equivalence relation associated with the mapping $u\mathbin{\circ}\varphi$ of $E$ into $F/S$ is called the inverse image of $S$ under $\varphi$; if $R$ is this relation, $R\{x,y\}$ is equivalent to $S\{\varphi(x),\varphi(y)\}$, and the equivalence classes with respect to $R$ are the inverse images under $\varphi$ of the equivalence classes with respect to $S$ which meet $\varphi\langle E\rangle$.

¶ In particular, consider an equivalence relation $R$ on a set $E$, and let $A$ be a subset of $E$; then the inverse image of $R$ under the injection $j$ of $A$ into $E$ is called the equivalence relation induced by $R$ on $A$, and is denoted by $R_A$.

¶ The equivalence classes with respect to $R_A$ are the traces on $A$ of the equivalence classes with respect to $R$ which meet $A$. The injection $j$ is obviously compatible with the relations $R_A$ and $R$; the mapping $h$ of $A/R_A$ into $E/R$ induced by $j$ on passing to the quotient with respect to $R_A$ and $R$ is an injective mapping of $A/R_A$ into $E/R$: for if $f$ (resp. $g$) is the canonical mapping of $E$ onto $E/R$ (resp. $A$ onto $A/R_A$), then the relation $h(g(x))=h(g(x'))$, where $x\in A$ and $x'\in A$, is equivalent to $f(x)=f(x')$ and therefore to $g(x)=g(x')$. The image $h\langle A/R_A\rangle$ is equal to $f\langle A\rangle$. If $k$ is the bijective mapping of $A/R_A$ onto $f\langle A\rangle$ which has the same graph as $h$, then $k$ and its inverse are said to be canonical.

7. Quotients of equivalence relations

Let $R$, $S$ be two equivalence relations with respect to two letters $x$, $y$. We shall say that $S$ is finer than $R$ (or that $R$ is coarser than $S$) if the relation $S\Rightarrow R$ is true. If $R$ and $S$ are equivalence relations on the same set $E$, the statement that $S$ is finer than $R$ means that the graph of $S$ is contained in that of $R$, or again that every equivalence class with respect to $S$ is contained in an equivalence class with respect to $R$; or, equivalently, that every equivalence class with respect to $R$ is saturated with respect to $S$.

Examples

8. Product of two equivalence relations

Let $R\{x, y\}$ and $R'\{x', y'\}$ be two equivalence relations. Let $S\{u, v\}$ denote the relation

it is immediately verified that $S\{u, v\}$ is an equivalence relation, called the product of R and R', and denoted by $R \times R'$. Suppose that R is an equivalence relation on a set E and that R' is an equivalence relation on a set E'. Then the relation $S\{u, u\}$ is equivalent to

i.e., to $(\exists x)(\exists x')(u = (x, x')$ and $x \in E$ and $x' \in E')$, hence to $u \in E \times E'$. It follows that $R \times R'$ is an equivalence relation on $E \times E'$. If

is an element of $E \times E'$, the relation $S\{u, v\}$ is equivalent to

if $G$ and $G'$ are the graphs of $R$ and $R'$, respectively, this relation is in turn equivalent to $v \in G(x) \times G(x')$. Hence every equivalence class with respect to $R \times R'$ is the product of an equivalence class with respect to $R$ and an equivalence class with respect to $R'$, and conversely.

¶ Let $f$ and $f'$ be the canonical mappings of $E$ onto $E/R$ and $E'$ onto $E'/R'$, respectively, and let $f \times f'$ be the canonical extension of $f$ and $f'$ to the product sets (§ 3, no. 9). Then $(f \times f')(x, x') = (f(x), f'(x'))$ for all $(x, x') \in E \times E'$. The inverse image under $f \times f'$ of an element $(u, u')$ of $(E/R) \times (E'/R')$ is just the product $u \times u'$ of the equivalence class $u$ with respect to $R$ and the equivalence class $u'$ with respect to $R'$. It follows that the equivalence relation associated with $f \times f'$ is equivalent to $R \times R'$. The mapping $f \times f'$ can therefore be written as $h \circ g$, where $g$ is the canonical mapping of $E \times E'$ onto

and $h$ is a one-to-one mapping of $(E \times E')/(R \times R')$ onto

this mapping $h$ and its inverse are said to be canonical.

9. Classes of equivalent objects

Let $R\{x, y\}$ be an equivalence relation, which need not have a graph. It is obvious that if $x$, $x'$, $y$ are three distinct letters, the relation $R\{x, x'\}$ implies "$R\{x, y\} \Longleftrightarrow R\{x', y\}$" and therefore also implies the relation $(\forall y)(R\{x, y\} \Longleftrightarrow R\{x', y\})$. By the scheme S7 (Chapter I, § 5, no. 1), if we put $\theta\{x\} = \tau_y(R\{x, y\})$, the relation $R\{x, x'\}$ implies

Note, on the other hand, that by definition $R\{x, \theta\{x\}\}$ is the relation $(\exists y)(R\{x, y\})$ and hence (no. 1) is equivalent to $R\{x, x\}$. It follows that the relation $(R\{x, x\}$ and $R\{x', x'\}$ and $\theta\{x\} = \theta\{x'\})$ is equivalent to $R\{x, x'\}$, for it implies, by S6 (Chapter I, §5, no. 1), the relation

hence also $(R\{x, \theta\{x\}\}$ and $R\{x', \theta\{x\}\})$, and finally $R\{x, x'\}$ by transitivity and symmetry. And since, conversely, $R\{x, x'\}$ implies $R\{x, x\}$ and $R\{x', x'\}$, the assertion is proved. The term $\theta\{x\}$ is called the class of objects equivalent to x (with respect to the relation R).

¶ Suppose now that T is a term such that the relation

(1)

is true. Then the relation $(\exists x)(R\{x, x\}$ and $z = \theta\{x\})$ is collectivizing in z. For we may suppose that $x \in T$ implies $R\{x, x\}$; it is sufficient to replace T by the set of all $x \in T$ such that $R\{x, x\}$ (observing that $R\{x, y\}$ implies $R\{x, x\}$). Let $\Theta$ be the set of all objects of the form $\theta\{x\}$ for $x \in T$ (§1, no. 6). Suppose that $R\{y, y\}$ is true; then there exists $x \in T$ such that $R\{x, y\}$ and therefore $\theta\{y\} = \theta\{x\} \in \Theta$. The set $\Theta$ is called the set of classes of equivalent objects with respect to R; and for each $x$ such that $R\{x, x\}$, $\theta\{x\}$ is the unique element $z \in \Theta$ such that $R\{x, z\}$.

Under the same hypothesis, let $A\{x\}$ be a term such that $R\{x, y\}$ implies $A\{x\} = A\{y\}$. Then the relation $(\exists x)(R\{x, x\}$ and $z = \{x\})$ is collectivizing in $z$, since $R\{x, x\}$, being equivalent to $R\{x, \theta\{x\}\}$, implies $A\{x\} = A\{\theta\{x\}\}$, and consequently if E is the set of objects of the form $A\{t\}$ for $t \in \Theta$, then $R\{x, x\}$ implies $A\{x\} \in E$. If $f$ is the function $t \to A\{t\}$ $(t \in \Theta, A\{t\} \in E)$, then the relation $R\{x, x\}$ implies $A\{x\} = f(\theta\{x\})$.

In particular, if R is an equivalence relation on a set F, we may take $A\{x\}$ to be the equivalence class of x with respect to R (no. 2), and the function $f$ is then a bijection of $\Theta$ onto the quotient set F/R; this justifies the terminology introduced.

\* Example. Let $R\{x, y\}$ be the equivalence relation "$x$ and $y$ are two vector spaces of the same finite dimension over $\mathbf{C}$"; this relation has no graph. It satisfies condition (1) when T is the set of all vector subspaces of $\mathbf{C}^{(\mathbf{N})}$, or when the subset T' of T consists of the spaces $\mathbf{C}^n$ $(n \in \mathbf{N})$ with the conventions that $\mathbf{C}^0$ consists of the point 0 of $\mathbf{C}^{(\mathbf{N})}$ and that $\mathbf{C}^n$ $(n > 0)$ is the sum of the first $n$ components of the direct sum $\mathbf{C}^{(\mathbf{N})}$. With this second choice we have $\Theta = T'$.\*

Exercises

See the exercises for § 6.