Boolos’s proof of the first incompleteness theorem. Predicate $C(x,y)$ and assumption of completeness.

Question

I am trying really hard to understand how Boolos’s proof works, but I keep having doubts about it. Can you spot any logical flaws in my reasoning? This question arose from a previous question, but it is different from it as a consequence of things that were explained to me in response to such previous question.

The first incompleteness theorem states that any consistent theory is not complete. In other words, stated very naively, the result of the proof is: ¬(“true” ↔ “provable”). To avoid making a circular argument, the assumption about the theory that carries out our proof must be “true” ↔ “provable”. If our theory starts with this assumption, it seems to me that it can be showed $C(x,y) → ¬C(x,y)$ and therefore $¬C(x,y)$ can be proved by contradiction (with $C(x,y)$ being the predicate found in Boolos's proof). The reason for this is it seems to me that assuming $C(x,y)$ true allows you to prove both $∃n(∀(()↔=[]))$ and $¬∃n(∀(()↔=[]))$.

$∃n(∀(()↔=[]))$ has to be proved as part of Boolos’s proof (it is asserted to be true along the proof). From the assumption “true” ↔ “provable”, ¬∃n(∀(()↔=[])) can be deduced in a few mechanical steps. If the implication $(∀(()↔=[]) → ¬∀(()↔=[]))$ is true then we also have $¬∃n(∀(()↔=[]))$. It can be seen easily by rewriting $∀(()↔=[])$ as $J(n)$ and using proof by contradiction $(J(n) → ¬J(n)) → ¬J(n)$ and the generalisation inference rule $J(n) → ∀nJ(n)$. Then just substitute $¬∃n¬$ with $∀n$ (they are syntactically the same) to get $∀n¬J(n) ↔ ¬∃n¬¬J(n) ↔ ¬∃nJ(n) ↔ ¬∃n(∀(()↔=[n]))$.

Now, how can we show the implication $(∀(()↔=[]) → ¬∀(()↔=[]))$ to be true? We see that $∀(()↔=[])$ implies $A(n,m)$. Let’s say $F(x)$ is d symbols long, with d<m by construction ($m = 10k$ and $d = 2k + 24$ in Boolos’s proof). We also have $A(n,m) → ¬(C(n,y) ∧ (y<m)) → ¬C(n,d) → ¬∀(()↔=[n])$.

An objection could be: $¬C(n,d)$ just implies that there is no proof for $∀(()↔=[n])$, it does not imply $¬∀(()↔=[n])$. But if we have to start with the assumption “true” ↔ “provable” we can deduce these two things are exactly the same.

So to summarise, it seems to me that starting by the assumption that your theory is consistent and complete, $¬C(x,y)$ is proved by showing $C(x,y)$ leads to contradiction. Therefore to me it looks like Boolos’s proof cannot be carried out if you start from these assumptions. But these are the assumptions you have to start from to avoid making a circular argument.

Answer 1

IMO the issue is with your use of formula $F(x)$.

According to Boolos' definition,

"a formula $F(x)$ names a number $n$ if the statement $\forall x (F(x) \leftrightarrow x=[n])$ (where $[n]$ is $ss \ldots s0$, with $n$ times $s$) is in the output of algorithm $M$."

Boolos says (page 386): "$n$ is not named by $F$; in other words, $\forall x (F(x) \leftrightarrow x=[n])$ is not in the output of $M$."

You are switching from "$\forall x (F(x) \leftrightarrow x=[n])$ is not in the output of $M$" to "$\lnot \forall x (F(x) \leftrightarrow x=[n])$ is in the output of $M$."

But this is what we are trying to prove: that the system is (negation) complete:

for each sentence (closed formula) $\phi$ of the language of the system either $\phi$ or $¬ \phi$ is a theorem (an output) of the system.

Thus, if $\phi$ is not an output of the system, then $\lnot \phi$ must be.

But this is exactly what $\mathsf {PA}$ is not: it is (negation) incomplete.

See page 383:

a new proof of the Gödel incompleteness theorem in the form: There is no algorithm whose output contains all true statements of arithmetic and no false ones.

And page 384:

if there were an algorithm that printed out all and only [emphasis added] the true statements of arithmetic...

This is the crux of the matter: from the fact that $\forall x (F(x) \leftrightarrow x=[n])$ is not in the output of $M$ we cannot conclude that $\lnot \forall x (F(x) \leftrightarrow x=[n])$ is the output of $M$.