Completeness and Definability
Kees Doets

Abstract:
Completeness and Definability
Applications of the Ehrenfeucht game in second-order and intensional logic
Kees Doets

This dissertation contains results on classical first- and second-order logic (parts I and II) and their intensional colleagues: modal- tense- and intuitionistic (propositional) logic (part III).
One underlying theme is Ehrenfeucht's game and some of its variants
Chapter 1 is an Introduction to Ehrenfeucht game theorg and its relation with (quantifierrank-) \alpha-equivalence in (infinitary) logic. Section 1.0 intends to whet the appetite for the finite Ehrenfeucht game.
In chapter 2 the game is played on binary trees. A characterisation is obtained of all trees n-equivalent with the binary tree B+m, all of whose branches have length m. In particular, it follows that B_m has _infinite_ n-equivalents when m>=2^n-1. This has been applied by Rodenburg [1986] to solve a problem in intuitionistic correspondence theory; the story is told in chapter 8.
Part II shows how to axiomatize certain monadic \Pi^1_1-theories, most of them dealing with wellfoundedness. Chapter3 is on linear orderings. One of the nicer results is in 3.3 where the effects of the Suslin propertg for the monadic \Pi^1_1-theory of H are isolated. Chapter 4 generalizes the method of 3 to the case of trees.
In part III, chapter 5 discusses Löwenheim-Skolem type problems in modal correspondence theory. It is shown that most examples of non-first-order definable modal formulas already cannot be first-order defined on _finite_ frames. On the other hand, an example is given of a non-first-order definable formula which _is_ first-order definable on all countable frames.
Chapter 6 modifies the Ehrenfeucht game for use in intensional logic; exact Kripke models are constructed universal with respect to finite partially ordered Kripke models.

Chapter 7 presents our version of Z-completeness.
In chapter 9, games and the universal-exact Kripke model appropriate for one-variable intuitionistic formulas are applied to solve some problems in intuitionistic correspondence theory left open by Rodenburg [1952].
Appendix A constructs asymmetric linear orderings with lots of homogeneity-properties in each uncountable cardinal.
Appendix B reduces all of higher-order logic to monadic second-order logic - indicating the expressive possibilities of modal logic in the Kripke semantics.

To help the reader find his way, here is an indication what can be omitted without loss of understanding of the rest. In chapter 1, sections 4, 8 and 9 are not needed for the other chapters. Also, not much will be lost if, in the discussion of the \alpha-game, the reader always assumes \alpha to be _finite_. Section 2.4 can be read independently from the rest of chapter 2. Section 3.2 may be omitted. In part III, all chapters can be read individually (except for a couple of references where this is indicated.)

I am obliged to several people for different reasons; in particular I wish to thank here prof. Specker for a lecture featuring Ehrenfeucht games; Piet Rodenburg for the communication of his problems to which chapters 2/8/9 are devoted and the elimination of numerous mistakes in a previous version of this text; Anne Troelstra and Dick de Jongh for scientific support and the software used to produce this text on the Macintosh Plus.
However, above all, my gratitude concerns my thesis-advisor Johan van Benthem whose determination and persuasiveness eventually turned out to be irresistible.