5 credits
30.0 h
Q1
This biannual learning unit is being organized in 2017-2018
Teacher(s)
Verdée Peter;
Language
French
Prerequisites
Basic instruction in logic and philosophy of language.
Main themes
Each year this course will select a particular theme - for example, theories of grammaticality, meaning, discourse analysis, pragmatics, modal logics, lambda calculus, theory of proof, set theory, non-classical logic, contemporary approaches to ancient logic, etc.
Aims
At the end of this learning unit, the student is able to : | |
| 1 |
At the end of the course the student should be able to understand the background of current debates in logic
At the end of the course the student should : |
The contribution of this Teaching Unit to the development and command of the skills and learning outcomes of the programme(s) can be accessed at the end of this sheet, in the section entitled “Programmes/courses offering this Teaching Unit”.
Content
Limitative theorems in logic and their philosophical implication
In this course we study the limitative theorems proven by Gödel, Tarski, Church and Turing in the 1930's. It concerns the following five famous results.
1) Every formal system of a certain expressive strength is necessarily incomplete. (Gödel
2) Every formal system of a certain expressive strength is unable to prove its own consistency. (Gödel)
3) Every formal system of a certain expressive strength cannot contain its own truth predicate. (Tarski)
4) There is no general algorithm that can compute whether a procedure is going to halt for a given input, neither is there one that can compute whether a predicate logic formula is valid. (Church and Turing)
5) Every theory formulated in predicate logic which has an infinite model, has a model of arbitrary cardinality. (Löwenheim and Skolem)
All of these results have had an enormous humbling effect on the foundations of mathematical and scientific theories. They destroyed the hope that we would be able to reduce complex theories to their logical axiomatizations that would once and forever decide on the truth of each sentence. The influence of these theorems on epistemology, (the philosophy of) mathematics and (the philosophy of) computer science can hardly be overestimated. Unfortunately, all of these results have also been abused by drawing too far reaching (often post-modernist) conclusions from some interpretation of the formal theorems.
We will go through some essential preliminaries in order to be able to understand the five theorems (predicate logic, recursive functions, Turing machines, Peano and Robinson arithmetic). We will study the precise formal meaning of the five theorems. For the first four we will give a clear sketch of their ingenious proofs. Finally we will carefully study the philosophical implications of the studies theorems on the basis of selections from [1] and [4] of the bibliography.
In this course we study the limitative theorems proven by Gödel, Tarski, Church and Turing in the 1930's. It concerns the following five famous results.
1) Every formal system of a certain expressive strength is necessarily incomplete. (Gödel
2) Every formal system of a certain expressive strength is unable to prove its own consistency. (Gödel)
3) Every formal system of a certain expressive strength cannot contain its own truth predicate. (Tarski)
4) There is no general algorithm that can compute whether a procedure is going to halt for a given input, neither is there one that can compute whether a predicate logic formula is valid. (Church and Turing)
5) Every theory formulated in predicate logic which has an infinite model, has a model of arbitrary cardinality. (Löwenheim and Skolem)
All of these results have had an enormous humbling effect on the foundations of mathematical and scientific theories. They destroyed the hope that we would be able to reduce complex theories to their logical axiomatizations that would once and forever decide on the truth of each sentence. The influence of these theorems on epistemology, (the philosophy of) mathematics and (the philosophy of) computer science can hardly be overestimated. Unfortunately, all of these results have also been abused by drawing too far reaching (often post-modernist) conclusions from some interpretation of the formal theorems.
We will go through some essential preliminaries in order to be able to understand the five theorems (predicate logic, recursive functions, Turing machines, Peano and Robinson arithmetic). We will study the precise formal meaning of the five theorems. For the first four we will give a clear sketch of their ingenious proofs. Finally we will carefully study the philosophical implications of the studies theorems on the basis of selections from [1] and [4] of the bibliography.
Teaching methods
Every week a given text is studied. Students read the text in detail before the class. In class, the text is discussed and the students ask questions about the text.
Evaluation methods
Students can freely choose between the following choices:
1) a presentation of roughly one hour for the other students, followed by questions from other students and the professor) on a topic relevant for the contents of the course
2) a written essay followed by a discussion on the essay
3) an oral open book exam in the official examination period
1) a presentation of roughly one hour for the other students, followed by questions from other students and the professor) on a topic relevant for the contents of the course
2) a written essay followed by a discussion on the essay
3) an oral open book exam in the official examination period
Other information
/
Online resources
/
Bibliography
1. Torkel Franzén, Gödel's Theorem: An Incomplete Guide to its Use and Abuse, A K Peters 2005.
2. Kurt Gödel: Collected Works, Volume I: Publications 1929-1936, Oxford University Press, New York, Oxford 1986; Volume III, Oxford University Press, 1995.
3. Douglas R. Hofstadter, Gödel, Escher, Bach, an Eternal Golden Braid, Basic Books, NY 1979.
4. Jean Ladrière. Les limitations internes des formalismes. Étude sur la signification du théorème de Gödel et des théorèmes apparentés dans la théorie des fondements des mathématiques, ed.Nauwelaerts-Gauthier-Villars, Leuven-Paris, 1957; réed. éd. J. Gabay, coll "les grands classiques", Paris 1992.
5. Peter Smith, An Introduction to Gödel's Theorems, Cambridge University Press 2007.
6. Raymond M. Smullyan, Gödel's Incompleteness Theorems, Oxford University Press, New York, Oxford 1992.
2. Kurt Gödel: Collected Works, Volume I: Publications 1929-1936, Oxford University Press, New York, Oxford 1986; Volume III, Oxford University Press, 1995.
3. Douglas R. Hofstadter, Gödel, Escher, Bach, an Eternal Golden Braid, Basic Books, NY 1979.
4. Jean Ladrière. Les limitations internes des formalismes. Étude sur la signification du théorème de Gödel et des théorèmes apparentés dans la théorie des fondements des mathématiques, ed.Nauwelaerts-Gauthier-Villars, Leuven-Paris, 1957; réed. éd. J. Gabay, coll "les grands classiques", Paris 1992.
5. Peter Smith, An Introduction to Gödel's Theorems, Cambridge University Press 2007.
6. Raymond M. Smullyan, Gödel's Incompleteness Theorems, Oxford University Press, New York, Oxford 1992.
Faculty or entity
EFIL
