# completeness of first-order logic

## Summary

Godel's Completeness Theorem shows that there is a complete (and sound) deductive calculus for first-order logic. In other words, if some set of sentences is consistent (one cannot derive a contradiction from them), then there is some model in which all the sentences are satisfied. This result is significant in that it unifies the syntax and semantics of first-order logic.

## Context

This concept has the prerequisites:

- first-order logic
- semantics of first-order logic (Defining completeness requires defining the semantics.)
- proofs in first-order logic (One must show a particular predicate calculus to be complete.)
- countable sets (The proof of the Completeness Theorem involves countable sets.)

## Goals

- Know what it means for a first-order deductive calculus to be complete

- Know the statement of Godel's Completeness Theorem

- Prove Godel's Completeness Theorem (Henkin's proof in particular)

- Using the Completeness Theorem, prove the Compactness Theorem for first-order logic.

## Core resources (read/watch one of the following)

## -Free-

→ Notes on Logic (2013)

Lecture notes for a course on first order logic.

## -Paid-

→ A Mathematical Introduction to Logic

An undergraduate textbook in mathematical logic, with proofs.

- Section 2.2, "Truth and models," subsection "Homomorphisms," pages 94-99
- Section 2.5, "Soundness and completeness theorems," pages 131-145

Other notes:

- Refer to Section 2.4 for the specific deductive calculus.

→ A Course in Mathematical Logic

A graduate textbook in mathematical logic.

- Section 2.7, "Hintikka sets," pages 83-88
- Section 3.3, "Completeness of the first-order predicate calculus," pages 117-122
- Section 3.5, "What have we achieved?", pages 122-124

## See also

-No Additional Notes-