 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/digital-systems-linear-algebra-introduction-to-formal-proof/8/e/solution

Two unary predicates suffice. Require all four unary predicate types to be inhabited:

\exists x (P (x) \land Q (x)) \land \exists x (P (x) \land \neg Q (x)) \land \exists x (\neg P (x) \land Q (x)) \land \exists x (\neg P (x) \land \neg Q (x)) .

There are no constants, no logical equality and no nonunary predicates. Any two of these conditions disagree on at least one predicate, so one domain element cannot witness both. Hence every satisfying first-order structure has at least four elements, by distinct witnesses from incompatible unary predicates. Conversely take domain

{a, b, c, d}

P = {a, b}

and

Q = {a, c}

: the four elements realize the four displayed unary predicate types, respectively. These element names describe the example; they are not constants in the first-order sentence.

 New to topics? Read the docs here!