Consider the following first order formula (the conjunction of the four clauses): (forall x exists y: R(x,y)) AND (forall x forall y: (R(x,y) -> ~R(y,x))) AND (forall x forall y forall z: (R(x,y) AND R(y,z) -> R(x,z))) AND (forall x: ~R(x,x)). Does it have finite models? Is it satisfiable? If so, give a countable model for it.
GATE 1991 · Discrete Mathematics · First Order Logic · medium
Answer: No finite model exists; the formula is satisfiable; the natural numbers (N, <) form a countable model.
Identify the relational properties: Clause 1 = serial, clause 2 = asymmetric, clause 3 = transitive, clause 4 = irreflexive. So R is a serial strict partial order.
No finite model: In a finite domain start at x0; seriality gives x0 R x1 R x2 R ... Since the domain is finite, some element repeats, and transitivity yields a R a for that element, contradicting irreflexivity. Hence no finite model.
Exhibit a countable model: On (N, <): every n has successor n+1 (serial); n<m forbids m<n (asymmetric); < is transitive; never n<n (irreflexive). All four clauses hold.