A binary relation $R$ over sets $A$ and $B$ is a subst $R \subset A \times B$.
$(a, b) \in R$ is also denoted by $aRb$.

Totality and uniqueness

$R$ may have the following properties:

  • total:
    $\forall a \in A, \exists b \in B, aRb$. (left)
    $\forall b \in B, \exists a \in A, aRb$. (right)
  • unique:
    $\forall b \in B, \exists_{\leq 1} a \in A, aRb$. (left)
    $\forall a \in A, \exists_{\leq 1} b \in B, aRb$. (right)

Then, we can define

  • function: a left-total and right-unique relation
  • injection: a left-unique function
  • surjection: a right-total function
  • bijection: a left-unique and right-total function

A function $f \subset A \times B$ is also denoted by $f: A \to B$ or $A \xrightarrow{f} B$.
$A$ is called the domain and $B$ is called the codomain.
A binary function $f: A \times B \to C$ can be written in prefix notation $f(a, b)$ or in infix notation $afb$.

Composition

The composition of relations is a function $\circ: (B \times C) \times (A \times B) \to (A \times C)$ defined by $$S \circ R = \{(a, c) \in (A \times C) \mid \exists b \in B, aRb \land bSc\}.$$ For functions, we have the composition of functions that outputs the composite function.
Alternatively, we can write the composite function $g \circ f$ as $f ; g$, representing the diagram $A \xrightarrow{f} B \xrightarrow{g} C$.

Endorelation

An endorelation $R \subset A \times A$ may have the following properties:

  • reflexive: $\forall a \in A, aRa$. (all loops)
  • irreflexive: $\forall a \in A, \lnot aRa$. (no loop)
  • symmetric: $\forall a_1, a_2 \in A, a_1 R a_2 \implies a_2 R a_1$. (bidirected)
  • asymmetric: $\forall a_1, a_2 \in A, a_1 R a_2 \implies \lnot a_2 R a_1$. (oriented)
  • antisymmetric: $\forall a_1, a_2 \in A, a_1 R a_2 \land a_2 R a_1 \implies a_1 = a_2$. (oriented or loop)
  • semiconnex: $\forall a_1, a_2 \in A, a_1 \neq a_2 \implies a_1 R a_2 \lor a_2 R a_1$. (tournament)
  • connex: $\forall a_1, a_2 \in A, a_1 R a_2 \lor a_2 R a_1$. (tournament or loop)
  • transitive: $\forall a_1, a_2, a_3 \in A, a_1 R a_2 \land a_2 R a_3 \implies a_1 R a_3$.

Then, we can define

  • preorder ($\leq$): a reflexive and transitive relation (a graph with all loops)
  • partial order: an antisymmetric preorder (an oriented graph with all loops)
  • total order: a connex partial order (a tournament with all loops)
  • strict preorder ($<$): an irreflexive and transitive relation (a graph without any loops)
  • strict partial order: an asymmetric strict preorder (a oriented graph without any loops)
  • strict total order: a semiconnex strict partial order (a tournament without any loops)
  • equivalence relation ($\sim$): a symmetric preorder (a bidirected graph with all loops)

A partially ordered set is called a poset and a preordered set is called a proset.

A function $f: A \to B$ is monotonic (order-preserving) if $a_1 R_A a_2 \implies f(a_1) R_B f(a_2)$, where $R$ is a kind of orders.