Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics, and probability / Discrete mathematics / 3

A binary relation $R$ on $A$ is a reflexive relation precisely when $aRa$ for every $a\in A$.

A binary relation $R$ on $A$ is a symmetric relation precisely when $aRb\Rightarrow bRa$ for all $a,b\in A$.

A binary relation $R$ on $A$ is an antisymmetric relation precisely when $(aRb\text{and}bRa)\Rightarrow a=b$ for all $a,b\in A$.

A binary relation $R$ on $A$ is a transitive relation precisely when $(aRb\text{and}bRc)\Rightarrow aRc$ for all $a,b,c\in A$.

A binary relation is an equivalence relation precisely when it is reflexive, symmetric, and transitive.

For a counterexample to closure under union of antisymmetric relations, take $A=\{0,1\}$, $R=\{(0,1)\}$, and $S=\{(1,0)\}$. Each is an antisymmetric relation: neither contains an off-diagonal pair together with its reverse. But $R\cup S$ contains both $(0,1)$ and $(1,0)$ while $0\ne 1$. Therefore $R\cup S$ is not an antisymmetric relation.

Write $q(x,y)=x^2+y^2$. Equality of $q$-values defines an equivalence relation induced by a function: equality is reflexive, symmetric, and transitive, so all three properties hold for $R$. The equivalence class of $(x,y)$ isFor $(x,y)\ne (0,0)$ this is the circle centred at the origin with radius $\sqrt{x^2+y^2}$; the remaining equivalence class is the singleton $\{(0,0)\}$.

This binary relation is not an equivalence relation, because it is not symmetric: $(0,0)R(0,1)$ since $0\le 1$, but $(0,1)R(0,0)$ is false. In fact the injective encoding $(a,b)\mapsto 10a+b$ gives a total order. There are no equivalence classes for this binary relation.

Every nonzero integer $a$ has $a^2>0$, proving reflexivity. Because $ab=ba$, the relation is symmetric. If $ab>0$ and $bc>0$, then $ac=(ab)(bc)/b^2>0$, proving transitivity. Thus this is an equivalence relation, whose two equivalence classes are the positive integers and the negative integers: