Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (23.12.2023)
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í.
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (23.12.2023)
Non-repeated universal elective course.
In 2023/24: Decidable theories.
We will study basic methods for proving algorithmic decidability of first-order theories and main examples of
decidable theories.
Podmínky zakončení předmětu - angličtina
Poslední úprava: Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D. (27.12.2023)
Oral exam.
Literatura -
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (23.12.2023)
Wilfrid Hodges: Model Theory, Cambridge University Press, 1993.
Michael O. Rabin: Decidable theories, in: Handbook of Mathematical Logic, 1977, pp. 595-629.
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (23.12.2023)
Wilfrid Hodges: Model Theory, Cambridge University Press, 1993.
Michael O. Rabin: Decidable theories, in: Handbook of Mathematical Logic, 1977, pp. 595-629.
Požadavky ke zkoušce -
Poslední úprava: Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D. (03.01.2024)
Ústní zkouška pro ověření znalosti hlavních výsledků představených na přednášce
Poslední úprava: Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D. (03.01.2024)
Oral exam to assess understanding of the main results presented during the course.
Sylabus -
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (23.12.2023)
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
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (23.12.2023)
We will study basic methods for proving algorithmic decidability of first-order theories and main examples of decidable theories.
Tools:
quantifier elimination
interpretations
Ehrenfeucht-Fraïssé games
Mostowski and Feferman-Vaught theorems
Fraïssé limits
Exhibits (depending on time constraints):
theories of abelian groups and modules
ordered abelian groups (divisible, Presburger arithmetic)
algebraically closed and real-closed fields
theories of linear orders
theories of Boolean algebras
theories of random structures
theories of locally free algebras
Skolem arithmetic
Vstupní požadavky -
Poslední úprava: Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D. (27.12.2023)
Základní znalost matematické logiky a teorie modelů
Poslední úprava: Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D. (27.12.2023)
Basic knowledge of mathematical logic and model theory