29345 - Logic (LM)

Course Unit Page

Academic Year 2021/2022

Course contents

INCOMPLETENESS AND UNDECIDABILITY

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

Topics dealt with in the course:

- Historic overview of the debate on the foundations of mathematics

- First and second order Peano Arithmetic and Robinson Arithmetic

- First and second order Gödel Theorems

- Tarski Theorem

- Undecidability of first order logic

- Incompleteness of second order logic

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

Non-attending students are referred to the instructions given in the section "Readings/Bibliography".

 

COMMUNICATION FOR THE STUDENTS OF THE COURSE LOGICA (LM) 12 CREDITI: the second module of the course will be borrowed from the course Teoria dei Modelli (1) (LM).

Readings/Bibliography

The main material to study for the preparation of the final exam is constituted by the handouts provided by the teacher.

Non-attending students must also read the book by Peter Smith, An Introduction to Goedel's Theorems, Cambridge UP, 2008.

Teaching methods

Lessons in classroom with electronic blackboard also available in streaming.

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 have to show their comprehension of the main notions introduced in the course and to reconstruct the proofs concerning the selected 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 mostly 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

On line streaming

- Electronic blackboard

- Handouts of the teacher.

Office hours

See the website of Guido Gherardi