Relations

Definition 25   A relation from A to B is a subset $R\subseteq A\times B$. In the case where A=B we call this a relation on A.

We often use infix notation for relations, writing aRb for $(a,b)\in R$.

Definition 26   Relations can be composed using convolution: if $R\subseteq A\times B$ and $S\subseteq B \times C$ then

$$S\circ R=\{(a,c)\vert\mbox{ there is }b\in B\mbox{ with }(a,b)\in R\mbox{ and }(b,c)\in S\}$$

Definition 27   If $f:A\to B$ is a function then the graph of f is the relation $\Gamma_f=\{(a,f(a))\vert a\in A\}$.

Proposition 4.1   A relation R is the graph of a function $f:A\to B$ if and only if for every $a\in A$ there is exactly one element of R with first component a.

Proposition 4.2   $\Gamma_{f\circ g}=\Gamma_f \circ \Gamma_g$

Definition 28   The identity relation on A is the diagonal set $\{(a,a)\vert a\in A\}$. Note that this is also the graph of the identity function.

Definition 29   If $R\subseteq A\times B$ is a relation from A to B, then R^-1 is the relation from B to A given by $R^{-1}=\{(b,a)\vert(a,b)\in R\}$.

Definition 30   A relation R on A is reflexive iff the identity relation is contained in R.

Definition 31   A relation R on A is symmetric if whenever aRb, then bRa.

Definition 32   A relation R on A is antisymmetric if whenever aRb and bRa, then a=b.

Definition 33   A relation is transitive if whenever aRb and bRc, then aRc.

Definition 34   A relation R on A is total if whenever for every $a,b\in A$ either aRb or bRa.

Theorem 4.3   The properties reflexive, symmetric, and transitive are independent: there are relations which satisfy all properties but one, and any of the properties can be the one which fails.

Theorem 4.4   The properties antisymmetric, transitive, and total are independent: there are relations which satisfy all properties but one, and any of the properties can be the one which fails.

Proposition 4.5   Any total relation must be reflexive.

Proposition 4.6   For any relation R on A there is a smallest relation S with $R\subseteq S$ such that S is reflexive.

Proposition 4.7   For any relation R on A there is a smallest relation S with $R\subseteq S$ such that S is symmetric.

Proposition 4.8   For any relation R on A there is a smallest relation S with $R\subseteq S$ such that S is transitive.

Proposition 4.9   For any relation R on A there need not be a smallest relation S with $R\subseteq S$ such that S is total.