Menù principale
B020989 - CALCULABILITY AND LOGIC
Main information
Teaching Language
Course Content
Suggested readings
Learning Objectives
Prerequisites
Teaching Methods
Further information
Type of Assessment
Course program
Academic Year 2020-21
Course year
First year - First Semester
Belonging Department
Humanities (DILEF)
Course Type
Single education field course
Scientific Area
M-FIL/02 - LOGIC AND PHILOSOPHY OF SCIENCE
Credits
6
Teaching Hours
36
Teaching Term
14/09/2020 ⇒ 04/12/2020
Attendance required
Yes
Type of Evaluation
Final Grade
Course Content
show
Course program
show
Lectureship
Teaching Language
Italian
Course Content
Introduction to recursion theory. Goedel-Church-Tarski theorems: Incompleteness, undecidability, undefinability of truth.
Suggested readings (Search our library's catalogue)
a) lectures notes;
b) P. Smith. An introduction to Goedel's theorems. CUP 2007
b) P. Smith. An introduction to Goedel's theorems. CUP 2007
Learning Objectives
(i) Knowledge and understanding. Knowledge of the main theoretical issues and methodologies concerning recursion theory and limitative theorems. Understanding specific problems in these areas.
(ii) Applying knowledge and understanding. Applying the above knowledge and understanding though suggested exercises dealing with specific problems in the area of logic.
(iii) Making judgements.
Critical understanding of scientific contributions (articles, books) in an autonomous way.
(iv) Communication skills.
Ability to present in an appropriate way problems, solutions to problems, theories, arguments, proofs.
(ii) Applying knowledge and understanding. Applying the above knowledge and understanding though suggested exercises dealing with specific problems in the area of logic.
(iii) Making judgements.
Critical understanding of scientific contributions (articles, books) in an autonomous way.
(iv) Communication skills.
Ability to present in an appropriate way problems, solutions to problems, theories, arguments, proofs.
Prerequisites
Background knowledge corresponding to the program of the Logic 1 course (12 CFU)/ BA level. Contact the teacher before enrolling in the course.
Teaching Methods
Lectures, plus tutorial
Further information
This course uses the E-Learning Platform MOODLE (http://e-l.unifi.it/). Students are requested to register online within the first week of the course.
Course materials (lectures notes, exercises etc.) will be available online at the Moodle page of the course.
The course requires a regular attendance (at least 2/3 of the lectures)
Course materials (lectures notes, exercises etc.) will be available online at the Moodle page of the course.
The course requires a regular attendance (at least 2/3 of the lectures)
Type of Assessment
Oral examination (about 45 min.), typically based on two questions for each of the two parts of the program (recursion theory; limitative theorems). The student should be able to explain in a clear and appropriate language the main theoretical notions taught during the course, as well as to apply them correctly to the solution of simple exercises/problems.
Course program
Computability.
Primitive recursive functions.
Mu-recursive functions.
Kleene's normal form theorem.
First-order Peano arithmetic and subsystems.
Arithmetization of the syntax.
Representability.
Diagonalization Lemma.
Goedel's incompleteness theorems.
Church and Tarski theorems.
Primitive recursive functions.
Mu-recursive functions.
Kleene's normal form theorem.
First-order Peano arithmetic and subsystems.
Arithmetization of the syntax.
Representability.
Diagonalization Lemma.
Goedel's incompleteness theorems.
Church and Tarski theorems.