### Ondřej Ježil

Faculty of Mathematics and Physics,

Charles University in Prague, 2020

## Spectrum Problem

### Abstract

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.

### Table of Contents

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