Last update: 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.
Last update: 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í.
Course completion requirements
Last update: Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D. (27.12.2023)
Oral exam.
Literature
Last update: Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D. (20.05.2024)
Wilfrid Hodges: Model Theory, Cambridge University Press, 1993.
Michael O. Rabin: Decidable theories, in: Handbook of Mathematical Logic (ed. Jon Barwise), 1977, §C.3, pp. 595–629.
Hans Läuchli, John Leonard: On the elementary theory of linear order, Fundamenta Mathematicae 59 (1966), no. 1, pp. 109–116.
Requirements to the exam -
Last update: Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D. (20.05.2024)
Oral exam to assess understanding of the main results presented during the course. Each student will present one of the following topic groups of their own choosing:
Syntactic and semantic criteria for QE. Algebraically closed fields.
Fraïssé limits. Either random graphs or atomless Boolean algebras.
Last update: Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D. (20.05.2024)
Ústní zkouška pro ověření znalosti hlavních výsledků představených na přednášce. Každý student si připraví jednu z následujících tematických skupin dle svého výběru:
Syntaktická a semantická kriteria pro QE. Algebraicky uzavřená tělěsa.
Fraïssého limity. Buď náhodné grafy nebo bezatomární Booleovské algebry.
Last update: 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
Last update: 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
Entry requirements -
Last update: Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D. (27.12.2023)
Basic knowledge of mathematical logic and model theory
Last update: Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D. (27.12.2023)
Základní znalost matematické logiky a teorie modelů