David Stanovský    //

MATEMATICKÁ LOGIKA 2018/19

Cílem předmětu je vysvětlit neúplnost (neexistenci "hezké" axiomatizace) a algoritmickou nerozhodnutelnost aritmetiky přiurozených čísel. Částečně navazuje se na předmět Úvod do matematické logiky: k porozumění je nutné znát základní syntaktické a sémantické vlastnosti predikátové logiky (logiky prvního řádu), což bude vysvětleno pouze stručně. Program: Logika 1. řádu: syntax a semantika, věta o úplnosti a její důsledky (kompaktnost, Löwenheim-Skolemova věta, Vaughtův test). Algoritmická vyčíslitelnost: Turingovy stroje a nerozhodnutelnost halting problému; rekurzivní funkce a reprezentovatelnost formulemi. (Ne)rozhodnutelnost a úplné axiomatizace: formulace problému, různé axiomatizace aritmetiky, Churchova věta o nerozhodnutelnosti (Gödelova o neúplnosti jako důsledek), informativně druhá Gödelova věta o nedokazatelnosti vlastní konzistence. Oproti předloňské verzi se bude přednáška hodně lišit, predikátovou logiku pouze zopakuji a soustředím se na nerozhodnutelnost a neúplnost.

	program přednášky	doporučená četba	domácí práce
2.10.	Motivace, historie, stručný obsah. Goodsteinovy posloupnosti.	Logicomix, Goodsteinovy posloupnosti na wikipedii	přečtěte si Logicomix
9.10.	Logika 1. řádu: termy, formule, struktury, definovatelné podmnožiny.	vdDries 2.3-2.6
16.10.	Logika 1. řádu: podstruktury, homomorfismy, faktorstruktury; semantický důsledek vs. syntaktický důsledek.	vdDries 2.3, 2.7	DOMÁCÍ ÚKOL, odevzdat 30.10.
23.10.	Logika 1. řádu: dvě formulace věty o úplnosti, konstrukce modelu.	vdDries 3.1, 3.2
30.10.	Logika 1. řádu: důkaz věty o úplnosti - kdy model funguje, zúplnění, svědci.	vdDries 3.1, 3.2	DOMÁCÍ ÚKOL, odevzdat 13.11.(opravena 5. úloha)
6.11.	--- děkanský den ---
13.11.	Logika 1. řádu: dokončení věty o úplnosti, Löwenheim-Skolemova věta.	vdDries 3.2, 4.1
20.11.	Vaughtův test úplnosti, věta o kompaktnosti. Eliminace kvatifikátorů (informativně).	vdDries 3.2, 4.1, 4.2, 4.3
27.11.	(Ne)rozhodnutelnost a úplné axiomatizace. Př.: algebraická geometrie, aritmetika Presburgerova, Robinsonova, Peanova.	vdDries 4.4, 5.1	DOMÁCÍ ÚKOL, odevzdat 11.12.
4.12.	Turingovy stroje.	wikipedia	DOMÁCÍ ÚKOL, odevzdat 8.1.
11.12.	Halting problem. Vyčíslitelné funkce a Church-Turingova teze. Rekurzivní funkce - úvod.	vdDries 5.1, 5.2
18.12.	Rekurzivní funkce - reprezentovatelnost formulemi, příklady, Gödelova beta funkce a rekurze.	vdDries 5.1, 5.4
8.1.	Gödelovo číslování. Gödelova věta o neúplnosti a Churchova věta o nerozhodnutelnosti aritmetiky.	vdDries 5.5, 5.6

V průběhu semestru budou zadávány domácí úkoly. Budou 4 série, počítají se 3 nejlepší. Zadání a jejich termíny se budou objevovat průběžně zde.
Z celkových 100 bodů ke zkoušce je možné získat 15 za domácí úkoly a 85 za závěrečný test (standardní termíny během zkouškového období).

Požadavky ke zkoušce (první předvánoční verze, po poslední přednášce bude aktualizováno).

Výsledky domácích úkolů

Literatura:

• Lou van den Dries: Lecture notes on mathematical logic - podle těchto skript půjde přednáška
• video k přednášce Úvod do matematické logiky v podání Jana Krajíčka
• Logicomix - motivace a historické pohnutky ke vzniku formální logiky
• zdroje v češtine:
  • V. Švejdar, Logika: neúplnost, složitost a nutnost, Academia, Praha, 2002.
  • A. Sochor: Klasická matematická logika, Karolinum, Praha, 2001.
  • B. Balcar a P. Štěpánek: Teorie množin, Academia, Praha, 1986.
• více o nerozhodnutelnosti a neúplnosti (nedokazatelnosti):
  • J.R. Shoenfield: Mathematical logic - klasická učebnice
  • E. Mendelson: Introduction to Mathematical Logic
  • H.D. Ebinghaus, J. Flum, W. Thomas: Mathematical Logic, Springer-Verlag 1984
• P. Pudlák, Logical Foundations of Mathematics and Computational Complexity, Springer, 2013 - alternativní přístup ke kurzu základů matematiky