Relation, preorder #
Relation #
Definition. A relation over a set $S$ is a set of tuples over $S$ with the same arity. In particular:
For instance, if
\(S = \{a,b,c,d\}\) , then- \(\Big\{ (a,a),\ (a,b),\ (b,a),\ (b,c) \Big\}\)
- \(\Big\{ (a,b,a),\ (c,c,c) \Big\}\)
If $S$ is finite with size $n$, then how many $k$-ary relations are there over $S$?
A $k$-ary relation over $S$ is a subset of $S^k$.
So there are $2^{|S^k|} = 2^{n^k}$ $k$-ary relations over $S$.
Binary relation #
A binary relation can be represented in multiple ways.
In particular, it can be represented as a (directed) graph (and conversely).
For instance, the relation
\(\Big\{ (a,a),\ (a,b),\ (b,a),\ (b,c) \Big\}\)over
\(\{a,b,c,d\}\)can be viewed as the graph:
A binary relation can also be represented with an infix symbol.
For instance, the same relation
\(\Big\{ (a,a),\ (a,b),\ (b,a),\ (b,c) \Big\}\)can be represented as
\(a \preceq a \ \) , \(a \preceq b\ \) , \(b \preceq a\ \) , \(b \preceq c\ \) .Reflexivity, transitivity, antisymmetry #
Definition. A binary relation $\preceq$ over a set $S$ is
- reflexive if $x \preceq x$ for all $x \in S$
- transitive if for all $x, y, z \in S$
$\qquad \qquad \qquad x \preceq y$ and $y \preceq z$ imply $x \preceq z$
- antisymmetric if for all $x, y \in S$
$\qquad \qquad \qquad x \preceq y$ and $y \preceq x$ imply $x = y$
Which of these three properties does the relation below satisfy?
Only reflexivity.
Preorder, order #
Definition. A binary relation is a preorder if it is reflexive and transitive. It is an order if it is also antisymmetric.
Total vs partial #
Definition. A preorder $\preceq$ over $S$ is total if every two elements of $S$ are comparable, i.e. if
$ \qquad \qquad x \preceq y$ or $y \preceq x$ for all $x, y \in S$.
A preoder that is not total is called partial.
Example. The natural order $\le$ over $\mathbb{R}$ is a total order (i.e. total, reflexive, transitive and antisymmetric).
Example. If $S$ is a set, then the set inclusion relation $\subseteq$ over the power set of $S$ is a partial order (i.e. reflexive, transitive and antisymmetric).
Warning. The term “order” is often used to refer to a total order.
Sorting #
If $S$ is a set, then a total preorder over $S$ is intuitively any relation that allows sorting $S$.
Example. Let $P$ be the set of people, and let $\preceq_{\text{age}}$ be the relation defined over $P$ by
$\qquad \qquad p_1 \preceq_{\text{age}} p_2$ iff $p_1$ is younger than (or as old as) $p_2$.
Then $\preceq_{\text{age}}$ is a total preorder (i.e. total, reflexive and transitive), but it is not an order (i.e. not antisymmetric), because two persons can have the same age.
Lexicographic product #
Notation. If $\preceq_o$ is a preorder, let us use:
- $x \prec_o y$ as a shortcut for ($ x \preceq_o y$ and $ y \not\preceq_o x$ ),
- $x =_o y$ as a shortcut for ($x \preceq_o y$ and $y \preceq_o x$ ).
Definition. The lexicographic product $\preceq_{1,2}$ of a preorder $\preceq_1$ by a preorder $\preceq_2$ is defined by
$\qquad \qquad x \preceq_{1,2} y$ iff $x \prec_1 y$ or ( $x =_1 y$ and $x \preceq_2 y$ )
Example. Let $P$ be the set of people, and let $\preceq_{\text{age}}$ and $\preceq_{\text{size}}$ be the total preorders defined over $S$ by
$\qquad \qquad p_1 \preceq_{\text{age}} p_2$ iff $p_1$ is younger than (or as old as) $p_2$, and
$\qquad \qquad p_1 \preceq_{\text{size}} p_2$ iff $p_1$ is smaller than (or as tall as) $p_2$.
Then the lexicographic product $\preceq_{\text{age, size}}$ of $\preceq_{\text{age}}$ by $\preceq_{\text{size}}$ is defined by
$\qquad p_1 \preceq_{\text{age, size}} p_2$ iff
$\qquad \qquad p_1$ is strictly younger than $p_2$, or
$\qquad \qquad$ they have the same age and $p_1$ is smaller than (or as tall as) $p_2$.
Warning. The lexicographic product of $\preceq_1$ by $\preceq_2$ may differ from the lexicographic product of $\preceq_2$ by $\preceq_1$.
Note. The lexicographic product of a total preorder by a total preorder (resp. a total order) is itself a total preorder (resp. a total order).