4.3 Domain equals range

Many relations have the same set for domain and range. These relations may have additional attributes.

• Reflexive: $L \subseteq X \times X, \forall x \in X: \exists (x,x) \in L$
• Symmetric: $L \subseteq X \times X, \forall (x,y) \in L: \exists (y,x) \in L$
• Antisymmetric: $L \subseteq X \times X, \forall (x,y) \in L: (x \ne y) \Rightarrow \neg(\exists (y,x) \in L)$
• Transitive: $L \subseteq X \times X, \forall (x,y) \in L: \forall (y,z) \in L: \exists (x,z) \in L$
• Total: $L \subseteq X \times X, \forall x,y \in X: ((x,y) \in L) \vee ((y,x) \in L)$ . Total implies reflexive.

Let us consider some examples:

• Real number equality. It is reflexive because $\forall v \in \mathbb{R}: v = v$ . It is symmetric because $\forall x \in \mathbb{R}, y \in \mathbb{R}: x = y \Rightarrow y = x$ . It is also transitive because $\forall x,y,z \in \mathbb{R}: (x = y) \wedge (y = z) \Rightarrow (x = z)$ . It is not total because $1 = 2$ and $2 = 1$ are both false. It is antisymmetric.
• Real number $\le$ (less-than-or-equal-to). It is reflexive because $\forall v \in \mathbb{R}: v \le v$ . It is not symmetric because $1 \le 2$ , but $\neg(2 \le 1)$ . It is transitive because $\forall x,y,z \in \mathbb{R}: (x \le y) \wedge (y \le z) \Rightarrow (x \le z)$ . It is total and antisymmetric.
• Real number $<$ (less-than). It is not reflexive because $\forall v \in \mathbb{R}: \neg(v < v)$ . It is not symmetric because $\forall x,y \in \mathbb{R}: (x < y) \Rightarrow \neg(y < x)$ . Last, but not least, it is transitive because $\forall x,y,z \in \mathbb{R}: (x < y) \wedge (y < z) \Rightarrow (x < z)$ . It is not total, but it is antisymmetric.
• Positive integers ``is a factor of''. It is reflexive because each integer is its own factor. It is not symmetric because 3 is a factor of 9, but 9 is not a factor of 3. It is transitive because if $i$ is a factor of $j$ , and $j$ is a factor of $k$ , then $i$ is a factor of $k$ . This relation is not total, and it is antisymmetric.

There are special names for relations that satisfy a combination of properties:

• Partial order: reflexive, antisymmetric and transitive
• Total order: total, antisymmetric and transitive
• Equivalence: reflexive, symmetric and transitive