PřF:M7152 Geom. Appl. of model theory

M7152 Geometric applications of model theory

Faculty of Science
Autumn 2016

Extent and Intensity

2/0. 2 credit(s) (příf plus uk k 1 zk 2 plus 1 > 4). Type of Completion: k (colloquium).

Teacher(s)

Guaranteed by

prof. RNDr. Jiří Rosický, DrSc.
Department of Mathematics and Statistics – Departments – Faculty of Science
Supplier department: Department of Mathematics and Statistics – Departments – Faculty of Science

Timetable

Mon 19. 9. to Sun 18. 12. Thu 16:00–17:50 M3,01023

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.

fields of study / plans the course is directly associated with

Algebra and Discrete Mathematics (programme PřF, N-MA)
Algebra, Number Theory and Mathematical Logic (programme PřF, D-MA4)
Geometry (programme PřF, N-MA)
Geometry, Topology and Global Analysis (programme PřF, D-MA4)

Course objectives (in Czech)

There are families of mathematical statements whose truth values can be determined algorithmically. The first such family was discovered by Tarski in the 1950's, and includes all of "elementary plane geometry". The theories of ordered division rings, algebraically closed fields and real closed fields are the most prominent examples, with decision algorithms that are implemented and improved to this day. This course investigates what it means to have decision algorithms for first order theories, and what are their practical uses and limitations. Notions of model theory, algebra and complexity theory will be recalled as needed. Time permitting, the course will end with a look at undecidability: why is it that there cannot exist algorithms for deciding the truth of all mathematical statements?

Syllabus (in Czech)

1) Review of first order logic; quantifier elimination; dense linear orders without endpoints. 2) Ordered division rings; Presburger arithmetic. 3) Algebraically closed fields; the Chevalley-Tarski theorem. 4) Weak Nullstellensatz; Rabinowitz’s trick; effective Nullstellensatz. 5) Reals and real closed fields; the Tarski-Seidenberg theorem. 6) Collins’s cylindrical algebraic decomposition. 7) Topology of semialgebraic sets: dimension; connected components; Euler characteristic; Betti numbers. 8) Term rewriting; Knuth–Bendix completion. 9) Grobner bases. 10) Introduction to complexity; upper and lower bounds. 11) Undecidability.

PřF:M7152 Geom. Appl. of model theory - Course Information

M7152 Geometric applications of model theory

Other applications