Descriptive Set Theory and Infinitary Languages

John P. Burgess

Kurepa trees, partitions, lensen's principles, large cardinals, and other notions from combinatorial set theory play an enormous role in the model theory of generalized-quantifier languages. (See e.g. [29].) Borel and analytic sets, Polish group actions, and notions from descriptive set theory can play almost as large a role in the model theory of certain infinitary languages. (See [31] and [32].) The present paper is a study, by the methods of descriptive set theory, of the class of strong first-order languages. These, roughly, are the infinitary languages which are strong enough to express wellfoundedness, at least over countable structures, yet weak enough that the satisfaction relation is AI-definable. Examples, culled from the literature of exotic model theory, are present in § 1. The set- theoretic machinery for their study is set up in §§ 2-4. §§ 5 and 6 are devoted to an exposition of the properties shared by all strong first-order languages. Most notably: There is a quasiconstructive complete proof procedure involving rules with $N_1$ premisses for any strong first-order language, and even the weak version of Beth's Definability Theorem fails for every such language. Many of the results in this paper date from the author's days as a student in R.L. Vaught's seminar at Berkeley, 1972-73. At that time I had the benefit of correspondence with Profs. Barwise and Moschovakis, and especially of frequent discussions with Prof. Vaught and D. E. Miller. Most of this work was included in [6], and a few items have appeared in print ([5]; [8], § 2). More recent discussions with Miller led to the discovery of the proof procedure and the counterexample to Beth's Theorem alluded to above, and to the writing of this paper.