Godel’s incompleteness theorem deals with “first order logic”, so it’s worth a post explaining what that is. In particular, we will distinguish it from zeroth order logic as well as from second and higher order logics.

What distinguishes these levels of logic from one another is what they’re allowed to quantify over. The two most common quantifiers are the symbols \(\forall\) which stands for “for all” and \(\exists\) which stands for “there exists”. One might use these quantifiers to make a statement like so:

\[\forall x ((Prime(x) \land x > 2) \supset Odd(x))\]

which is a formal way of stating that all primes greater than 2 are odd. If I translated this formula into a sentence, it would read: “for all \(x\), if \(x\) is prime and \(x\) is greater than 2, then \(x\) is odd”. I’m assuming I’ve already defined the \(Prime\) and \(Odd\) properties elsewhere, but you get the idea.

When we quantify over variables (\(x\) in this case), we first need to specify the domain over which these variable can range. Maybe the domain of \(x\) is the natural numbers, maybe it’s the real numbers, or maybe it’s something altogether different like colors. I can quantify over colors. There exists a color \(x\) that I like more than red. QED.

Let’s say that we’ve specified the domain is the natural numbers, as Godel did.

Zeroth order logic is not allowed to quantify over the domain at all. By the way, propositional logic is another name for zeroth order logic.

First order logic is allowed to quantify over individuals of the domain (e.g. over natural numbers). The statement I made above about primes is a statement of first order logic in that \(x\) is to be interpreted as a natural number.

Second order logic is allowed to quantify over sets of the domain. Recall that a property of the natural numbers can be thought of as the set of numbers which have that property. So, the ability to quantify over sets gives one the ability to quantify over properties (or relations, more generally). Here is a statement that requires second order logic:

\[\exists P. P(5) \land P(7)\]

In words, there exists a property \(P\) such that both \(5\) and \(7\) have the property \(P\). Maybe \(P\) is the property of being odd, or the property of being prime, or the property of being less than 10, … the list can go on.

Higher order logics: You can extend this pattern to higher order logics. Third order logic can quantify over sets of sets… and so on.