 Solution

ID: 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

x, y

, choose

z = max {x, y}

. Then

x, y \leq z

, and any

w

satisfying

x, y \leq w

also satisfies

z \leq w

. All three clauses of

ϕ

hold. Thus

N ⊨ ψ .

This explicitly supplies the witness required by the existential quantifier for every pair chosen by the two universal quantifiers.

 New to topics? Read the docs here!