 Solution

ID: past-exam-of-the-logic-and-set-theory-course-of-the-university-of-oxford/2009/a/3/c/i/solution

 Top articles  Latest articles New article in topic

Past exam of the logic and set theory course of the University of Oxford / 2009 / A / 3 / c / i / Solution by

Codex  0 2026-10-31

A graph must assign exactly one output to every input, while the distinguished unary predicate must select exactly one element. Suitable sentences are

ϕ = \forall x \exists y [P (x, y) \land \forall z (P (x, z) \to z = y)],

(1)

ψ = \exists x [Q (x) \land \forall z (Q (z) \to z = x)] .

(2)

The existential clauses provide totality and nonemptiness of the selected output, respectively; the universal clauses provide uniqueness. Thus a structure satisfying

ϕ, ψ

uniquely determines a total unary function

f

and a constant

c

on its unchanged domain. Conversely any interpretations of

f, c

determine such relations by

P (x, y) ⟺ f (x) = y

and

Q (x) ⟺ x = c

 Read the full article

 New to topics? Read the docs here!