Název:
Problém spektra
Překlad názvu:
Spectrum problem
Autoři:
Ježil, Ondřej ; Krajíček, Jan (vedoucí práce) ; Šaroch, Jan (oponent) Typ dokumentu: Bakalářské práce
Rok:
2020
Jazyk:
eng
Abstrakt: [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
Klíčová slova:
Asserův problém; Cobhamova věta; Scholzův problém; spektrum; zobecněné spektrum; Asser's problem; Cobham's theorem; generalized spectrum; Scholz's problem; spectrum