Rozhodnutelné teorie - NMAG570

• Anglický název: Decidable theories
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: angličtina, čeština
• Způsob výuky: prezenční
• Další informace: https://users.math.cas.cz/~jerabek/teaching/decidable/decidable.html
• Poznámka: předmět lze zapsat opakovaně
• Garant: Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D.
• Vyučující: Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D.
• Třída: M Mgr. MSTR; M Mgr. MSTR > Volitelné
• Kategorizace předmětu: Matematika > Algebra

Anotace

čeština

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: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (05.06.2024)

angličtina

We will study basic methods for proving algorithmic decidability of first-order theories and main examples of decidable theories.

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (05.06.2024)

Podmínky zakončení předmětu

Oral exam.

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (05.06.2024)

Literatura

čeština

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.

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (05.06.2024)

Požadavky ke zkoušce

čeština

Ú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 hlavních tematických skupin dle svého výběru.

V roce 2023/24 byla na výběr následující témata, to se ale může změnit v závislosti na tom, co přesně letos probereme:

• 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.

• Ehrenfeucht–Fraïssého hry, graded back-and-forth systems. Presburgerova aritmetika.

• Teorie lineárních uspořádání.

• Feferman–Vaughtovy věty. Skolemova arithmetika.

Poslední úprava: Jeřábek Emil, Mgr. et Mgr., Dr., Ph.D. (05.02.2025)

angličtina

Oral exam to assess understanding of the main results presented during the course. Each student will present one of the main topic groups of their own choosing.

The list of possible topics in 2023/24 was as follows, but this is subject to change depending on what exactly we will cover in the course this year:

• Syntactic and semantic criteria for QE. Algebraically closed fields.

• Fraïssé limits. Either random graphs or atomless Boolean algebras.

• Ehrenfeucht–Fraïssé games, graded back-and-forth systems. Presburger arithmetic.

• The theory of linear orders.

• Feferman–Vaught theorems. Skolem arithmetic.

Poslední úprava: Jeřábek Emil, Mgr. et Mgr., Dr., Ph.D. (05.02.2025)

Sylabus

čeština

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

• Fraïssého limity

• Ehrenfeuchtovy–Fraïssého hry

• věty Fefermanova–Vaughtova typu

Příklady teorií (dle časových možností):

• 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 a lokálně volných algeber

• teorie abelovských grup a modulů

• uspořádané abelovské grupy (divizibilní, Presburgerova aritmetika)

• Skolemova aritmetika

Poslední úprava: Jeřábek Emil, Mgr. et Mgr., Dr., Ph.D. (06.02.2025)

angličtina

We will study basic methods for proving algorithmic decidability of first-order theories and main examples of decidable theories.

Tools:

• quantifier elimination

• interpretations

• Fraïssé limits

• Ehrenfeucht–Fraïssé games

• Feferman–Vaught-like theorems

Exhibits (depending on time constraints):

• algebraically closed and real-closed fields

• theories of linear orders

• theories of Boolean algebras

• theories of random structures and locally free algebras

• theories of abelian groups and modules

• ordered abelian groups (divisible, Presburger arithmetic)

• Skolem arithmetic

Poslední úprava: Jeřábek Emil, Mgr. et Mgr., Dr., Ph.D. (06.02.2025)

Vstupní požadavky

čeština

Základní znalost matematické logiky a teorie modelů

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (05.06.2024)

angličtina

Basic knowledge of mathematical logic and model theory

Poslední úprava: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (05.06.2024)