Monadic NP sets

• Název práce v češtině: Monadické NP množiny
• Název v anglickém jazyce: Monadic NP sets
• Klíčová slova: spektrum|zobecněné spektrum|Asserův problém|existenční druhořádová logika|Ehrenfeucht-Fraïssého hry|monadické NP|Fagin-Hájkova věta
• Klíčová slova anglicky: spectrum|generalised spectrum|Asser's problem|existential second-order logic|Ehrenfeucht-Fraïssé games|monadic NP|Fagin-Hájek theorem
• Akademický rok vypsání: 2022/2023
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra logiky (21-KLOG)
• Vedoucí / školitel: prof. RNDr. Jan Krajíček, DrSc.
• Řešitel: Martin Putzer - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 11.10.2022
• Datum zadání: 11.10.2022
• Schválení administrátorem: bylo schváleno
• Datum potvrzení stud. oddělením: 17.12.2022
• Datum a čas obhajoby: 16.06.2023 09:00
• Datum odevzdání elektronické podoby: 09.05.2023
• Datum proběhlé obhajoby: 16.06.2023
• Odevzdaná/finalizovaná: odevzdaná studentem a finalizovaná
• Oponenti: doc. Mgr. Radek Honzík, Ph.D.

Zásady pro vypracování

Nastudovat a prezentovat důkaz věty (Fagin a Hájek), že monadické NP množiny (t.j. množiny definované monadickou Sigma-1-1 sentencí) nejsou uzavřeny na doplněk.

Learn and present some proof of the Fagin-Hajek theorem that monadic NP sets (i.e. sets definable by a monadic Sigma-1-1 sentence) are not closed under complementation.

Seznam odborné literatury

A. Durand, N.D. Jones, J.A. Makowsky and M. More,
Fifty Years of the Spectrum Problem: Survey and New Results,
preprint (submitted to the Bulletin of Symbolic Logic), 2009
http://www.diku.dk/hjemmesider/ansatte/neil/SpectraSubmitted.pdf

Hajek, P. (1975), On logics of discovery, in “Proceedings, 4th
Conference on Mathematical Foundations of Computer
Science, Lecture Notes in Computer Science 32,” pp. 3 W 5 ,
Springer-Verlag, Berlin.


Fagin, R. (1975), Monadic generalized spectra, Zeitschrqt f i r
Mathematische Logik und Grundlagen akr Mathematik 21,89-96.