Properties of Relations

Definition 32   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 33   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 34   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 55   $\Gamma_{f\circ g}=\Gamma_f \circ \Gamma_g$

(2 Points )

Definition 35   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 36   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 37   A relation $R$ on $A$ is reflexive iff the identity relation is contained in $R$.

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

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

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

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

Theorem 56   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.

(6 Points )

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

(3 Points )

Proposition 58   The intersection of any family of symmetric relations is symmetric

(3 Points )

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

(3 Points )

Proposition 60   The intersection of any family of transitive relations is transitive.

(3 Points )

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

(3 Points )