3
$\begingroup$

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 10500,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?
$\endgroup$
4
  • 2
    $\begingroup$ You should cite the original source. $\endgroup$ Oct 24 at 20:59
  • $\begingroup$ I'd like the source for this too please, can you edit it into the question? $\endgroup$
    – Ten O'Four
    Oct 25 at 2:39
  • 1
    $\begingroup$ @TenO'Four I've gone ahead and edited in the source myself. To the OP, you should do this yourself in the future. $\endgroup$ Oct 25 at 3:40
  • $\begingroup$ @Noah Schweber, thanks 😊 $\endgroup$
    – Ten O'Four
    Oct 25 at 3:51
4
$\begingroup$

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.

$\endgroup$
17
  • $\begingroup$ Thanks for answering, can you recheck the last statement under Re: (1)? $\endgroup$
    – Ajax
    Oct 24 at 20:52
  • $\begingroup$ @Ajax Whoops, good catch, fixed. $\endgroup$ Oct 24 at 20:57
  • $\begingroup$ What is happening then? If these non-standard numbers do not exist in reality...what is the basis of there being "...no contradiction between 𝑀 thinking that there is a number coding a contradiction in 𝖯𝖠, and there not actually being such a number in reality" ...whatever "thinking" is supposed to mean here...? $\endgroup$
    – Ajax
    Oct 24 at 21:00
  • 1
    $\begingroup$ @Ajax Don't read too much into the word "thinking," it's just language I'm using to try to make things less confusing. Here's a concrete example of a simpler phenomenon: if we let $M$ be the ordered semiring of polynomials in one variable $\alpha$ with integer coefficients which (are zero or) have positive leading term, we get a model of Robinson arithmetic + $$(\dagger)\quad \exists x\forall y(y+y\not=x\wedge y+y\not=x+1)$$ (take $x=\alpha$). So this $M$ "thinks" that there is a number which is not even or odd. But of course, in reality (= $\mathbb{N}$) every number is even or odd. $\endgroup$ Oct 24 at 21:05
  • 3
    $\begingroup$ @Ajax "I don't know how to construct a question around that in Math.SE." ... OK? Why do you need to construct a question around that? For what it's worth, not every line of expository text needs systematic exegesis; the important point is the actual mathematics, and I would focus on understanding that rather than over-emphasizing the specific language used in explaining it. $\endgroup$ Oct 24 at 21:19
1
$\begingroup$
  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.
$\endgroup$
4
  • $\begingroup$ Let me ask...you use the word "conspire" only from our perspective...? That for model M, everything may mean entirely different....and perhaps not so controversial? $\endgroup$
    – Ajax
    Oct 24 at 21:05
  • $\begingroup$ By "conspire", I mean that the arithmetic on the non-standard numbers makes $X$ look like it encodes a finite set of valid inference steps that prove $0 \neq 0$. However, because $X$ is non-standard, if we tried to unwind the definitions of our encoding to find that finite set of inference steps, the process would never terminate. $\endgroup$
    – Rob Arthan
    Oct 24 at 21:16
  • $\begingroup$ ...but process would end, if say magically, I know the encoding for non-standard numbers...? $\endgroup$
    – Ajax
    Oct 24 at 21:18
  • $\begingroup$ No the process would not end: if it did, $X$ must have been standard to start with. Note the encoding I am talking about is the encoding of proofs as numbers, as used to define the predicate $\mathrm{Con}$. For a given model, the process I am talking about is fully determined: there is nothing that any magical extra information could do to make it terminate. $\endgroup$
    – Rob Arthan
    Oct 24 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.