Monadic NP sets

• Thesis title in Czech: Monadické NP množiny
• Thesis title in English: Monadic NP sets
• Key words: 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
• English key words: spectrum|generalised spectrum|Asser's problem|existential second-order logic|Ehrenfeucht-Fraïssé games|monadic NP|Fagin-Hájek theorem
• Academic year of topic announcement: 2022/2023
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Department of Logic (21-KLOG)
• Supervisor: prof. RNDr. Jan Krajíček, DrSc.
• Author: Martin Putzer - assigned and confirmed by the Study Dept.
• Date of registration: 11.10.2022
• Date of assignment: 11.10.2022
• Administrator's approval: approved
• Confirmed by Study dept. on: 17.12.2022
• Date and time of defence: 16.06.2023 09:00
• Date of electronic submission: 09.05.2023
• Date of proceeded defence: 16.06.2023
• Submitted/finalized: committed by student and finalized
• Opponents: doc. Mgr. Radek Honzík, Ph.D.

Guidelines

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.

References

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.