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.''
When i reached 70 I vowed I would not lecture Part III again, but
Prof Bollobas told me i should, so i will. However this will
definitely be the last lecture course i give in Cambridge. (I shall be lecturing Maths 713 in Auckland in july 2022.)
Content
Here is the current
version of the notes from which I had been proposing to lecture this course, when i was going to lecture it before COVID. You are
welcome to read them if you want to hit the ground running but
you should not download them. The single most
important respect in which they will change is in deletion of
material. There is far more stuff in that folder than
i can possibly lecture and I haven't yet decided which bits to leave out. This
leaves you time to lobby me to cover (or omit) specific topics.
Background
Much of what you might expect to find under a heading like this is in the Prolegomenon to the online notes from which I would have lectured and which are linked above.
My intended audience is people who did Set Theory and Logic and
Languages and Automata at Part II. The point, really, is that if you
are a Cambridge student doing Part III who did Part II last year and
who now wants to do Computability-and-Logic at Part III then you
would have chosen those courses when you did Part II, so it is a
reasonable assumption for me to make that you attended them. With
that in mind you might like to look at the material on my Materials for Part II Mathematics page .
I am guilty of two pdfs which contain most (if not all) the
basic logic and discrete maths that in my not-so-humble opinion
should be in the backpack of every young mathematician about town.
One on Countability and another on Discrete Mathematics. They were
designed for 1a's but Gareth tells me they are far too advanced for
1a's. They contain elementary material that may have escaped your
notice, and which—if you going to do logic—you will find
agreeable. Read through them quickly, it won't take long.
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 2021/22 but i'm going to leave the links up anyway.
I am leaving here
the notes from which I lectured the first part of the course in 2017, on constructive logic; and here
the notes from which I lectured the second part of the course, on model theory.
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 Introduction to Mathematical Logic wherein
he shows how to use induction up to ε0 to prove the
consistency of PA. Actually that appendix has come back to life as an
appendix to the latest edition of Mendelson's text.....which is an excellent
book.
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.
I may 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 several 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 2021/22; and
I welcome enquiries
about them.
I am trying to get off the ground an essay on
Synonymy; the proposal linked
here is formatted like an official proposal but it is as yet only
in draught form. If you like the look of it, and think you might
want to do it, by all means contact me and i shall work it up into
a proposal acceptable to the committee.
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 .