home

Relations

A relation can be defined between elements of set $$A$$ and elements of another set $$B$$.

Relations may also be defined between elements of the same set.

The letter $$\mathcal R$$ is used to refer to relation.

Syntax

Let $$A$$ and $$B$$ be two sets, and $$x \in A$$, $$y \in B$$. Given some $$\mathcal R$$ linking these, it can be stated that $$x$$ is related to $$y$$ with respect to the relation $$\mathcal R$$. This may be more succinctly expressed as $$x\ \mathcal R\ y$$.

Representation

Relations within or between bounded sets be shown via a boolean matrix. For two sets $$A$$ and $$B$$ this is then shown as a matrix of order $$|A| \times |B|$$.

For example, given $$A = \{1,2,3,4,5\}$$ the relation $$\mathcal R_< = \{(a,b) \in A^2\ |\ a < b\}$$ may be noted as $M_{\mathcal R_<} = \begin{bmatrix} 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}$

Equivalently, a directed graph that expresses this as an adjacency matrix may also be shown.

Properties

Term Bi-condition Digraph Matrix
reflexivity $$x \mathcal R x$$ loop on every node $$M_{i,i} = 1$$
symmetry $$a \mathcal R b \iff b \mathcal R a$$ parallel edges on all connected nodes $$M_{i,j} = M_{j,i}$$
anti-symmetry $$a \mathcal R b \land b \mathcal R a \implies a = b$$ no parallel edges $$M_{i,j} \neq 0 \implies M_{j,i} = 0$$
transitivity $$a \mathcal R b \land b \mathcal R c \implies a \mathcal R c$$ direct paths between any two connected nodes $$M^2_{i,j} \neq 0 \implies M_{i,j} \neq 0$$

If a relation is reflexive, symmetric, and transitive it is termed an Equivalence relation.

A relation that is reflexive, anti-symmetric, and transitive is a partial order.

A relation is a total order if satisfies the properties of a partial order and $$\forall a,b \in S$$ either $$a \mathcal R b$$ or $$b \mathcal R a$$. That is, all elements of $$S$$ must be comparable under $$\mathcal R$$.