Course MAT509

Topics in Logic and Foundations: Computational Complexity

The focus of the course will be consistency proofs.

Discussion of why Gödel's second incompleteness theorem does not preclude a finitary consistency proof for Peano Arithmetic (PA).

A finitary consistency proof for PA.

Critique of finitism.

Construction of Polynomial Time Arithmetic (PTA), weaker than Primitive Recursive Arithmetic.

Some polynomial time consistency proofs.