What is the author trying to explain here?

Question

From Aaronson's 2006 lecture notes for PHYS$771$:

... Why the Incompleteness Theorem doesn't contradict the Completeness Theorem? The easiest way to do this is probably through an example. Consider the "self-hating theory" PA+Not(Con(PA)), or Peano Arithmetic plus the assertion of its own inconsistency. We know that if PA is consistent, then this strange theory must be consistent as well -- since otherwise PA would prove its own consistency, which the Incompleteness Theorem doesn't allow. It follows, by the Completeness Theorem, that PA+Not(Con(PA)) must have a model. But what could such a model possibly look like? In particular, what you happen if, within that model, you just asked to see the proof that PA was inconsistent?

I'll tell you what would happen: the axioms would tell you that proof of PA's inconsistency is encoded by a positive integer X. And then you would say, "but what is X?" And the axioms would say, "X." And you would say, "But what is X, as an ordinary positive integer?"

"No, no, no! Talk to the axioms."

"Alright, is X greater or less than 10^500,000?"

"Greater." (The axioms aren't stupid: they know that if they said "smaller", then you could simply try every smaller number and verify that none of them encode a proof of PA's inconsistency.)

"Alright then, what's X+1?"

"Y."

And so on. The axioms will keep cooking up fictitious numbers to satisfy your requests, and assuming that PA itself is consistent, you'll never be able to trap them in an inconsistency. The point of the Completeness Theorem is that the whole infinite set of fictitious numbers the axioms cook up will constitute a model for PA -- just not the usual model (i.e., the ordinary positive integers)! If we insist on talking about the usual model, then we switch from the domain of the Completeness Theorem to the domain of the Incompleteness Theorem.

1. What is meant by "self-halting theory"? And how is PA+Not(Con(PA)) consistent?
2. What is the author trying to say by the fictitious number argument where Axioms respond by saying X, etc. Why would I want to ask to see the proof of PA's inconsistency?

Answer 1

Throughout I'll assume that $\mathsf{PA}$ is consistent.

---

Re: (1):

"Self-halting theory" is just a bit of colorful language. "Self-doubting" would be more appropriate in my opinion (or maybe "halting" is a typo for "hating"?). Regardless, it's not worth focusing on.

The real question is why $\mathsf{PA+\neg Con(PA)}$ is consistent. This is a beautiful consequence of the second incompleteness theorem:

• If $\mathsf{PA+\neg Con(PA)}\vdash\perp$, the deduction theorem would give us $\mathsf{PA}\vdash \neg \mathsf{Con(PA)}\rightarrow\perp$, or equivalently $$\mathsf{PA}\vdash\neg (\neg \mathsf{Con(PA))}.$$

• But that's just a funny way of saying "$\mathsf{PA}\vdash \mathsf{Con(PA)}$." And we know that can't happen, by Godel, unless $\mathsf{PA}$ is inconsistent.

Put another way, "$T$ doesn't prove $A$" is always equivalent to "$T+\neg A$ is consistent." Here we're using $T=\mathsf{PA}$ and $A=\mathsf{Con(PA)}$.

---

Re: (2):

The point is that the completeness theorem (not a typo - quite different from the incompleteness theorem, the terminology overlap is quite unfortunate) says that any consistent theory has a model. In particular, per the section above the theory $\mathsf{PA+\neg Con(PA)}$ must have a model, $M$.

At first glance this seems weird: $M$ must think that part of its own behavior is contradictory! Personally I think this is very worth looking into ("Why would I want to ask to see the proof of PA's inconsistency?"), and the corresponding portion of the argument simply seeks to demystify it.

The punchline of course is that $\neg\mathsf{Con(PA)}$ is an existential statement, and the things in $M$ which ($M$ thinks) witness the truth of this statement are not actually standard natural numbers (that is, not in the range of the unique embedding $\mathbb{N}\rightarrow M$). So there's no contradiction between $M$ thinking that there is a number coding a contradiction in $\mathsf{PA}$, and there not actually being such a number in reality.

Answer 2

1. "Self-hating" theory is just the author's whimsical term for a theory like $\mathrm{PA} + \lnot(\mathrm{Con}(\mathrm{PA}))$ that asserts the inconsistency of one of its subtheories. If $\mathrm{PA} + \lnot\mathrm{Con}(\mathrm{PA})$ were inconsistent, we could derive a contradiction from $\mathrm{PA} + \lnot\mathrm{Con}(\mathrm{PA})$, which would mean that $\mathrm{PA}$ would be able to prove $\mathrm{Con}(\mathrm{PA})$, contradicting the second incompleteness theorem. (I am assuming throughout that $\mathrm{PA}$ is actually consistent.)
2. The second point is that as we now know that $\mathrm{PA} + \lnot\mathrm{Con}(\mathrm{PA})$ is consistent, the completeness theorem tells us that it must have a model. It is then surely natural to wonder what that model could look like. It is not hard to see that any model of a theory that extends $\mathrm{PA}$ includes a copy of the natural numbers with the usual arithmetic operations - let's call the numbers in that copy the standard natural numbers. But what $\lnot\mathrm{Con}(\mathrm{PA})$ actually says is that there is a number $X$ that encodes a proof of $0 \neq 0$. That number can't be a standard natural number, otherwise it would encode a proof in $\mathrm{PA}$ of $0 \neq 0$. So we conclude, working back through the definition of $\mathrm{Con}$, that the model includes a host of non-standard natural numbers which conspire to give the illusion that $0\neq 0$ has a proof.