Relations

Definition: Relation

A relation $R\subseteq A\times B$ between two Sets $A$ and $B$ is any subset of the Cartesian product $A\times B$.

NOTATION

For any $a\in A$ and any $b\in B$, if $(a;b)\in R$, then we write

$$aRb$$

INTUITION

The statement $aRb$ translates to “there is a relationship between $a$ and $b$ which is expressed by $R$“.

EXAMPLE

Let $R\subseteq \mathbb{N}\times \mathbb{N}$ be the relation

$$R=\{(a;b)\mid a,b\in \mathbb{N}\text{ and }b\text{ is a divisor of a}\}$$

For any $x,y\in \mathbb{N}$, the statement $xRy$ means that $(x,y)\in R$ which in this case translates to ”$y$ is a divisor of $b$“.

Types of Relations

Reflexive and Irreflexive Relations

Definition: Reflexive Relation

A relation $R\subseteq A\times A$ is reflexive iff

$$xRx$$

is true for all $x\in A$.

Definition: Irreflexive Relation

A relation $R\subseteq A\times A$ is irreflexive if there is no $x\in A$ such that

$$xRx$$

NOTE

Irreflexive relations are also called anti-reflexive or aliorelative.

Unique Relations

Definition: Right-Unique Relation

A relation $R\subseteq A\times B$ is right-unique, if for all $a\in A$ and all $b_1,b_2\in B$

$$((aR{b}_1)\wedge (aR{b}_1))⟹b_1=b_2$$

Symmetric and Asymmetric Relations

Definition: Symmetric Relation

A relation $R\subseteq A\times A$ is symmetric if

$$xRy⟹yRx$$

for all $x,y\in A$.

Definition: Asymmetric Relation

A relation $R\subseteq A\times A$ is asymmetric if

$$((xRy)\wedge (yRx))⟹x=y$$

for all $x,y,\in A$

Transitive Relations

Definition: Transitivity

A relation $R\subseteq A\times A$ is transitive iff

$$((xRy)\wedge (yRz))⟹xRz$$

for all $x,y,z\in A$.

Equivalence Relations

Definition: Equivalence Relation

An equivalence relation on the set $A$ is any relation $R\subseteq A\times A$ which is reflexive, transitive and symmetric.

NOTATION

Equivalence relations are usually denoted with $\sim$ instead of $R$.

INTUITION

The statement $x\sim y$ means that $x$ is equal to $y$ in the sense of $\sim$.

Definition: Equivalence Class

Let $A$ be a set with an Equivalence Relation $\sim$.

The equivalence class of an element $a\in A$ formed by $\sim$ is the set of all $x\in A$ which are equivalent to $a$.

$$\{x\in A\mid a\sim x\}$$

NOTATION

$$[a{]}_{\sim }$$