Výběrová přednáška z MSTR 2 - NMAG499

• Anglický název: MSTR Elective 2
• Zajišťuje: Katedra algebry (32-KA)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• 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í
• Způsob výuky: prezenční
• Další informace: https://users.math.cas.cz/~jerabek/teaching/decidable.html
• Poznámka: předmět lze zapsat opakovaně
• Garant: 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

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

angličtina

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

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

Oral exam.

Literatura

čeština

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

čeština

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

angličtina

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

čeština

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

angličtina

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

čeština

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

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

angličtina

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

Basic knowledge of mathematical logic and model theory