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:

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

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 .