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 / 8

In this first-order structure, $R(x,z)\wedge R(y,z)$ says $x\le z$ and $y\le z$. Thus $z$ is an upper bound of $x,y$. The universally quantified clause says that if $w$ is any other upper bound, then $z\le w$. Therefore $z$ is their least upper bound. In the usual total order on the natural numbers, this is their maximum:This describes a condition on the values assigned to the free variables $x,y,z$; $\varphi$ itself is not a closed first-order sentence.

Every pair of natural numbers has a maximum, itself a natural number. Given arbitrary $x,y$, choose $z=\max \{x,y\}$. Then $x,y\le z$, and any $w$ satisfying $x,y\le w$ also satisfies $z\le w$. All three clauses of $\varphi$ hold. ThusThis explicitly supplies the witness required by the existential quantifier for every pair chosen by the two universal quantifiers.

Here the direction of the divisibility relation matters: $R(x,z)$ means $z\mid x$. The first two clauses say that $z$ is a common divisor of $x,y$. The last clause says that every common divisor $w$ divides $z$. These are precisely the defining properties of the greatest common divisor. Choose $z=\gcd (x,y)$; thenHenceThis also holds if the natural numbers include zero: use $\gcd (x,0)=x$ and $\gcd (0,0)=0$. Every natural number divides zero, so for $x=y=z=0$ the last clause remains true. In the order obtained by reversing divisibility, the greatest common divisor is the least upper bound.

The first two clauses now require $x=2z$ and $y=2z$. Thus they already imply $x=y$. Choose, for example, $x=1,y=2$; no natural number $z$ can satisfy both equations. Consequently the existential quantifier fails for this pair, irrespective of the universally quantified final clause, andIn fact even $x=y=1$ fails, since $1=2z$ has no solution among the natural numbers.