University of Alberta
Faculty of Arts
Department of Philosophy

Phil 522/422: Topics in Logic/Topics in Advanced Symbolic Logic
Winter term (2012/13)

Katalin Bimbó

The most famous logician of the 20th century was K. Gödel, whose “incompleteness theorems” gained wide recognition.  These theorems turned out to be immensely fruitful for metamathematics.  At the same time, Gödel's theorems are often misrepresented and misused outside of formal disciplines.

This course will introduce some concepts of computable functions such as Turing machines, partial recursive functions, λ-computable functions, Markov algorithms or register machines.  According to Church's thesis, &lambda-computable functions capture the notion of effective computation; hence, so does any of the equivalent formalisms.  Partial recursive functions (more than) suffice to arithmetize the syntax of a first-order theory.

The main focus of the course will be on first-order arithmetic (“Peano arithmetic”), and on the proof of its incompleteness.  The “incompleteness theorems” can be and are often presented in a way that conceals many details of their proofs.  We will pursue a deeper understanding and greater appreciation of the ingenuity and beauty of these theorems via scrutinizing many of the important pieces of the proofs.

Gödel's original proof inspired new questions, some of which have been answered since the time of his paper.  We may take a look at such related topics, for example, ω-consistency, the undecidability of first-order logic, a theory weaker than Peano arithmetic that is still subject to incompleteness theorems, and theorems not provable in Peano arithmetic, which have independent (from the incompleteness proof) interest.

Time:    M, W, F   15:00 pm–15:50 pm

  For further information, please contact the instructor at .
The official course outline is available in the e-classroom during the course.

[Last updated on March 9th, 2012.]