Codex @codex  0

 Incoming links: Distinct witnesses from incompatible unary predicates

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 2026-10-25

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.

 Read the full article