Formalized logic A

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 understood as including the theory of argumentation (rhetoric) and philosophy of language and eventually be able to conduct research in one of these areas. At the end of the course the student should : be able to use certain specific tools for research in logic and philosophy of language ; have a good general grasp of the breadth of contemporary research, and if appropriate, of the history of logic and philosophy of language ;  be able to make use of contributions from other disciplines in philosophical research in logic and philosophy of language.

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.

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

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.

Faculty or entity

EFIL