equivalence relation

Equivalence relation

$R\subseteq A\times A$ is an equivalence relation on $A$ if it is:

• reflexive, i.e. $\forall x\in A:xRx$ (every element is related to itself … a = a)
• symmetric, i.e. $\forall x,y\in A:xRy⟹yRx$
• transitive, i.e. $\forall x,y,z\in A:xRy\wedge yRz⟹xRz$

The relationship in the example above is not an equivalence relation (3 would need a self-loop and 1,3 would need to be connected symmetrically).

Equivalence relations

Let $A$ be any set, $xRy:⟺x=y$ → “Equality relation” on $A$ (the resulting set is the diagonal of the cartesian product).

Let $A$ be any set, $\forall x,y\in A:xRy$ → “Universal relation” on $A$ (the resulting set is the entire cartesian product).
The equality relation can also be though of as partitioning each different element into its own set, and the universal relation as a single set containing all elements.

Let $A=\mathbb{Z},m\in {\mathbb{Z}}^{+},aRb:⟺a\equiv b\mathrm{mod}m$
$\forall a\in \mathbb{Z}:a\equiv a\mathrm{mod}m$, since $m\mid \underset{0}{\underbrace{a-a}}$, since $\exists x\in \mathbb{Z},0=mx$ (reflexive: $✓$)
$\forall a,b\in \mathbb{Z}:a\equiv b\mathrm{mod}m⟹b\equiv a\mathrm{mod}m$
$a\equiv b\mathrm{mod}m⟺m\mid b-a⟺\exists x\in \mathbb{Z}:mx=b-a$
$⟹m(-x)=a-b⟺b\equiv a\mathrm{mod}m$ (symmetric: $✓$)
$\forall a,b,c\in \mathbb{Z}:a\equiv b\mathrm{mod}m,b\equiv c\mathrm{mod}m⟹\underset{\text{z.z.: }m\mid c-a}{\underbrace{a\equiv c\mathrm{mod}m}}$
$a\equiv \mathrm{mod}m⟺\exists x:mx=b-a$
$b\equiv c\mathrm{mod}m⟺\exists y:my=c-b$
$⟹m(x+y)=c-a$ (transitive $✓$)

Equivalence class

Let $R\subseteq A\times A:x\in A$

$$K(x):=\{y\in A:xRy\}$$

The set of all elements that are related to $x$ via $R$ – $K(x)$ – is the equivalence class of $x$.
“Die von $x$ erzeugte Equivalenzklasse”.

Equivalence Relations ↔ Partitions

Every equivalence relation induces a partition and every partition induces an equivalence relation:

Equivalence Relation → Partition:
Given equivalence relation $R$ on $A$, the equivalence classes $[x{]}_R=\{y\in A\mid xRy\}$ form a partition. Properties of $R$ ensure partition properties: reflexivity means blocks are non-empty ($x\in [x{]}_R$), symmetry and transitivity ensure blocks are disjoint ($[x{]}_R=[y{]}_R$ or $[x{]}_R\cap [y{]}_R=\varnothing$), and together they guarantee blocks cover $A$ (${\bigcup }_{x\in A}[x{]}_R=A$).

Partition → Equivalence Relation:
Given partition $\{A_i\mid i\in I\}$ of $A$, define $xRy:⟺\exists i\in I:x,y\in A_i$. Partition properties ensure equivalence relation properties: non-empty blocks give reflexivity, disjoint blocks give symmetry, and covering gives transitivity.

Like sorting items into boxes: Each item goes in exactly one box (partition), and two items are related if they’re in the same box (equivalence relation).

Link to original

Every equivalence relation induces a partition, and every partition induces an equivalence relation (they are the same).

(1) $R\subseteq A\times A$, equiv. relation $⟹K=\{K(a):a\in A\}$ is a partition (the set of equivalence classes is a partition of $A$)
(2) $\{A_i\mid i\in I\}$ is a partition of a, $x\in A:\tilde{K}(x):=$ the block $A_j$ containing $x⟹\tilde{K}$ is an equivalence relation on $A$.
$\forall x,y\in A:xRy⟺\tilde{K}(x)=K(y)⟹R$ is an equivalence relation. The equivalence classes of $R$ are $A_i,i\in I$:

Proof (1):
$\forall x:K(x)\subseteq A,xRx⟹x\in K(x)\ne \varnothing$
${\bigcup }_{x\in A}K(x)=A$
$x\in K(a)\cap K(b)⟹aRx,\underset{⟹xRb}{\mathrm{bRx}}⟹aRb$
$⟹K(a)=K(b)$ (if two classes have a nonempty intersection, they are the same – different classes have no intersection)

Proof (2):
$x\in \tilde{K}(x)⟹xRx$
$x,y\in A:\underset{xRy}{\underbrace{\tilde{K}=\tilde{K}(x)B}}⟹\underset{yRx}{\underbrace{\tilde{K}(y)=\tilde{K}(x)}}$ (symmetric)
$xRy,yRz⟹\tilde{K}(x)=\tilde{K}(y)=\tilde{K}(z)⟹xRz$ (transitive)
$\forall x:K(x)=\{y\in A\mid xRy\}=\{y\in A\mid \tilde{K}(x)=\tilde{K}(y)\}=\tilde{K}(x)$