Sylabus
Úplnost — Syntax a semantika predikátové logiky (opakování), úplnost, kompaktnost, Löwenheim–Skolemovy věty, Vaughtův test, nestandardní modely
Vyčíslitelnost — Turingovy stroje, vyčíslitelné funkce, univerzální Turingův stroj, nerozhodnutelnost halting problemu
Nerozhodnutelnost a neúplnost — Peanova aritmetika PA, Gödelova a Churchova věta o neúplnosti a nerozhodnutelnosti aritmetiky, formalizace syntaxe v PA
Viz též https://users.math.cas.cz/~jerabek/teaching/mathlog.html a https://www.karlin.mff.cuni.cz/~krajicek/mll.html
Anotace
Pokročilejší přednáška o matematické logice. Stručně zopakuje základní pojmy a konstrukce. Hlavním tématem přednášky je neúplnost a nerozhodnutelnost, zejména Gödelovy věty.
Určeno pro zaměření Matematická analýza a Matematické struktury na OM.