Original title:
Problém spektra
Translated title:
Spectrum problem
Authors:
Ježil, Ondřej ; Krajíček, Jan (advisor) ; Šaroch, Jan (referee) Document type: Bachelor's theses
Year:
2020
Language:
eng Abstract:
[eng][cze] 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. 1V této práci se věnujeme spektrům sentencí prvního řádu. Nejprve předvedeme kon- strukci několika zajímavých příkladů spekter a poté ukážeme, že je třída všech spekter uzavřena na několik jednoduchých množinových a algebraických operací. Poté definu- jeme novou třídu definovatelných operací, která zobecní předchozí konstrukce. Hlavním výsledkem práce je důkaz toho, že je třída těchto funkcí uzavřena na určitý druh iterace. Toto nám ve spojení s Cobhamovou charakterizací FP nabízí nový důkaz Faginovy věty a také Jonesovy-Selmenovy charakterizace spekter jako NE množin. 1
Keywords:
Asser's problem; Cobham's theorem; generalized spectrum; Scholz's problem; spectrum; Asserův problém; Cobhamova věta; Scholzův problém; spektrum; zobecněné spektrum
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/118876