Sylabus
Seznámíme se se základními metodami pro důkaz algoritmické rozhodnutelnosti teorií prvního řádu a nejdůležitějšími konkrétními příklady rozhodnutelných teorií.
Nástroje:
- eliminace kvantifikátorů
- interpretace
- Ehrenfeuchtovy-Fraïssého hry
- Mostowského a Fefermanova-Vaughtova věta
- Fraïssého limity
Příklady teorií (dle časových možností):
- teorie abelovských grup a modulů
- uspořádané abelovské grupy (divizibilní, Presburgerova aritmetika)
- algebraicky uzavřená a reálně uzavřená tělesa
- teorie lineárních uspořádání
- teorie Booleových algeber
- teorie náhodných struktur
- teorie lokálně volných algeber
- Skolemova aritmetika
Anotace
Jednorázová výběrová přednáška na různá témata.
V 2023/24: Rozhodnutelné teorie.
Seznámíme se se základními metodami pro důkaz algoritmické rozhodnutelnosti teorií prvního řádu a nejdůležitějšími konkrétními příklady rozhodnutelných teorií.