What Does Gödel's Incompleteness Theorem Say?

If you are to use first-order logic to represent some declarative information, you must settle on your domain, and on some set of key symbols, that is, your relation symbols (which denote relations or properties), function symbols (for denoting functions), and constants (which are like names; they pick out individual objects directly). For example, if your task is to represent romantic facts about the domain of people, including, specifically, Alice and Bertrand, and the fathers of both of them, you might decide to use

• the relation symbol L for `loves,' so that Lxy indicates that x loves y;
• the constants a and b to refer to Alice and Bertrand, respectively;
• the function symbol f to denote the father-of function.³

Given this symbol set, {L, f, a, b}, you are able to pick out individual things in the domain in question by way of what are called terms (e.g., a is a term, as are: f(a), f(f(a)), b, f(b)), and you can create formulas to say such things as the following:

English	Formulas in FOL
Alice loves Bertrand.	Lab
Alice loves Bertrand's father.	Laf(b)
Alice loves everyone.	$\forall x Lax$
Bertrand loves those who love Alice's father.	$\forall x (Lxf(a) \rightarrow Lbx)$
People who love themselves are not loved by Alice.	$\forall x (Lxx \rightarrow \neg Lax)$
Someone is loved by both Alice and Bertrand.	$\exists x (Lax \wedge Lbx)$

In the case of Gödel I, the domain is the natural numbers N = {0, 1, 2, $\ldots$}, and the symbol set in question is one configured for simple arithmetic, viz., $S_{ar}^< = \{+, \times, 0, 1, <\}$. With this symbol set we can make assertions about arithmetic, such as that ``Every number multiplied by one returns itself" ( $\forall x x \times 1 = x$), and ``There is no greatest number" ( $\neg \exists x \forall y y < x$). What Gödel astonishingly showed is that given a set $\Phi$ of formulas about arithmetic (i.e., Phi is an S_ar^;SPMlt; formula) that meets three particular conditions, there is a formula about arithmetic, $\phi_g$, which is such that neither it nor its negation can be proved from $\Phi$. The three particular conditions are that $\Phi$ must be (i) consistent (i.e., for now, no contradiction can be derived from $\Phi$), (ii) decidable (which, for now, amounts to: an ordinary computer program exists which decides, for an S_ar^;SPMlt; formula $\psi$, whether or not $\psi \in \Phi$), and (iii) representable (or just `Rep' for short). These three conditions are explained in model-based fashion in the next section. For now, you can rely on your intuitive understanding of the parenthetical explanations of (i) and (ii), and (iii) may be provisionally understood to mean that $\Phi$ can be used to perfectly model the operation of any ordinary computer program. So we have:

Theorem 1 (Gödel I)   Suppose that $\Phi$ is consistent and decidable, and that Rep $\Phi$ as well. Then there is an S_ar-sentence $\phi_g$ such that neither $\Phi \vdash \phi_g$ nor $\Phi \vdash \neg\phi_g$.