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

In first-order logic with equality, the three first-order sentences areA reflexive relation relates each element to itself. An antisymmetric relation forbids distinct elements from relating in both directions. A transitive relation contains every composite of two successive related pairs. Together these axioms define a partially ordered set.

The requested examples are binary relations on sets, rather than partially ordered sets: a partially ordered set necessarily has all three properties. This corrects the wording of the source.^[ref]

For an antisymmetric relation and transitive relation that is not a reflexive relation, take $S=\{0,1\}$ and $R=\{(0,1)\}$. No distinct pair relates both ways, so the antisymmetric relation condition holds. There are no composable pairs, so the transitive relation condition holds vacuously. Neither $(0,0)$ nor $(1,1)$ belongs to $R$, so the reflexive relation condition fails.

For a reflexive relation and transitive relation that is not an antisymmetric relation, take $S=\{0,1\}$ and $R=S\times S$. All diagonal pairs and all composite pairs belong to $R$, but $R(0,1)$ and $R(1,0)$ both hold with $0\ne 1$.

For a reflexive relation and antisymmetric relation that is not a transitive relation, takeAll diagonal pairs are present, and no off-diagonal pair has its reverse present. However $R(0,1)$ and $R(1,2)$ hold while $R(0,2)$ fails. Thus each pair of axioms can hold without the third.

Totality of the binary relation is expressed byWhen $R$ is already an order, this adds comparability and makes it a total order. In fact this first-order sentence alone entails $\rho =\forall xR(x,x)$.

By the definition of semantic entailment, $\tau \models \rho$ means that every first-order structure satisfying $\tau$ also satisfies $\rho$. Let $\mathcal{M}$ be any such first-order structure, and let $a$ be any element of its domain of a first-order structure. The instance of $\tau$ with $x=y=a$ gives $R(a,a)\vee R(a,a)$, which is true only if $R(a,a)$ is true. Since $a$ was arbitrary, $\mathcal{M}\models \forall xR(x,x)$. ThereforeThere is no exception for $x=y$ in the displayed totality axiom; that case is exactly what forces the reflexive relation property.