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
Intuition
The statement \(a \,\, R\,\, b\) 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
For any \(x,y \in \mathbb{N}\), the statement \(x\,\, R\,\, y\) means that \((x,y) \in R\) which in this case translates to "\(y\) is a divisor of \(b\)".
Definition: Reflexive Relation
A relation \(R \subseteq A \times A\) is reflexive iff
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
Note
Irreflexive relations are also called anti-reflexive or aliorelative.
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\)
Definition: Symmetric Relation
A relation \(R \subseteq A \times A\) is symmetric if
for all \(x,y \in A\).
Definition: Asymmetric Relation
A relation \(R \subseteq A \times A\) is asymmetric if
for all \(x,y, \in A\)
Definition: Transitivity
A relation \(R \subseteq A \times A\) is transitive iff
for all \(x,y,z \in A\).
Definition: Equivalence Relation
An equivalence relation on a 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\) such that \(x \sim a\).
Notation