Category Archives: logic.2013

Turing Machines

An algorithm must be seen to be believed. –Donald Knuth In the age defined by computing, we are apt to forget that the quest to solve mathematical problems algorithmically, by a mechanical procedure terminating in finitely many steps, dates back … Continue reading

Posted in logic.2013 | Leave a comment

Tennenbaum’s Theorem

Gödel’s Incompleteness Theorems established two fundamental types of incompleteness phenomena in first-order arithmetic (and stronger theories). The First Incompleteness Theorem showed that no recursive axiomatization extending ${\rm PA}$ can decide all properties of natural numbers and the Second Incompleteness Theorem … Continue reading

Posted in logic.2013 | Leave a comment

The Second Incompleteness Theorem

There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable. There is another theory … Continue reading

Posted in logic.2013 | Leave a comment

The First Incompleteness Theorem

Some people are always critical of vague statements. I tend rather to be critical of precise statements; they are the only ones which can correctly be labeled ‘wrong’. –Raymond Smullyan At the dawn of the $20^{\text{th}}$-century formal mathematics flourished. In … Continue reading

Posted in logic.2013 | Leave a comment

Recursive Functions

To understand recursion, you must understand recursion. In his First Incompleteness Theorem paper, Gödel provided the first explicit definition of the class of primitive recursive functions on the natural numbers ($\mathbb N^k\to\mathbb N$). Properties of functions on the natural numbers … Continue reading

Posted in logic.2013 | Leave a comment

Models of Peano Arithmetic

…it’s turtles all the way down. In 1889, more than two millennia after ancient Greeks initiated a rigorous study of number theory, Guiseppe Peano introduced the first axiomatization for the theory of the natural numbers. Incidentally, Peano is also famous … Continue reading

Posted in logic.2013 | Leave a comment

The Completeness Theorem

The Completeness Theorem was proved by Kurt Gödel in 1929. To state the theorem we must formally define the notion of proof. This is not because it is good to give formal proofs, but rather so that we can prove … Continue reading

Posted in logic.2013 | Leave a comment