Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Decidable theories - NMAG570

Title:	Rozhodnutelné teorie
Guaranteed by:	Department of Algebra (32-KA)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2024
Semester:	summer
E-Credits:	3
Hours per week, examination:	summer s.:2/0, Ex [HT]
Capacity:	unlimited
Min. number of students:	unlimited
4EU+:	no
Virtual mobility / capacity:	no
State of the course:	taught
Language:	English, Czech
Teaching methods:	full-time
Additional information:	https://users.math.cas.cz/~jerabek/teaching/decidable/decidable.html
Note:	you can enroll for the course repeatedly

Guarantor:	Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D.
Teacher(s):	Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D.
Class:	M Mgr. MSTR M Mgr. MSTR > Volitelné
Classification:	Mathematics > Algebra

Opinion survey results Examination dates SS schedule Noticeboard

Annotation -

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

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (05.06.2024)

Course completion requirements

Oral exam.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (05.06.2024)

Literature -

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.

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (05.06.2024)

Requirements to the exam -

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.

Last update: Jeřábek Emil, Mgr. et Mgr., Dr., Ph.D. (05.02.2025)

Syllabus -

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

Last update: Jeřábek Emil, Mgr. et Mgr., Dr., Ph.D. (06.02.2025)

Entry requirements -

Basic knowledge of mathematical logic and model theory

Last update: Žemlička Jan, doc. Mgr. et Mgr., Ph.D. (05.06.2024)