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. 1 V 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

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/118876

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-415396


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce