(in Polish) Logika matematyczna II

elective monographs

Knowledge of logic and set theory at the level of the courses "Mathematical Logic" and "Introduction to Mathematics". Some familiarity with algebra (e.g. algebraically closed fields) and set theory (e.g. ordinals and cardinals) will be useful, but not strictly required.

The course will cover selected topics in logic that go beyond the standard undergraduate course, in particular the basic concepts of model theory and theorems concerning unprovability in axiomatic systems. Topics will include, among other things: quantifier elimination and its applications to algebra, o-minimal structures, ω-categoricity, basic information about uncountable categoricity, and the limitative results of Tarski, Gödel, and Paris-Harrington (and possibly also Matiyasevich).

The course will consist of two parts. The selection of more advanced material will partly depend on the interests of participants.

I. Elements of model theory

1. Quantifier elimination and its typical consequences.

2. Classical examples of quantifier elimination: Presburger Arithmetic, algebraically closed fields, real closed ordered fields. Algebraic applications of quantifier elimination: the Ax-Grothendieck Theorem, Hilbert's Nullstellensatz, Hilbert's 17th Problem. Information on o-minimal structures and their properties.

3. Realizing and omitting types. Prime, atomic, and saturated models. Characterization of ω-categorical theories.

4. Depending on time and interests of participants: Morley's result on the number of countable models or Morley's Theorem on categoricity in uncountable cardinalities.

II. Limitative theorems

1. Theories interpreting arithmetic. Coding sequences and representation of computable functions. Universal formulas.

2. Tarski's Theorem on the undefinability of truth. Gödel's Incompleteness Theorems. Nonstandard models of arithmetic and Tennenbaum's Theorem.

3. The Paris-Harrington Theorem.

4. Depending on time and interests of participants: Matiyasevich's Theorem (the undecidability of Hilbert's 10th Problem).

1. Z. Adamowicz, P. Zbierski. The Logic of Mathematics. Wiley 1997.

2. D. Marker. Model Theory: an Introduction. Springer 2002.

3. W. Hodges. A shorter model theory. Cambridge 1997.

4. K. Tent, M. Ziegler. A Course in Model Theory. Cambridge 2012.

5. R. Kaye. Models of Peano Arithmetic. Oxford 1991.

The student:

1. understands the method of quantifier elimination and is familiar with classical examples of its application. Knows how to use quantifier elimination to prove selected results in algebra.

2. is familiar with the basic notions of classical model theory, including notions related to realizing and omitting types. Knows the characterization of countably categorical countable theories and is able to prove it. Knows the statement of Morley's Theorem on uncountable categoricity.

3. knows the definition of Peano Arithmetic and its typical subtheories. Understands the idea of coding finite sequences, computations, and other discrete objects in arithmetic.

4. knows the statements of the classical limitiative theorems of Tarski, Gödel, and Tennenbaum. Knows how to prove these theorems. Knows the statement of the Paris-Harrington Theorem and the idea of its proof.

5. knows the statement of Matiyasevich's Theorem and understands its significance.

Exam.