I'm reviewing the books on the MIRI course list. After putting down Model Theory partway through I picked up a book on logic. Computability and Logic, specifically.

Computability and Logic

This book is not on the MIRI course list. It was recommended to me by Luke along with a number of other books as a potential way to learn provability logic.

Computability and Logic is a wonderful book. It's well written. It's formal, but pulls off a conversational tone. It demonstrates many difficult concepts with ease. It even feels nice — it's got thick pages, large text, and a number of useful diagrams.

That said, I didn't find it very useful to me personally.

This book is a wonderful introduction to computability, incompleteness, unsatisfiability, and related concepts. It masterfully motivates the connection between computability and logic (a subject near and dear to my heart). It could be an invaluable resource for anyone in computer science looking to branch out into logic. It starts with the basic concept of enumeration and takes you all the way through Löb's theorem: quite an impressive feat, for one textbook.

For me, though, it was on the easy side. I already knew all the computability stuff quite well, and skimmed over much of it. The logic sections were a good refresher, though they were somewhat rudimentary by comparison to Model Theory. (Actually, this book would have been a great precursor to Model Theory: It spent quite a bit of time motivating and fleshing out concepts that Model Theory dumps on your head.)

Still, while this book was not exactly what I needed, I highly recommend it for other purposes. Its contents are summarized below.

Contents

Enumerability
Diagonalization
Turing Computability
Uncomputability
Abacus Computability
Recursive Functions
Recursive Sets and Relations
Equivalent Definitions of Computability
A Précis of First-Order Logic: Syntax
A Précis of First-Order Logic: Semantics
The Undecidability of First-Order Logic
Models
The Existence of Models
Proofs and Completeness
Arithmetization
Representability of Recursive Functions
Indefinability, Undecidability, and Incompleteness
The Unprovability of Consistency
Normal Forms
The Craig Interpolation Theorem
Monadic and Dyadic Logic
Second-Order Logic
Arithmetical Decidability
Decidability of Arithmetic without Multiplication
Nonstandard Models
Ramsey's Theorem
Modal Logic a

...

dalchris

dalchris

dalchris

dalchris

dalchris

dalchris