We study spectra of first-order sentences. After providing some interesting examples of spectra we show that the class of spectra is closed under some simple set-theoretic and algebraic operations. We then define a new class of definable operations generalizing the earlier constructions. Our main result is that the class of these operations is, in a suitable technical sense, closed under a form of iteration. This in conjunction with Cobham’s characterisation of FP offers a new proof of Fagin’s theorem and also of the Jones-Selman characterisation of spectra as NE sets.
Introduction 1 Preliminaries 1.1 Logic 1.2 Cobham’s characterization of FP 2 Elementary results on spectra 2.1 Interesting examples of spectra 2.1.1 Spectra based on factors 2.1.2 Mutually orthogonal latin squares 2.2 Operations on spectra 2.2.1 Set operations on spectra 2.2.2 Arithmetical operations on spectra 3 \Sigma_1^1-definable functions 3.1 Basic notions 3.2 \Sigma_1^1-definability of FP 3.3 Fagin’s theorem 3.4 F\Sigma_1^1 operations on generalized spectra Concluding remarks
Number of pages: 36
