# Logic & Computation

Module 3LC for third year mathematics MAM3.

## Lecturer

Vasco Brattka

Department of Mathematics & Applied Mathematics
University of Cape Town ## Time Table (2009)

The lectures take place in M204 at 11:00 (fourth period) on Tuesdays, Fridays and the following Wednesdays:
• 25 Feb, 11 Mar, 25 Mar, 22 Apr, 6 May, 20 May.
The tutorial takes place in M214 at 14:00 (sixth period), each Tuesday.

## Course Description

Logic is the general theory of reasoning. The roots of this discipline go back to ancient times but since the late 19th century the field has seen a vast development. Due to the paradoxes which have been discovered after mathematics had been build on the language of set theory, a careful re-investigation of the logical basis of mathematics became necessary. It was the idea of Hilbert's program to develop mathematics from sound and complete axioms in a systematic way. This program, in its original form, came to an end after Gödel proved his famous Incompleteness Theorem which roughly speaking shows that no such general axiomatic development is possible (even for arithmetic there is no axiom system which is both, sound and complete). Hence, it became clear that provability and truth are two different aspects of mathematical statements. In this course we will try to capture the elementary development of mathematical logic.

In particular, we will cover the following topics:

• distinction between syntax and semantics,
• propositional logic,
• first-order logic,
• theories and models,
• arithmetic. M.C. Escher's "Drawing Hands" © 2005 The M.C. Escher Company - The Netherlands. All rights reserved. Used by permission. www.mcescher.com

## Contents

### Part A: Propositional Logic

1. Introduction
• Introduction
• Historical Background
• Aristotle's Analytics
• Hilbert's Program
• Gödel's Incompleteness Theorem
• Syntax and Semantics
• Different Logics
2. Syntax of Propositional Logic
• Propositional Logic
• Symbols of Propositional Logic
• Syntax of Propositional Logic
• Formation Trees
• Recursive Definitions and Structural Induction
3. Semantics of Propositional Logic
• Semantics of Propositional Logic
• Truth Tables
• Evaluation of Formulas with Trees
• Satisfiability and Tautologies
• Coincidence Lemma
• The Truth Table Method
4. Logical Implication and Equivalence
• Logical Implication and Equivalence
• Syntactical Implications and Logical Consequences
• Realizability of Boolean Functions
• Disjunctive and Conjunctive Normal Form
• Complete Sets of Connectives
• Digital Circuits
5. The Compactness Theorem
• Satisfiability and Logical Consequences of Sets of Formulas
• The Compactness Theorem
6. Computability Notions for Subsets
• Notions of Computability
• Computability and Computable Enumerability
• The Truth Table Method
• Computable Enumerability of Logical Consequences
7. Axioms for Propositional Logic
• An Axiom System for Propositional Calculus
• Soundness Theorem
• Deduction Theorem
• Hypothetical Syllogism
8. Consistency and Completeness
• Consistency and Completeness
• Characterization of Consistency
• Characterization of Consistent Extensions
• Lindenbaum's Theorem
9. The Completeness Theorem
• Completeness and Implication
• Satisfiability of Consistent Sets
• Completeness Theorem
• A Proof Theoretic Proof of the Compactness Theorem

### Part B: First-Order Logic

1. Syntax of First-Order Logic
• First-Order Logic
• Symbols of First-Order Logic
• Syntax of First-Order Logic
• Terms and Formulas
• Free and Bound Occurrences of Variables
• Closed Formulas
2. Semantics of First-Order Logic
• Semantics of First-Order Logic
• Structures
• The Structure of Arithmetic
• Assignments and Valuations
• Satisfiability over Structures with Assignments
• Valid Formulas
• Coincidence Lemma
3. Substitution and the Translation Lemma
• Substitution Instances of Tautologies
• Logical Implication and Equivalence
• Substitution in Terms and Formulas
• Terms which are Free For Variables in Formulas
• The Translation Lemma
4. Prenex Normal Form and Skolem Normal Form
• Renaming of Bound Variables and Rectification of Formulas
• Prenex Normal Form
• Skolem Normal Form
• Universal Closure of Formulas
5. Herbrand Structures
• Satisfiability of Sets of Formulas
• Herbrand Structures
• Herbrand Models for Formulas in Skolem Normal Form
• Theorem of Löwenheim-Skolem
• Theorem of Herbrand
6. The Enumerability Theorem
• The Compactness Theorem of First-Order Logic
• Logical Consequences of Sets of Formulas
• Gilmore's Procedure
• The Enumerability Theorem
• The Theorem of Church
• Computably Enumerable Classes of First-Order Formulas
7. Axioms for First-Order Logic
• An Axiom System for First-Order Calculus
• Deducibility and Theorems of First-Order Logic
• Substitution Instances of Tautologies
• Soundness Theorem of First-Order Logic
• Deduction Theorem of First-Order Logic
• Deduction for Closed Formulas and Hypothetical Syllogism
8. Consistency, Completeness and Henkin Sets
• Consistency and Completeness
• Lindenbaum's Theorem
• Provable Variable Change
• Henkin Sets
9. Gödel's Completeness Theorem
• Implication and Universal Closure
• Model Existence Lemma
• Gödel's Completeness Theorem
• A Proof Theoretic Proof of the Enumerability Theorem

