29345 - Logic (LM)

Learning outcomes

At the end of the course, students are supposed to become acquainted with the metatheory of some selected formal system. among which modal logics, intuitionistic logic, Peano's arithmetic and corresponding incompleteness results.

Course contents

INCOMPLETENESS AND UNDECIDABILITY

Aim of the course is to analysis the notions of incompleteness and undecidability of formal systems.

 

Topics dealt with in the course:

- First and second order Peano Arithmetic

- First and second order Gödel Theorems

- Tarski Theorem

- Undecidability of first order logic 

- Incompleteness of second order logic

- Modal logic KW

- Turing Machines

- Arithmetical hierarchy and undecidability 

- Chaitin Complexity

- Philosophical investigations on incompleteness, undecidability. complexity 

The treatment of the topics will be homogeneously distributed during the course.

Readings/Bibliography

- Peter Smith, An Introduction to Goedel's Theorems, Cambridge UP, 2008

- Duccio Pianigiani, Una guida ai risultati di incompletezza di Kurt Gödel, Edizioni ETS, Pisa, 2008

-Handouts provided by the teacher

Teaching methods

Lessons in classrooms with blackboard.

Assessment methods

Oral exam based on the explanation of a topic chosen by the student and on a question selected by the teacher.

In order to obtain a good mark students will be supposed to show their comprehension of the main notions introduced in the course and to reconstruct the proofs concerning the chosen topic.

 

Assessment criteria and thresholds of evaluation:

30 cum laude: Excellent as to knowledge, terminology and critical expression.

30: Excellent, knowledge is complete, well articulated and correctly expressed, although with some slight faults.

27-29: Good, knowledge comprehensive and satisfactory, essentially correct expression .

24-26: Fairly good, knowledge present in significant points, but not complete and not always expressed with correctness.

21-23: Sufficient, knowledge is sometimes superficial, but the guiding general thread is included. Expression and articulation incomplete and often not appropriate

18-21:.Almost sufficient, but knowledge present only on the surface. The guiding principle is not included with continuity. The expression and articulation of the speech show important gaps.

<18: Not sufficient, knowledge absent or very incomplete, lack of guidance in discipline, expression seriously deficient. Exam failed.

Teaching tools

- Blackboard

- Teacher's handouts.

Office hours

See the website of Guido Gherardi