The Mathematics of Logic: A Guide to Completeness Theorems and Their Applications

I am a serious CD collector. Well, maybe eclectic and obsessive is more like it. I have over 25,000 CDs and they are organized in drawers, each with an icon, basically a single symbol representing a class into which CDs are organized lexigraphically. However, with a finite set of drawers, no matter how imaginative my symbols (60s rock is a peace sign, heavy music is an anvil, etc.), I always end up acquiring a disc that “does not exist” according to my “formal system”. That is OK. I have a drawer for such recordings and the symbol there is Gödel’s face. There they wait until I can extend into new combinations of drawers and icons.

As you can see, the idea of Gödel’s Theorem fascinates me, but its general meaning and application have been obscure to me. Richard Kaye, Senior Lecturer in Pure Mathematics at the University of Birmingham, has done a great service in producing a concise yet self-contained book that is a guide to completeness theorems and their applications. The book is suitable for self-guided learning of this fundamental and fascinating area, or as a textbook for a first course in mathematical logic for undergraduate and first-year graduate students.

Each focused chapter sticks to a single point in three sections. The first section of preliminaries and core ideas is essential. A following section is rich in applications, exercises, and examples. Along with additional discussion, proofs, and exercises, the reader will find hints and some answers to the text’s exercises at a case-sensitive URL in the book. Additional sections offer a more penetrating look into the subject at hand and are for the more ambitious and advanced reader.

Completing the book gives the diligent reader a full mathematical account of the Completeness Theorem for first-order logic. The book starts at the easy to grasp idea of König's Lemma and continues into order relations in sets, Zorn's Lemma, formal systems including post systems and compatibility, deductions and proofs about posets, Boolean algebras, propositional logic, filters and ideals. Applications toward the end include first-order logic, completeness and compactness, model theory, and nonstandard analysis. Progressing through these areas in increasing complexity, Kaye minimizes anything extraneous to the critical path of the book and provides proofs of all the required set theoretical results.

Tom Schulte (http://www.oakland.edu/~tgschult/) collects CDs and math books in Michigan and is in the Industrial Applied Mathematics graduate program at Oakland University (http://www.oakland.edu).