Part III Mathematics

This page is undergoing extensive revision over the summer vacation 2017; the current plan is that the course that it pertains to will be lectured in Michaelmas 2017, and naturally I hope to have it properly updated by the start of the academic year. You are welcome to consult it before then, but be sure to reload every time you consult it.
A Part III lecture course on Logic

Gerald Sacks on Mathematical Logic:

``Good afternoon, ladies and gentlemen. The subject of Mathematical Logic splits fourfold into: Recursive Functions, the heart of the subject; Proof Theory, which includes the best theorem in the subject; Sets and Classes, whose romantic appeal far outweigh their mathematical substance; and Model Theory, whose value is its applicability to, and roots in, Algebra.''


In 2010/11 I finally took Sacks' quip to heart and instead of 24 lectures in set theory (and related topics) I lectured a 16 lecture course in computable function theory. From 2012/13 it has been 24 lectures not 16, and was entitled ``Computability and Logic'' rather than ``Computable function theory'' to reflect the slightly wider - more discursive - choice of material. However the 2016 cohort had the benefit of a computability course at Part II, so I stripped out that part of the computability material that is covered in Part II, and will reconfigure the course to suit the new title: Logic. (I am the only person other than Wittgenstein to have given a course of lectures gazetted in the Reporter as Philosophy and I have now capped that by offering a course of lectures gazetted in the Reporter as Logic and I don't think Witters ever did that). One result of that change is that the course is going to look pretty much like the pre-2011 course. I've had a look down the back of the sofa and i've come up with
My lecture Notes from 2009 and
My lecture notes from 2007 ;
My lecture notes from 2015/6;
Henk-Jaap Wagenaar's notes from my lectures from 2015
Dexter Chua's Notes of my lectures from 2016/7.


in 2016 Maurice Chiodo gave a couple of guest lectures on Automatic groups. I am putting here the Introduction to hyperbolic and automatic groups by Baumslag, and the Notes on Hyperbolic and Automatic Groups by Batty and Papasoglu, both kindly provided by Chiodo. I am almost certainly not going to lecture this stuff in 2017/8 but i'm going to leave the links up anyway.

I have put here the current version of the notes from which I am lecturing the first part of the course, on constructive logic; I have put here the current version of the notes from which I am lecturing the second part of the course, on model theory. Other parts will appear later.


I have linked from my Materials for Part II Mathematics page a lot of nice stuff about computable functions, lambda calculus etc. [Scroll down to ``Languages and Automata'']. Some of it is a bit basic for Advanced Lifeforms such as your good selves, and of course the links are on that Part II page beco's they are aimed primarily at Part II students, but there is some material there (mainly the lambda calculus) which is not lectured at Part II, and in any case a bit of revision will do you no harm.
Speaking of lambda-calculus, here is Toby Miller's nice lambda term that tests equality of Church numerals. And I found this rather nice lambda-calculus reduction workbench. I hope you will find it fun.


Among other things I shall be discussing Turing machines. So, if you want a foretaste of how they work, click here . (It's a shame about the voice-over but the video is dead cute.)

Here are Frank Stephan's Notes on computation theory whence I lifted the proof of Kleene-Post.



Here is the appendix to the first edition of Mendelson, wherein he shows how to use induction up to ε -0 to prove the consistency of PA.
Books you might want to read
Nigel Cutland's Computability is worth reading and may be worth actually buying. Boolos-and-Jeffrey ditto, tho' the current edition no longer has the appendix that explains Tennenbaum's theorem. I am putting here a scan of that appendix.

Another book possibly worth getting is Peter Smith's Gödel book .

In 2016 we had a couple of guest lectures from Maurice Chiodo (who is here for a couple of years on a Marie Curie postdoc) on Automatic groups. Readers might like to look at Automatic Sequences, theory, applications, generalizations by Allouche and Shallit. I shall be pillaging material from it, but I don't know how much! You might like to be ahead of the game, and have a look at it. It certainly looks like fun.

In 2017/8 as in 2016/7 I plan to cover some constructive arithmetic and possibly some constructive Analysis (much harder!), with the intention that my students will look at familar Part I material In A New Light. I have just (re)discovered the entirely delightful A Primer of Infinitesimal Analysis by John Bell. Worth a look, tho' perhaps not worth buying.

Wilfrid Hodges: Model Theory (either the five minute argument or the full half-hour) is something the Logician-About-Town should have on their shelves.

All the above books are Cambridge University Press and so you can get 15% off the list price at the Cambridge University Press bookshop in Trinity street [allegedly the oldest bookshop in the world] by brandishing your wee blue card.

Also by John Bell (co-authored with Alan Slomson) but not published by CUP (it's from Dover) is Models and Ultraproducts. It was the first book on model theory that I read, and I loved it. And it's just the right level for you lot, too.


Part III Essays
There are Logic-related essays that I sponsor, so if you want one come and talk to me. Subject to confirmation by the Part III committee the following Part III essays will be available in 2017/8:

Large Countable Ordinals;
BQOs and WQOs;
Fraenkel-Mostowski Models;
Nonstandard Analysis;
and
Quine's Set Theory ``NF''.

I welcome enquiries about them. That said, the material for the first two might get covered in my Part III lectures if nobody wants to do essays on them, so I might discourage you from doing either of them!

If you are interested in countable ordinals you might like to read (the rather discursive) talk i gave at the TMS in 2012 and Notes on countable ordinals . Cambridge students who did Part II in 2016/7 will have encountered a rudimentary form of Fraenkel-Mostowski models in my proof of the independence of the Axiom of Choice. I promote Fraenkel-Mostowski models partly because the final step in Randall Holmes' proof of the consistency of Quine's New Foundations is a [diabolical] FM construction and it is a medium-term project of mine to really understand it. I am most of the way there, but the one part I have not yet fully mastered is precisely that final step. So I am always happy to talk to anyone about FM constructions! That diabolical FM construction is of course beyond the scope of a Part III essay [and i use the word diabolical advisedly: Holmes had to sell his soul to The Auld Ane to get the proof, and we owe it to him to ensure that his sacrifice is not in vain] but the general idea of an FM construction is a very good topic for a Part III essay. If we have several takers we could have a reading group and that could be Serious Fun.


Part III students should remember that if the essay they want to write is not listed, it is entirely in order for them to ask for someone to set it. That is how i ended up setting the essay on Nonstandard Analysis! Try your luck.

Materials for 1b Computer Science.
Materials for 1a Computer Science .
Materials for Logic-For-Linguists.
Materials for Part II Mathematics .
Materials for Part IV Mathematics .
Materials for the Computer Science M. Phil .