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 / b / Solution

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.