Paper 3, Section II, G

Logic and Set Theory | Part II, 2018

State and prove the Compactness Theorem for first-order predicate logic. State and prove the Upward Löwenheim-Skolem Theorem.

[You may assume the Completeness Theorem for first-order predicate logic.]

For each of the following theories, either give axioms (in the specified language) for the theory or prove that the theory is not axiomatisable.

(i) The theory of finite groups (in the language of groups).

(ii) The theory of groups in which every non-identity element has infinite order (in the language of groups).

(iii) The theory of total orders (in the language of posets).

(iv) The theory of well-orderings (in the language of posets).

If a theory is axiomatisable by a set SS of sentences, and also by a finite set TT of sentences, does it follow that the theory is axiomatisable by some finite subset of SS ? Justify your answer.

Typos? Please submit corrections to this page on GitHub.