### Part C: Models & Theories

1. The Homomorphism Theorem
• The Homomorphism Theorem
• Elementary Equivalent Structures
• Definability in Structures
• The Automorphism Theorem
2. First-Order Logic with Equality
• First-Order Logic with Equality
• Normal Structures
• Non-Characterizability of Normality
• An Axiom System for First-Order Calculus with Equality
• Equivalence Relations
• Congruence Relations
• Quotient Structures
• Characterization of Normal Models
3. Normal and Finite Models
• Normal Completeness Theorem
• Normal Compactness and Enumerability Theorem
• Theorem of Löwenheim-Skolem for Normal Models
• Theorem on Infinite Normal Models
• Characterization of Normal Structures with Finite Universe
4. Theories
• Theories
• Theories of Structures and Consequences of Formula Sets
• Characterization of Inclusion of Theories
• Complete Theories
• Group Theory and Other Examples
5. Complete Theories
• Categoricty and the Łoś-Vaught Test
• Substructures and Elementary Substructures
• Model Completeness and the Robinson Test
• Quantifier Elimination
6. Axiomatizable Theories
• Axiomatizable Theories
• Computability of Axiomatizable Theories
• Computability of Theories of Finite Structures
• Computably Enumerable Classes of First-Order Formulas
• The Spectrum Problem
7. Order-Theoretic Theories
• Theory of Dense Linear Orderings Without Endpoints
• Theorem of Cantor
• Theory of Equivalence Relations
• Theorem of Janiczak
8. Algebraic Theories
• Theory of Fields
• Theory of Fields of a Certain Characteristic
• Theorem of Tarski
• Some Decidable Theories
• Some Undecidable Theories
9. Versions of Arithmetic
• Versions of Arithmetic
• Arithemtic With Successor
• Arithmetic with Successor and Comparison
• Presburger Arithmetic
10. Peano Arithmetic and Gödel's Incompleteness Theorem
• Peano Arithmetic
• Skolem's Nonstandard Model for Arithmetic
• Gödel's First Incompleteness Theorem
11. Zermelo-Fraenkel Set Theory
• Zermelo-Fraenkel Set Theory
• Interpretation of Arithmetic in Set Theory
• Gödel's Second Incompleteness Theorem
• Consistency of Set Theory
• The Axiom of Choice
• The Continuum Hypothesis

### Part D: Other Logics

1. Second-Order Logic

## Slides

The course slides simultaneously serve as lecture notes.

## Class Record, Tests, Examination

There will be a 90 minute class test on Thursday, 2 April (provisional date) and a 90 minute written exam in May/June.
The final mark (FM) is calculated from the class record (CR) and the examination mark (EM) using the formula
• FM = max(0.4 CR + 0.6 EX, 0.1 CR + 0.9 EX).

## References

The following text books are not prescribed to the course but recommended for further reading:
• Herbert B. Enderton, A Mathematical Introduction to Logic, 2nd Edition, Academic Press, New York 2001
(Publisher's information, Errata)
• Elliott Mendelson, Introduction to Mathematical Logic, 4th Edition, Chapman & Hall, London 1997
(Publisher's information)
• Uwe Schöning, Logic for Computer Scientists, Birkhäuser, Boston 1989
• A.G. Hamilton, Logic for Mathematicians, Cambridge University Press, 1987
If you intend to buy a book, then the first one is recommended for this purpose.

## History

Here are some links to biographies of some famous logicians (at Mathematics Archive St Andrews): And here is some background information (from Stanford Encyclopedia of Philosophy):

© 2005-2009 Vasco Brattka