Relation

NOTE

A relation is a special set

Inverse of Relation

Discrete Mathematics ETH, p.53

The inverse of a relation $\rho$ from $A$ to $B$ is the relation $\rho$ from $B$ to $A$ defined by

$$\hat{\rho }\stackrel{def}{=}\{(b,a)|(a,b)\in \rho \}$$

Eigenschaften von Relation

Eigenschaften von Relation $\rho$ auf $A$:

• reflexiv: $\forall a(a\rho a)$
• symmetrisch: $\forall a,b(a\rho b\leftrightarrow b\rho a)$
• antisymmetrisch: $\forall a,b(a\rho b\wedge b\rho a\to a=b)$
• transitiv: $\forall a,b,c(a\rho b\wedge b\rho c\to a\rho c)$

Transitive Closure

$${\rho }^{\ast }\stackrel{def}{=}\bigcup P_{\rho }\text{ with }{P}_{\rho }=\{\rho ,{\rho }^2,{\rho }^3,\dots \}$$

Equivalence Relations

Discrete Mathematics ETH, p.57

An equivalence relation is a relation on a set $A$ that is reflexive, symmetric, and transitive.

Example

${\equiv }_m$ is an equivalence relation on $\mathbb{Z}$ ${\equiv }_3$

equivalence relation example.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠ You can decompress Drawing data with the command palette: ‘Decompress current Excalidraw file’. For more info check in plugin settings under ‘Saving’

Excalidraw Data

Text Elements

-3

6

0

10

7

Link to original

Equivalence class

$$[a{]}_{\theta }\stackrel{def}{=}\{b\in A|b\theta a\}$$

each group of elements circled in red is a equivalence class

Circular transclusion detected: Excalidraw/equivalence-relation-example.excalidraw

Example

The equivalence classes of ${\equiv }_3$

Partition via equivalence relations

$A/\theta \stackrel{def}{=}\{[a{]}_{\theta }|a\in A\}$ The quotient set of $A$ by $\theta$, or simply A modulo $\theta$ or $A$ mod $\theta$

This concept is similar to factor group and factor rings

• Section 14 Factor Groups
• Section 26 Homomorphisms and Factor Rings

Context	Relation type	Quotient object	Categorical role
Set	Equivalence relation	Partition ( $S/\sim$ )	Coequalizer in $\mathbf{Set}$
Group	Normal subgroup ( $N$ ) $a\sim b⟺a^{-1}b\in N$	Factor group ( $G/N$ )	Coequalizer in $\mathbf{Grp}$
Ring	Ideal ( $I$ ) $a\sim b⟺a-b\in I$	Factor ring ( $R/I$ )	Coequalizer in $\mathbf{Ring}$

Example

Consider $A=\mathbb{Z}\times (\mathbb{Z}\setminus \{0\})$ and define $\sim$ as $(a,b)\sim (c,d)\stackrel{def}{⟺}ad=bc$ $\sim$ is an equivalence relation

• reflexive: $(a,b)\sim (a,b)⟺ab=ba⟺ab=ab$
• symmetric: $(a,b)\sim (c,d)⟺ad=bc⟺bc=ad⟺cb=da⟺(c,d)\sim (a,b)$
• transitive: $(a,b)\sim (c,d),(c,d)\sim (e,f)⟹ad=bc\text{ and }cf=de$
  • If $c=0$
• then $a=0$ and $e=0$ $⟹af=be⟺(a,b)\sim (e,f)$
  • If $c\ne 0$
• then $adcf=bcde⟹adf=dbe⟹af=be⟺(a,b)\sim (e,f)$

And now we can define the set of rational numbers

Definition of the rational numbers

$$\mathbb{Q}\stackrel{def}{=}(\mathbb{Z}\times (\mathbb{Z}\setminus \{0\}))/\sim$$

Intersection of equivalence relations

Discrete Mathematics ETH, p.58

The intersection of two equivalence relations (on the same set) is an equivalence relation.

Example

${\equiv }_3\cap {\equiv }_5={\equiv }_{15}$