Definition:Equivalence Relation Induced by Preordering

Definition

Let $\struct {S, \RR}$ be a relational structure such that $\RR$ is a preordering.

Let a relation $\sim_\RR$ be defined on $S$ by:

$x \sim_\RR y$ if and only if $x \mathrel \RR y$ and $y \mathrel \RR x$

Then $\sim_\RR$ is known as the equivalence (relation) induced by $\RR$.

Examples

Finite Set Difference on Natural Numbers

Consider the preordering $\RR$ on the powerset of the natural numbers:

$\forall a, b \in \powerset \N: a \mathrel \RR b \iff a \setminus b \text { is finite}$

where $\setminus$ denotes set difference.

Let $\sim_\RR$ denote the equivalence relation on $\powerset \N$ induced by $\RR$.

Then the $\sim_\RR$-equivalence class of an element $a$ of $\powerset \N$ is defined as:

$\eqclass a {\sim_\RR} = \set {b \in \powerset \N: a \symdif b \text { is finite} }$

where $\symdif$ denotes symmetric difference.

Also see

• Preordering induces Equivalence Relation for a proof that $\sim_\RR$ is indeed an equivalence relation.

Sources

• 1996: Winfried Just and Martin Weese: Discovering Modern Set Theory. I: The Basics ... (previous) ... (next): Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations