Toward a Model-Based Proof of Gödel I

Given the foregoing, we can re-express Gödel I in model-based terms that make the theorem much easier to understand. (Readers are encouraged to return to the presentation of the theorem above, and to read it again, but this time with the model-based explanations firmly in mind $\ldots$ Back? Now the theorem should make some real sense to you, even if you're new to it.) But what about proving Gödel I? Well, as I said earlier, proving Gödel I herein would make this paper too long, and too technical. But rest assured that a model-based proof can be given; it's how I and others across the globe teach Gödel I (and, for that matter, Gödel's second incompleteness theorem as well), and it's how Gödel himself pondered and eventually established his famous result. (Readers interested in the ``model-based" mind of Gödel himself are encouraged to read [18] for a marvelous introduction, delivered by Gödel's friend Hao Wang.) Let me give a brief sample that trades on the model-based elements introduced above.

Chapter 51 of the second book of Cervantes' immortal Don Quijote is Gödel's key move in a nutshell. Sancho Panza is governor of an island and must preside as judge over some rather tough cases, one of which is presented to him as follows:

My lord [Sancho Panza], a broad river separates the two parts of a single domain $\ldots$ Now, there's a bridge over this river, and at one end there stands a gallows and a court building, in which four judges usually preside, applying the law formulated by the lord of this river, this bridge, and this entire realm, which runs as follows: ``Anyone passing over this bridge, from one section of this domain to the other, must first declare under oath where he is coming from and where he is going, and if he swears truly, he shall be allowed to pass, but if he lies, he shall be hanged from the gallows standing nearby, without any appeal or reprieve allowed." $\ldots$ Well, it happened, one day, that a man came and swore the required oath, saying among other things that he had come to be hanged on that gallows, and for no other purpose. The judges considered his oath, saying: ``If we simply let this man cross the bridge, his oath will be a lie, and then, according to the law, he ought to die, but if we hang him, the oath he swore about being hanged on this gallows will be true, and then the same law decrees that he be allowed to cross over in peace." Please consider, my lord governor, your grace, what the judges should do with this fellow, for even now they remain anxious and unsure how to proceed, and, having been made aware of your grace's keen mind and sublime understanding, they have sent me to implore your grace to tell them how you view this singularly complicated and puzzling case. ([9], 629)

Now I know that you, reader, are blessed with wisdom well beyond what Sancho Panza and even his noble friend Don Quijote wielded, but I doubt that you can fare any better than Sancho in judging the following case, which I unblushingly confess has driven my brain dizzy, with no verdict forming therein, let alone forthcoming. Of course, this is the famous Liar Paradox in narrative form. Gödel found a way to turn it to his advantage.

A streamlined version of the paradox runs as follows. Is the following sentence true or false?

$$\mbox{This sentence is false.}$$

If this sentence is true, then since it says it's false, it is false. If, on the other hand, this sentence is false, then since that's what it says, it's true. So it's true if and only if it's false, an outright contradiction.

All this is perhaps interesting, but how does the paradox help establish anything relevant to Gödel I? And how is it to work in model-based fashion? Well, here's a way to make the connection:⁵ Return to our monkey, and recall that he leaves output for us on the railroad tape when he is finished. Let us imagine that the monkey can thus be said to print things for us. To simplify things, let's give the monkey the alphabet

$$\neg \: P \: N \: 1 \: 0$$

with which to work (rather than S_ar from above), and let's set up a streamlined system for the monkey to obtain Gödel numbers, and to move from such numbers to formulas. Specifically, let's have him identify natural numbers with their correlates in binary notation through the following table.

$\neg$	P	N	1	0
10	100	1000	10000	100000

For example, P N N P has the Gödel number 10010001000100. Let's say the norm of an expression is that expression followed by the Gödel number of that expression obtained by the monkey. So sticking with our example, the norm of P N N P is P N N P 10010001000100. Next, let's stipulate that a formula is an expression having one of the four forms P X, P N X, $\neg P X$, and $\neg P N X$, where X is any number in binary. We also say the following.

• P X is true if and only if X is the Gödel number of an expression that the monkey can print.
• P N X is true if and only if X is the Gödel number of an expression whose norm is printable by the monkey.
• $\neg P X$ is true if and only if P X is not true.
• $\neg P N X$ is true if and only if P N X is not true.

If we assume that our monkey never prints a false sentence, can we find a true sentence that he cannot print? If so, we will have found something perfectly analogous to the formula $\phi_g$ in Gödel I. There is such a sentence: $\neg P N 101001000$. Here's the ``Liar-like" proof: We know that $\neg P N 101001000$ is true if and only if P N 101001000 is not true, i.e., if and only if 101001000 is the Gödel number of an expression whose norm is not printable by the monkey. But 101001000 is the Gödel number of $\neg P N$, and the norm of $\neg P N$ is $\neg P N 101001000$ itself! So $\neg P N 101001000$ is true if and only if it's not printable by the monkey. This implies that either $\neg P N 101001000$ is true and not printable, or is printable and not true. Since by hypothesis the monkey never prints out untrue formulas, the formula is true and not printable.

What about more precise uses of the Liar? I end this section by giving a more careful version of the core reasoning behind Gödel I.

First, recall some simple propositional logic: If you can prove a biconditional expression p if and only if q (= $p \leftrightarrow q$), and you can prove p, you can chain from left to right across the biconditional to obtain q. And if you have proved a biconditional p if and only if q, as well as that p is false, i.e., $\neg p$, you can safely infer to $\neg q$.

Now, assume that we have previously proved that for every property F that can be expressed of a constant in first-order logic, there is a sentence $\phi$ that is true exactly when the Gödel number of $\phi$ has F, and that this fact can be proved from the set $\Phi$ referenced in the hypothesis of Gödel I. (Remember that the Gödel number of $\phi$ is written $n^\phi$.) That is,

$$(1) \hspace{.5in} \Phi \vdash \phi \leftrightarrow Fn^\phi$$

Now let F be the property `is provable from $\Phi$,' denoted by F^p. So we can move to

$$(2) \hspace{.5in} \Phi \vdash \phi \leftrightarrow \neg F^pn^\phi$$

Now, suppose that $\phi$ is provable from $\Phi$, i.e., $\Phi \vdash \phi$. Then from this together with (2) it follows that $\Phi \vdash \neg F^pn^\phi$, which is to say that $\phi$ is not provable -- contradiction. Suppose on the other hand that $\neg \phi$ is provable from $\Phi$; then from this and (2) it follows that $\Phi \vdash F^pn^\phi$, which is to say that $\phi$ is provable from $\Phi$ -- contradiction again! So it follows that $\phi$ is not provable from $\Phi$, and neither is $\neg \phi$ provable.