Mathematical logic, HT 2001 (MAN480/TMA240)

Svensk version



THE EXAM (omtenta) IS CORRECTED! The results will be at the notice-board in the basement this afternoon (2 September).

The first exam with solutions can be found here.

Grades on the exam:

GU: 0-11 U, 12-19 G, 20-25 VG and CTH: 0-10 U, 11-14 3, 15-19 4, 20-25 5.

There is a Course Enquiry (kursenkät) now. Please fill it out, it is important for us when we plan next years course. There is only a swedish version, but you are most welcome to answer in english.

Which are the good exercises, thinking of the exam?

In general, all the exercises of the lessons are relevant, they are included in the following list of, which also include some more. Some more exercises will most probably be added.

Jan has written some extra material on Natural Deduction(pdf) and Kripke semantics(pdf). It's a good complement to van Dalen.

There is a proof editor for Unix (developed at Chalmers) called Alfa which handles ND perfectly well. You start the editor by the command "alfa - -norec" and a deduction starts by choosing ND Style Proof in the menu.

We have changed the literature to van Dalen: Logic and Structure.

  What is included in the course?

The course is a short introduction to mathematical logic. The two main goals are

We are going to talk about propositional and predicate (first order) logic and do some formal proofs in a proof system called natural deduction (ND for short). Some properties of propositional and predicate logic will be shown; for example completeness, which says that a sentence is true iff it can be proved in ND. We will also spend some time with Gödels incompleteness theorem, which says that there is no "good" set of axioms from which we can prove all arithmetical truths.


We will use the book Logic and Structure, written by Dirk van Dalen (Springer Verlag). At least chapter 1-3 and 5 is included in the course and maybe something more. Besides the book we are going to cover Gödels incompleteness theorem (which is not in the book).

There are a lot of other good books if you want to read more about logic. Introduction to mathematical logic by E. Mendelson is an example of a very good book.

  What we have done so far in the lectures.

  What we will do the next lecture

  Details of what is included in the course of what we have covered so far

Chapter 1

1.1 Induction principle and Definition by recursion are important. You don't have to know about formation sequence and Induction on rank-Principle. 1.2 Everything. 1.3 pp. 24-26 up to Definition 1.3.10 are not included. Definition 1.3.10 and the rest of section 1.3 contains very good examples of inductive definitions and proofs.

Chapter 2

All of 2.1-2.4. Section 2.5 contains a lot of examples which are good to have a look at. Understand what Theorem 2.5.8 says, as you can see the proof of this rather obvious theorem on substitution is a bit messy. Definition 2.5.10 and Theorem 2.5.11 about prenex form are important. All of 2.6. 2.7 contains many good examples, but the only one you are required to know about is Ex. 6 which is about arithmetic. All of 2.8-2.10, but 2.8 and 2.9 can be replaced by the notes on Natural Deduction(pdf).

Chapter 3

3.1:pp 105- middle of 110. Please note that we gave another proof of Lemma 3.1.9 which is hinted in the remark after the proof.

3.2: I did not follow the book on this material. Theorem 3.2.1 is important and also Lemma 3.2.6. See also exercise 3.3.8.

3.3: Some bits of Application I. Non-standard Models of Arithmetic on page 122.

Chapter 5

Sections 5.1 and 5.2, but Kripke semantics only for propositional logic. For the exam, it is enough to read the extra material on Kripke semantics(pdf).

  Plan for the lessons

  Old exams

Please observe that the course is rather different this year and therefore the old exams are not really appropriate.


Last modified: Mon Sep 2 12:00:16 MEST 2002