Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability (resit) / 2 / d

For a binary relation $R\subseteq A\times A$, reflexivity means $aRa$ for every $a\in A$; a symmetric relation satisfies $aRb\Rightarrow bRa$ for every $a,b\in A$; an antisymmetric relation satisfies $(aRb\text{ and }bRa)\Rightarrow a=b$ for every $a,b\in A$; transitivity means $(aRb\text{ and }bRc)\Rightarrow aRc$ for every $a,b,c\in A$; an irreflexive relation satisfies $\neg (aRa)$ for every $a\in A$. In particular, failure of reflexivity means at least one missing diagonal pair, whereas irreflexivity requires every diagonal pair to be missing.

There are $n^2$ possible ordered pairs and hence $2^{n^2}$ binary relations. A reflexive relation must contain the $n$ diagonal pairs, while its remaining $n^2-n$ pairs are unrestricted. Subtracting the reflexive relations givesbinary relations that are not reflexive.

A symmetric relation has $n$ independent choices on the diagonal. For each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered pairs $\{a,b\}$ of distinct elements, either both ordered pairs are included or neither is. Thus there are $2^{n+\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$ symmetric relations, so the requested number is

For each unordered pair $\{a,b\}$ with $a\ne b$, antisymmetry allows three choices: neither direction, only $(a,b)$, or only $(b,a)$. This contributes $3^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$. The diagonal is unrestricted by antisymmetry, but being not irreflexive requires a nonempty subset of the $n$ diagonal pairs. There are $2^n-1$ such choices. HenceThis allows some diagonal pairs to be absent; “not irreflexive” does not require a reflexive relation.