Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation / 6

The binary relation $x\le y$ on the natural numbers is not a Euclidean relation. Choose $x=1$, $y=3$, $z=2$. Then $1\le 3$ and $1\le 2$, but $3\nleqq 2$. Thus

The divisibility binary relation on positive natural numbers is not a Euclidean relation. With $x=1$, $y=2$, $z=3$, we have $1\mid 2$ and $1\mid 3$ but $2\nmid 3$. Therefore

Equality of remainders after division by eight is a Euclidean relation. If $x$, $y$ have the same remainder and $x$, $z$ have the same remainder, then $y$, $z$ have the same remainder. In the notation of modular arithmetic,Hence

Inequality on a domain containing at least two people is not a Euclidean relation. Choose distinct people $a,b$ and put $x=a$, $y=z=b$. Both premises $a\ne b$ hold, but the conclusion would be $b\ne b$. ThusThe possibility $y=z$ matters: the defining universal quantifiers do not require distinct arguments. On a domain with at most one element the inequality binary relation is empty and the condition holds by vacuous truth.

The “same age” binary relation is a Euclidean relation, with age understood as one consistently measured value at a fixed time. If $x$ has the same age as both $y$ and $z$, the ages of $y$ and $z$ are equal. HenceThis is another instance of equality of the values of a function inducing an equivalence relation.

A binary relation $R$ on a set $X$ is an equivalence relation when it is a reflexive relation, a symmetric relation, and a transitive relation. In first-order logic, these three requirements are

Suppose $R$ is an equivalence relation, and $xRy$, $xRz$. Since it is a symmetric relation, $yRx$. Since it is a transitive relation, $yRx$ together with $xRz$ implies $yRz$. This proves

Suppose $R$ is a reflexive relation and a Euclidean relation. To prove it is a symmetric relation, assume $xRy$. Reflexivity gives $xRx$, so applying the Euclidean implication to $xRy$ and $xRx$ gives $yRx$.

To prove it is a transitive relation, assume $xRy$ and $yRz$. The symmetry just established gives $yRx$. Apply the Euclidean implication with common predecessor $y$ to $yRx$ and $yRz$; the conclusion is $xRz$. Thus all three requirements hold:

On the nonempty set $X=\{a\}$ take the empty binary relation $R=\varnothing$. There are no triples for which $xRy\wedge xRz$ holds. The defining implication is therefore true for every triple by vacuous truth, making $R$ a Euclidean relation.

But $aRa$ is false, so $R$ is not a reflexive relation and hence is not an equivalence relation:

The answer is no, even when both original binary relations are equivalence relations. On $X=\{a,b,c\}$, let $R_1$ have equivalence classes $\{a,b\},\{c\}$ and $R_2$ have equivalence classes $\{a\},\{b,c\}$. Each is a transitive relation and, by the earlier proof, a Euclidean relation.

Use exactly the paper's convention for composition of relations: $xRy$ means $x{R}_{1}z$ and $z{R}_{2}y$ for some $z$. The possible successors areIndeed, from $a$ or $b$ the first step can reach $a$ or $b$, whose $R_2$ successors together exhaust $X$; from $c$ the first step must stay at $c$, whose $R_2$ successors are only $b,c$. Consequently $cRb$ and $bRa$, but not $cRa$. Therefore