Logik II
    UPPSALA UNIVERSITET
    Matematiska institutionen
    Vera Koponen

    Logik II, ht 2009

    General information / Allmän information

    • Lecturer: Vera Koponen, vera@math.uu.se, 018-471 31 85, Ångströmlaboratoriet, rum 14234.
    • Course literature: Mathematical Logic: A Course with Exercises. Part II: Recursion Theory, Gödel's theorems, Set theory, Model Theory, av 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.)
    • You can find your schedule on the internet: http://www.teknat.uu.se/student/schema/
    • Information om hur examinationen går till finns längre ner på sidan.
    • Formell kursplan.
    • Lite information om logik och logikkurser vid matematiska institutionen finns här.
    • Wikipedias artikel om matematisk logik.

    Copies of some notes/ stenciler

    The first three links below lead to some notes (pdf-files) 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.
    • Formler och strukturer (10 sidor).
    • Tarskis sanningsdefinition (8 sidor).
    • Mera om sanning i strukturer (13 sidor).
    The next three links (also pdf-files) cover the proof of the completeness theorem (in Swedish).
    • The completeness theorem (in Swedish), pages 1-8.
    • The completeness theorem (in Swedish), pages 9-18.
    • The completeness and compactness theorems, with some applications (in Swedish), pages 19-39.
    Lecture notes from 3rd - 8th lectures:
    • Basics about recursive functions.
    • More basics about recursive functions.
    • Formal arithmetic.
    • Representability.
    • Coding (Gödel numbers), (un)decidability and (in)completeness.
    • Partial recursive functions, recursively enumerable relations (and sets), the normal form theorem, the s-m-n-theorem.
    • Recursion theorem, fixed point theorem, Rice's theorem, stop problem and some more about recursively enumerable relations.
    • Some problems in recursion theory, with solutions.
    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.
    • Notes on set theory and model theory.

    Förberedelser

    När föreläsningarna börjar förväntas kursens deltagare ha repeterat följande saker, som är förkunskaper:
    (1) Första ordningens logik (dvs. vad som är formler i detta språk),
    (2) strukturer/modeller för första ordningens logik,
    (3) Tarskis sanningsdefinition, dvs. vad det innebär för en formel (utan fria variabler) att vara sann i en struktur/modell.
    Dessa tre punkter behandlas i kurslitteraturen för Logik och bevisteknik I, men ni kan också läsa om dem i tre (sammanhängande) stenciler som finns lite högre upp på sidan.

    Approximate plan for the lectures

    The course contains 15 lectures. The chapter references refer to the course literature mentioned above.

      1-2: Introduction, the completeness and compactness theorems.
      Mina stenciler / My handwritten notes (or, for English sources, se any basic book on logic which treats the completeness theorem).

      3-8: Recursion theory, Peano's axiomatization of arithmetic and Gödel's incompleteness theorems: (primitive) recursive functions, sets and relations, representability (in Peano arithmetic) of certain functions and relations, Gödel's incompleteness theorems, undecidability, the stop-problem, s-m-n-theorem, fix point theorems.
      Chap. 5.

      9-11: Set theory: ordinal numbers and cardinal numbers, and their basic arithmetic.
      Chap 7.1 - 7.4.

      12-15: Model theory: basic notions and results, Löwenheim-Skolem theorems, categoricity, Ehrenfeucht-Fraisse games, something about Lindström's characterization of first-order logic, applications, and perhaps something more.
      Chap. 8.1 - 8.2, some parts of my booklet about model theory (which will be available on this page later) and (possibly) something from Chap. 8.3 - 8.5.

    Progress of lectures

    Here I say roughly what I have talked about in the lectures so far.

      lectures 1,2: The completeness and compactness theorems. (my notes)
      18 Sept: Basics about recursive functions; chap. 5.1.1 - 5.1.2 (see also my notes).
      25 Sept: Formalization of Peano arithmetic, representable functions and relations; chap. 6.1 - 6.2 (see also my notes, above).
      29 Sept: Codes of expressions (Gödel numbers), (un)decidability; chap. 6.3, the 'undecidability theorem' 6.28 in the beginning of chap 6.4 (see also my notes).
      9 Oct: Gödel-Rosser incompleteness theorem, Gödel's second incompleteness theorem (my notes above and chap. 6.4), partial recursive functions (chap. 5.2.2). Please, also read about recursively enumerable relations and lemmas 5.0 - 5.4 in my notes above. I will start with Lemma 5.5 in my notes the next time.
      13 Oct: Normal form theorem, indices for partial recursive functions, s-m-n theorem.
      23 Oct: Recursion theorem, fixed-point theorem, Rice's theorem, the stop problem, and characterizations of recursively enumerable sets and relations. chap.5 (and/or my notes).
      30 Oct: Set theory; the axioms, ZF, ZFC, well orderings, ordinals and some basic properties that they have. Chap. 7.1, 7.2.1 - 7.2.2, 7.3.1 (and/or my notes).
      6, 10 Nov: Set theory; statements equivalent (in ZF) to the axiom of choice; cardinal numbers and cardinality. Chap. 7.3.2 - 7.4.3 (and/or my notes).
      20, 27 Nov: Last part of set theory (cardinal arithmetic) and beginnings of model theory; (elementary) embeddings/substructures/extensions, elementary equivalence, Tarski-Vaught test, downward and upward Löwenheim-Skolem theorems. Please, read about categoricity and Vaught's theorem on your own. Chap. 8.1 - 8.2 in course literature, and/or chap. 2.1 - 2.2 in my notes.
      1 Dec: Ehrenfeucht-Fraisse games and 'back and forth' systems. Chap. 2.5 - 2.6 in my notes (available above).
      8 Dec: The amalgamation theorem, (finite) axiomatizability, and an outlook into some influential "classical" problems and results within mathematical logic and its neighbours. Chap. 2.2 - 2.3 in my notes.

    Examination

    The examination consists of two parts:

      1. Assignments which are to be solved during the this autumn, and which are posted on this page.

      2. An examination (written) on 16 December (see examination schedule on the webb for information about exact time and place) which focuses on the central notions, ideas and (proof)arguments in 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 adequately complete all assignments of part (1) that are marked by '*' (see above). For grade 4 the requirements for grade 3 has to be met and in addition at least 50 percent of the assignments without '*' has to be adequately completed; for grade 5 the requirements for grade 3 has to be met and in addition at least 75 percent of the assignments without '*' has to be adequately completed.

    Assignments

      1. Soundness, completeness and compactness: Prove that the formal proof system described via this link is sound; this is a *-assignment (necessary for passing the course). Three more assignments (including one *-assignment) are here. Deadline for the *-assignments (the necessary assignments): 30 September.
      2. Incompleteness theorems and recursion theory: the assignments are here. Deadline for the *-assignments: 6 november, on the lecture if you give me solutions on paper.
      3. Set theory: the assignments are here. Deadline for the *-assignments: 8 december, on the lecture if you give me solutions on paper.
      4. Model theory: the assignments are here. Deadline for all assignments of the course: 10 January. Put them in my mailbox at the mathematics department or send them with an e-mail.
    8 December, 2009,
    Vera Koponen.