"Theorem 4 Let $\mathscr E$ be an equivalence relation on a nonempty set $X$. Then $X/\mathscr E$ is a partition of $X$.

[Proof] By Theorem 3(a) and Definition 6, $X/\mathscr E =\{\,x/\mathscr E\mid x \in X\,\}$ is a family of nonempty subsets of $X$. We next show that

$x/\mathscr E \neq y/\mathscr E ⇒ x/\mathscr E \cap y/\mathscr E = \emptyset$

by showing its contrapositive: $\color{red}{x/\mathscr E \cap y/\mathscr E \neq \emptyset \Rightarrow x/\mathscr E=y/\mathscr E}$.

The last assertion is a direct consequence of Theorem 3(b) and (c). Finally, we have to show that $\bigcup\limits_{x\in X} x/ \mathscr E = X$. This is also trivial, since each $x$ in $X$ belongs to $x/\mathscr E$."

The author assumes the partition $X/\mathscr E$ of $X$ satisfies two conditions to be a partition as the following:

(a) $(x/\mathscr E, y/\mathscr E \in X/\mathscr E) \land (x/\mathscr E \neq y/\mathscr E) \Rightarrow x/\mathscr E \cap y/\mathscr E = \emptyset$

(b) $\bigcup \limits_{x \in X}x/\mathscr E = X$

But as shown in the definition
$X/\mathscr E =\{\,x/\mathscr E\mid x \in X\,\}$,
$x/\mathscr E$ is the only element of $X/\mathscr E$, not $y/\mathscr E \in X$.

So why the author assumes $y/\mathscr E \in X$ is also an element of $X/\mathscr E$?


"Definition 5 Let $X$ be a nonempty set. By a partician $P$ of $X$ we mean a set of nonempty subsets of $X$ such that:

(a) If $A, B\in P$ and $A\neq B$, then $A\cap B=\emptyset$

(b) $\bigcup \limits_{C \in P}C = X$"

"Definition 6. Let $\mathscr E$ be an equivalence relation on a nonempty set $X$. For each $x∈X$, we define
​$$x/\mathscr E=\{\,y\in X\mid y\mathscr Ex\,\}$$
which is called the equivalence class determined by the element $x$.
The set of all such equivalence classes on $X$ is denoted by $X/\mathscr E$; that is, $X/\mathscr E=\{\,x/\mathscr E\mid x\in X\,\}$.
The symbol $X/\mathscr E$ is read "$X$ modulo $\mathscr E$," or simply "$X$ mod $\mathscr E$".

Source: Set Theory by You-Feng. Lin and Shwu-Yeng T. Lin


1 Answer 1


The notation $\{\,x/\mathscr E\mid x\in X\,\}$ is the set of all objects of the form $x/\mathscr E$ that can be obtained by letting $x$ run over the elements of $X$. For example, if $X=\{1,2,3\}$ then $\{\,x/\mathscr E\mid x\in X\,\}=\{1/\mathscr E,2/\mathscr E,3/\mathscr E\}$ (which may possibly be simplified, for example if it happens to be the case that $1/\mathscr E=2/\mathscr E$, then this is in fact the set $\{1/\mathscr E,3/\mathscr E\}$). At any rate, in the given context we have that $y\in X$. Therefore $y/\mathscr E$ is an element of $\{\,x/\mathscr E\mid x\in X\,\}$

Formal definition: If $\Phi$ is a class function and $A$ is a set, then the Axiom Scheme of Replacement states that there exists a set $B$ with the property that $$\forall z\colon z\in B\leftrightarrow\exists x\in A\colon z=\Phi(x) $$ In other words, $B$ contains precisely what can be onbtained by applying $\Phi$ to elements of $A$. The set $B$ guaranteed to exist this way is also written as $\{\,\Phi(x)\mid x\in A\,\}$, where $x$ is a free variable, or sometimes as $\Phi[A]$.

  • 1
    $\begingroup$ Fun fact: this is a mathematical example of "confusing the map with the territory" $\endgroup$ Jan 29, 2016 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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