 Solution

ID: 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/8/b/solution

Let

A

{a}

with

R (a, a)

. Taking

x = a

witnesses the existential quantifier, and the only

y

is comparable with

a

. Thus

A ⊨ φ

Let

B

be the two-element antichain

{a, b}

, with

R

consisting only of

(a, a)

and

(b, b)

x = a

, choose

y = b

, and if

x = b

, choose

y = a

. In either case both

R (x, y)

and

R (y, x)

are false. Therefore no witness for the existential quantifier exists:

A = ({a}, =) ⊨ φ, B = ({a, b}, =) \neq ⊨ φ .

 New to topics? Read the docs here!