Course literature:Mathematical Logic: A Course with Exercises. Part II: Recursion Theory, Gödel's theorems,
Set theory, Model Theory, by R. Cori och D. Lascar,
Oxford University Press. Note that we use Part II in this course.
Also some notes, and parts of a little booklet, will be used,
which you can download below. (The notes about the completeness theorem are in Swedish,
but proofs of that theorem appear in most elementary logic books.)
The participants should have rehearsed the following prerequisites when the course starts:
(1) First-order logic (the notions of terms, formulas and sentences of this language),
(2) structures/models of first-order logic,
(3) Tarski's truth definition, i.e. what it means for a sentence of first-order logic
to be true in a (first-order) structure.
These points are treated in most introductory books about formal logic, such as
van Dalen's Logic and Structure,
Cori's and Lascar's Mathematical Logic, Part I,
or the course literature of Logik och bevisteknik I
(which is Language, Proof, and Logic by Barwise and Etchemendy),
but they are also covered in three of the notes (in Swedish) below.
Approximate plan for the lectures
The course contains 25 lectures (each time 2 x 45 minutes). The chapter references refer to
the course literature mentioned above.
(Lecture nr)
1-3: Introduction, the completeness and compactness theorems: Notes below (or, for English sources, see any basic book on logic
which treats the completeness theorem).
13-18: Set theory: ordinal numbers and cardinal numbers, and their basic arithmetic.
Chap. 7.1 - 7.4 (and/or notes below).
19-24: Model theory: basic notions and results,
L?wenheim-Skolem theorems, categoricity,
Ehrenfeucht-Fraisse games, finite axiomatizability, applications,
something about Lindstr?m's characterization of first-order logic,
and perhaps something more.
Chap. 8.1 - 8.2, Sections 2.4, 2.6, 2.7 of my notes/booklet about set theory and model theory (below),
and (possibly) something from Chap. 8.3 - 8.5.
25: Reserve time;
some influential "classical" problems and results within mathematical logic and its neighbours.
Notes (pdf) that can be downloaded
The first three links below lead to some notes that are essentially rehearsal, and covers
the definition of first-order formulas, first-order structures/models, Tarski's thruth definition,
and some examples and results regarding these notions (in Swedish).
The next three links cover the proof of the completeness theorem (in Swedish).
The proof can also be found in most introductory books about formal logic;
for instance van Dalen's book Logic and Structure or Cori's and Lascar's
Mathematical Logic, Part I.
Below are some notes about set theory and model theory. The part about set theory corresponds very closely to the
presentation in the course literature (and also to the presentation that I give on the lectures).
I will say more about the model theory part later.
Here I tell roughly what we have covered in the lectures so far.
2/9: Introduction, rehearsal of basic notions (see notes above, about
formulas, structures and Tarski's truth definition), and an
illustration of a soundness proof.
6/9, 9/9, 12/9: The completeness- and compactness theorems.
(covered by my notes above)
16/9, 20/9: Basics about recursive, and primitive recursive,
functions and relations. Chap. 5.1.1, 5.1.2. (and/or my notes,
where there are some mistakes - at least partly because I earlier
changed some things and forgot to consistently make other changes.
I didn't have time to scan in the corrected version yesterday,
but will do it soon.)
22/9: The formal theory of Peano arithmetic; representable functions and relations, and the representation theorem.
Chap. 6.1 - 6.2 (and/or my notes).
27/9: Gödel numbers (codes) for expressions; recursive and decidable theories.
Chap. 6.3. (and/or my notes, until and including Proposition 4.1)
30/9: Church's undecidability theorem and Gödel's incompleteness theorem.
Chap. 6.4 (and/or my notes).
4/10: Definition of partial recursive function, recursively enumerable relation,
and some basic results about them; the normal form theorem for partial recursive functions.
Chap. 5 (and/or my notes: results 5.0 - 5.6)
7/10: Indices of partial recursive functions,
s-m-n theorem, recursion theorem and fixed point theorem.
Chap. 5 (and/or my notes).
11/10: Characterizations of recursively enumerable relations, Rice's theorem,
examples of non-recursive sets/relations.
Chap. 5 (and/or my notes). This concludes the recursion theory part.
The next time, we start with set theory.
25/10, 27/10, 31/10: Russel's paradox; Zermelo-Fraenkel axioms of set theory;
well orderings and ordinals. Chap. 7.1, 7.2.1 - 7.2.2, 7.3.1 (and/or my notes)
2/11: Statements which are equivalent with the axiom of choice
(Zorn's lemma and the statement that every set can be well ordered);
the Cantor-Bernstein theorem. chap. 7.1-7.5 (and/or my notes)
7/11, 11/11: Cardinals, cardinalities, and cardinal arithmetic.
chap. 7.1-7.5. (and/or my notes)
14/11, 18/11: Basics of model theory; substructures, elementary substructures,
elementary equivalence, isomorphism, Tarski-Vaught test, Downward Löwenheim-Skolem
theorem, expansions, reducts, elementary embeddings.
Chap. 8.1-8.2, and/or chap. 2 in my notes until Lemma 2.14.
22/11, 25/11: Upward Lowenheim-Skolem theroem, categoricity, Vaught's theorem,
axiomatisability, amalgamation theorem. Chap. 8.1-8.2, Section 2.2 - 2.3 of my notes.
Examination
The examination consists of two parts:
1. Problems to be solved; they are found below.
2. An examination (written) on 14 December
(see
examination schedule for information about exact time and place) which focuses on the central
concepts and methods of the course.
You find detailed information concerning what you need to know
here.
Grading: For grade 3 one has to pass the written exam (point (2)) and solve all problems
of part (1) that are marked by '*'.
For grade 4 the requirements for grade 3 have to be met and in addition at least 50 percent of
the problems without '*' have to be solved; for grade 5 the requirements for grade 3 have to be met and in addition at least 75 percent of
the problems without '*' have to be solved.
Problems
Your solutions must be clearly written and complete; otherwise you will
have to rewrite them.
2. Incompleteness theorems and recursion theory:
the assignments are here. Deadline for the *-problems: Thursday 27 October (on the lecture unless you
send them by e-mail).
4. Model theory:
the assignments are here. Deadline for *-problems, as well as all other problems that you want to be
counted for your grade: 11 January.