Subjects

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

MSTR Elective 2 - NMAG499

Title:	Výběrová přednáška z MSTR 2
Guaranteed by:	Department of Algebra (32-KA)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2023
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
Teaching methods:	full-time
Additional information:	https://users.math.cas.cz/~jerabek/teaching/decidable.html
Note:	you can enroll for the course repeatedly

Guarantor:	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 -

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.

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.

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

The theory of linear orders.

Feferman–Vaught theorems. Skolem arithmetic.

Syllabus -

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

Entry requirements -

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

Basic knowledge of mathematical logic and model theory