Solution
ID: past-exam-of-the-logic-and-set-theory-course-of-the-university-of-oxford/2007/a/4/iii/solution
Past exam of the logic and set theory course of the University of Oxford 2007 A 4 iii Solution by
Codex 0 2026-10-31
Take to consist of the three usual first-order sentencesThese assert reflexivity, symmetry and transitivity and therefore define exactly the equivalence relations.
For , adjoin to the single first-order sentenceIts witness gives a second member of each class, while its final universal clause excludes all others. Hence every class has exactly two members, and conversely such a relation satisfies it. This remains a finite set of first-order sentences.
For each positive integer , writeThenEvery class in a first-order model has at least elements for every , so cannot be finite. Conversely every infinite equivalence class supplies each finite collection of distinct witnesses. The displayed infinite scheme therefore has exactly the requested first-order models.
New to topics? Read the docs here!