Introduction to Logic and Model Theory

Beskrivelse

This course is mainly addressed to postgraduate students in Computer Science and Mathematics with the aim of introducing the basic concepts, results and tools from Mathematical Logic and Model Theory. The course will approach most of the hot problems in these fields, from the paradoxes of Set Theory to Gödel's theorems, while the main focus will be on Classical First and Second Order Logics and on Modal Logics. We will formally define various metamathematical concepts such as syntax, semantics, truth, provability, completeness and complete axiomatizations, compactness, decidability, quantification etc. With some of these concepts the students are already familiar from more specific courses. The role of this course is to present these concepts in a general framework and to clarify the spectrum of their use and applicability.

Formally, the course will cover the following topics:

I. An introduction to Classical Logic and Model Theory
I.1. Formal Theories
I.2. Propositional Logic (PL)
I.2.1 Syntax and Semantics, truth tables
I.2.2 Conjunctive and disjunctive normal forms
I.2.3 Proof theories for PL
I.2.4. Completeness and compactness
I.3. First Order Logic (FOL)
I.3.1. Syntax and Semantics
I.3.2. Axiomatization
I.3.3. Completeness and Compactness
I.3.4. Lowenheim-Skolem Theorems
I.3.5. Henkin’s constants and the relation to PL
I.4. Monadic Second Order Logic and finite state machines

II. Modal Logic and its Model Theory
II.1. Kripke structures and transition systems
II.2. Bisimulations and zig-zag morphisms
II.3. The standard translation into FOL and SOL
II.4. Model constructions
II.5. Bisimulation and invariance
II.6. Classical truth-preserving constructions
II.7. Axiomatizations and Weak Completeness
II.7.1. Axiomatic systems
II.7.2. Finite model property
II.7.3. Canonical models
II.7.4. The filtration method

III. Multimodal Logics for Transition Systems
III.1. Hennessy-Milner Logic
III.2. Dynamic Logic
III.3. Epistemic Logics
III.4. Probabilistic and Markovian Logics
III.5. Temporal and probabilistic/stochastic temporal logics

Periode	nov. 2011 → dec. 2011
Sted for afholdelse	Unknown external organisation