Download PDF

Propositional logic

Inference in propositional logic

Axioms for propositional logic

First-order logic

Gödel’s completeness theorem and the compactness theorem

Natural numbers and the successor function

Presberger arithmetic

Orderings

Subtraction and division

Divisors and prime numbers

Modulus and remainders

GCD and LCM

Skolem arithmetic

Löwenheim-Skolem theorem

Robinson arithmetic

First-order peano arithmetic

The fundamental theorem of arithmetic

Finite sequences of natural numbers

Powers, exponents and logarithms of natural numbers

Gödel numbering

The Gödel incompleteness theorems

Second-order logic

Second-order peano arithmetic

Axiom schema of specification and cardinal numbers

Set algebra

The axiom of extensionality

Axiom of adjunction

Algebra of cardinality

Orderings on sets and ordinal numbers

Zermelo–Fraenkel set theory

Axiom of union

The halting problem

Effective procedures

Proof theory

Model theory

The Entscheidungsproblem

Kleene's s-m-n Theorem

Primative recursive functions

Computable functions

General recursive functions

The Lambda calculus

Church encoding and Church numerals

Please select a chapter from the left.

This is a live document, and is full of gaps, mistakes, typos etc.