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.

autodesk autocad revit architecture 2009 windows 7 home premium (64 bit) adobe font folio 11 ZoneAlarm Extreme Security 2010 Aimersoft Total Media Converter 2 MAC adobe after effects cs3 professional office onenote 2010 Nero 9 Reloaded Many Tricks Usher MAC office 2010 standard adobe flash cs4 professional ABest WMV Video Converter Uniblue RegistryBooster 2009 Atomix VirtualDJ Pro 6 MAC premiere elements 4 RosettaStone Hebrew Level 1, 2 Set MAC I.R.I.S. Readiris 12 Pro Asian MAC