Model theory lectures in Fall 2020
This page will contain slides (and other comments) used in my lectures during the Fall 2020 Model theory course.
Lecture 1 (29.IX.2020)
A review of first-order logic:
languages, terms, formulas, sentences, theories, structures, models, the Completeness and the Compactness thms, definable sets and functions.
Slides.
Relevant pages in Marker's book: 7-11, 14-18 and 33-34.
Errata:
- slide 4: three sets in the vocabulary are disjoint
- slide 5: constants are also terms
- slide 8: DLO has often ax's that there are no the greatest and the least elements - we shall add these later on
Lecture 2 (6.X.2020)
Relations among structures, applications of the compactness:
substructures, preservation thms, elementary substructures, embeddings and isomorphisms, elementary equivalence, non-standard models of N and R, the Lowenheim-Skolem thm up, categoricity.
Slides.
Pages in Marker's book: 11-14, 39-40, 44-45, 66, 155, 207.
Errata:
- slide 4/ the 1st object in the 2nd example is not even a structure (not closed under +): delete + in both structures
- slide 10/3rd line from bottom: h(a_1)
- slide 12/the corollary does not need to mention map h at all
- slide 15/def. of T: word epsilon ought to be symbol \epsilon
- slide 19/ delete max in max \kappa
Lecture 3 (13.X.2020)
Back-and-forth, Ehrenfeucht-Fraisse games:
diagram of a structure, Cantor's thm, theory DLO, theory RG of the countable random graph, countable categoricity of DLO and RG.
Determinacy of games and axiom of determinacy.
Slides.
Pages in Marker's book: 44, 48-57.
Comments:
- on the last slide in Lect.2: an upper bound to the number of countable models
Errata/addendum:
- slides 4-5: add an observation that if we include among the conjuncts in \theta also \forall z (z\neq x \wedge z \neq y) then \theta characterizes $\mathbf A$ up to iso.
- slide 17: b_2 cannot be 1 (it is not there) but any element of (0,1) right to b_1 works as well
- slide 20: fla \alpha is open
- slide 28: spelling (3rd line: winning, lines 8 and 14: wins)
- slide 29: this discussion concerns general games played with moves taken from N and where any set of sequences from N may define winning positions for Duplicator
Lecture 4 (20.X.2020)
Uncountable categoricity: Th(Z,suc), vector spaces over Q, algebraically closed fields.
Complete theories and Vaught's test (its formulation, a proof next time). Important examples: RG and ACF_p.
Some additional remarks on AD - ax. of determinacy.
Slides.
Pages in Marker's book: 17-18, 41-42, 46
Errata/addendum:
- slide 10: sux(y) in the middle ought to be suc(x)
- slide 17: "0 and + form ..." should replace "0 and = form ..."
An example of a theory which is complete but not categorical in any power is given in Exercise 2.5.28 (parts a and b) o p.66 of Marker's book.
Lecture 5 (27.X.2020)
From completeness to decidability for recursively axiomatized theories.
Vaught's test and its proof from the Lowenheim-Skolem theorem.
Applications of compactness to RG (0-1 law for finite graphs) and to ACF_0 (the Ax-Grothendieck thm about polynomial maps on the complex field).
Slides.
Pages in Marker's book: 42-43, 51-52
Errata:
- slide 23: the notation W(\varphi) ought to depend also on n
- slide 24/center: there are 2^{n \choose 2} different outcomes, not just {n \choose 2}
Lecture 6 (3.XI.2020)
Skolemization and the proof of full Lowenheim-Skolem theorem.
Slides
Pages in Marker's book: 45-46
Errata:
- slide 19: the arrow represents map g (the caption "g" is missing)
Lecture 7 (10.XI.2020)
Quantifier elimination.
Non-examples (theories of the semiring of natural numbers, of the ring of integers and of the field of rationals), simple examples: DLO and RG, a reduction to primitive formulas, a sufficient model-theoretic condition, QE for ACF, definable sets in ACF
Slides.
Pages in Marker's book: 71-75, 184-188
Errata/addendum:
- slide 7/Def. of QE: the q-free fla has the same free variables as the original fla. If there are none (i.e. it is a sentence) then either (i) L contains a constant in which case the q-free fla is a q-free sentence, (ii) or not, in which case think that it has a free variable x_1.
- slide 7: atomic sentences over the non-example structures are algorithmically decidable a hence are also q-free sentences. But there are definable sets in all three non-ex's with algorithmically undecidable membership. Keywords: Halting problem, Hilbert's 10th problem.
- slide 12: \overline b in the last line of the proof ought to be \overline a.
- slide 18: last item should say that x_1 = x_1 replaces all flas with y but other flas (with x's only) remain in \psi_1
- slide 19: the thm can be formulated as follows (and that is what we prove): For any fla \varphi, if the situation ..., then \varphi is T-equivalent to a q-free fla. In fact, this is how we use it in Corollary on slide 21.
- slide 21: the fla \psi on the last line misses arguments \overline a
- slide 23: \neg Sigma on the last but one line ought to be \neg Sigma_0 for some finite part of \Sigma (by compactness). Hence the disjuction is one of the flas \alpha that get into \Gamma.
- slide 24: last but 1 line: ought to be ""the conjunction" instead of "the disjunction"
- slide 26: D is a semi-ring, which defines unique ring, etc.
Lecture 8 (24.XI.2020)
QE continued.
Completeness of $ACF_p$ from the QE for ACF, definable sets in ACF and strong minimality, algebraic geometry and Chevalley's theorem, combinatorial pregeometries, theory RCF and QE, the Tarski-Seidenberg thm, o-minimality, definable sets and cell decomposition.
Slides.
Pages in Marker's book: 30 (1.4.11), 85-88, 93-99, 102-104
Errata:
- slide 11/3rd line in the def. of acl: the parameters \overline a ought to be from U^n
- slide 14/1st line: 'filed' ought to be 'field'
- slide 23: second (1) ought to be (3)
Lecture 9 (1.XII.2020)
Ultraproduct.
Filters and ultrafilters, ultraproduct, Los's theorem, ultrapower constructions of non-standard models of N and R. The compactness theorem via ultraproduct. Ex's: ultraproduct of finite fields, of cyclic graphs, ... .
Slides.
Pages in Marker's book: 63-65
Errata:
- slide 11: I in the 3rd example is just N
- slide 18: bracket } is missing at the end of the bottom formula
- slide 21/Lemma: alphas and betas in the first fla ought to be in [...]
- slide 23: black A_i^* in the superscripts should be just A_i and := \beta ought to be := [\beta]
- slide 28/line 2: \eta([\alpha]) and \beta exists by AC
- slide 29: A ought to be infinite and the symbol between A and A^* should be strict elem.extension (i.e. the \not should cross only the equality, not the whole symbol)
- slides 31 and 33: both use non-principal ultrafilter
- slide 34/bottom line: the whole
Lecture 10 (8.XII.2020)
Types.
Partial and complete types, Stone space, types realized and omitted, characterization of complete types via elem.extensions.
Ex's: complete types in models of DLO, ACF and in the real closed ordered field.
Saturated structures and their properties.
Slides.
Pages in Marker's book: 115-117, 119, 121-124, 133, 138, 143-145
(other parts of Secs.4.1 and 4.3 add more examples to the material from the lecture)
Errata/addendum:
- slide 11/Ex.3: the complete type k < x < k+1 from Ex.2 is not present here
- slides 13 and 14/ M' is L_A-elementary ext. of M, i.e. the symbols \succeq (slide 13) and \preceq (slide) should have index A
- slide 21; "transfinite induction" means that if for some ordinal \lambda and some property P:
P holds for 0,
if P holds for \beta < \lambda then P holds for \beta+1 too,
if P holds for all \alpha < limit \beta < \lambda then P holds for \beta too,
then P holds for all \beta < \lambda.
- slide 24: Monster model is analogous to an extent to "Grothendieck universe" in algebraic geometry (a set closed under several set-th. operations) whose existence is equivalent to the existence of an inaccessible cardinal.
- An additional nice property of saturated structures concerns the possibility to characterize definability in terms of the automorphism group (pp.146-147).
Lecture 11 (15.XII.2020)
Types cont'd.
The existence of saturated structures. Isolated types and the omitting types thm. Peano arithemtic. The MacDowell-Specker thm via omitting types and via ultrapower.
Slides.
Pages in Marker's book: 125-128, 139-142, 168 (4.5.37)
Errata/addendum:
- slide 3: n+1 instead of n=1
- slide 6: we want to arrange also that D_{k+1} is a *proper* subset of D_k, e.g. remove one element (that is OK because U is non-principal)
- slide 10, the last line ought to be phrased as "there is a model of T that realizes all flas in p"
- slide 22, last line: \alpha = \beta
Lecture 12 (5.I.2021)
An overview of the course and of the exam problems.
Auxiliary topics in model theory.
Slides.