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 - angličtina
Poslední úprava: 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.
Požadavky ke zkoušce -
Poslední úprava: 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.
Poslední úprava: 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.
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