17
$\begingroup$

For the proof of Gödel's Incompleteness Theorem, most versions of proof use basically self-referential statements.

My question is, what if one argues that Gödel's Incompleteness Theorem only matters when a formula makes self-reference possible?

Is there any proof of Incompleteness Theorem that does not rely on self-referential statements?

$\endgroup$
  • 2
    $\begingroup$ There are statements that have no hint of self-reference that have been proved to be independent of this or that axiom system, so that very important consequence of the Incompleteness Theorem doesn't rely on self-referential statements. $\endgroup$ – Gerry Myerson Jul 17 '12 at 9:20
  • $\begingroup$ There are non-constructive versions of the incompleteness theorems that do not use self-referential statements, simply because they do not even construct any. However, the proofs themselves still use diagonalization. $\endgroup$ – user21820 Apr 11 '17 at 4:38
25
$\begingroup$

Roughly speaking, the real theorem is that the ability to express the theory of integer arithmetic implies the ability to express formal logic.

Gödel's incompleteness theorem is really just a corollary of this: once you've proven the technical result, it's a simple matter to use it to construct variations of the Liar's paradox and see what they imply.

Strictly speaking, you still cannot create self-referential statements: the (internal) self-referential statement can only be interpreted as such by invoking the correspondence between external logic (the language in which you are expressing your theory) and internal logic (the language which your theory expresses).

| cite | improve this answer | |
$\endgroup$
  • 10
    $\begingroup$ The last paragraph here is quite important: The Gödel sentence doesn't know it is speaking about itself; we have to conclude that looking at the formal system from the outside. $\endgroup$ – hmakholm left over Monica Jul 17 '12 at 10:56
7
$\begingroup$

There is a rather pretty proof of a standard version of Gödel's First Theorem by Kleene, that extracts it as a corollary of his (Kleene's) Normal Form Theorem. The proof involves diagonalization, but not self-reference. There's a two-page exposition here: http://www.logicmatters.net/resources/pdfs/KleeneProof.pdf

There are two further elementary proofs which don't involve self-reference, whose conclusions are something-a-bit-less-than the full Gödelian result, in Chs 6 and 7 of the second edition of my Gödel book.

Again, both those arguments involve diagonalization. It is diagonalization rather than self-reference which might reasonably be said to be characteristic of typical (though not all) incompleteness proofs.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Your email address on your site is quite ambiguous. What does "me" mean there? $\endgroup$ – Asaf Karagila Apr 25 '13 at 17:32
  • $\begingroup$ me.com means me.com :-) [you obviously aren't an Apple fanboy, Asaf ...] $\endgroup$ – Peter Smith Apr 25 '13 at 17:35
  • $\begingroup$ I rue the day I got an iPhone and became enslaved to the loathed iTunes! $\endgroup$ – Asaf Karagila Apr 25 '13 at 17:41
  • $\begingroup$ Anyway, prepare to be emailed! (Insert dramatic chord here) $\endgroup$ – Asaf Karagila Apr 25 '13 at 18:14
  • $\begingroup$ The Kritchman-Raz paper gives proofs using Kolmogorov complexity that don't use diagonalization or self-reference. $\endgroup$ – Jori Jul 2 at 0:27
2
$\begingroup$

There is a weaker version of the first incompleteness theorem that is an almost trivial consequence of an insight from computability theory, namely of the result that

  there exists a computably enumerable set that is not computable   (*).  

Consequence: the set of true first-order sentences (i.e. true about the 'real' natural number sequence) is not axiomatizable by a c.e. axiom set.

Unfortunately, most proofs of ($*$) have themselves a scent of self-referentiality hanging around them. However, you may want to check out 'simple sets'. Simple sets are c.e. and not recursive, and the standard textbook-proof of their existence is, to the best of my knowledge, the argument that comes closest to a non-selfreferential argument for ($*$).

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

There is this one, that I have heard of but not perused myself:

http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.ndjfl/1027953483&page=record

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

A low-level answer.
Gödel's own undecidable statement (it is now known from Julia Robinson etc.) can be of the form: "Here is a polynomial equation in many variables with integer coefficients. Does it have a solution in positive integers?" There is nothing self-referential about that. But we GOT that equation by coding something that Sarah considers to be self-referential into the polynomial.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Here's a direct computability-theoretic argument. Suppose $T$ is an "appropriate" theory. Let $A,B$ be two disjoint c.e. sets, and let $A_T=\{x: T\vdash x\in A\}$ and $B_T=\{x:T\vdash x\not\in A\}$. Each $A_T$ and $B_T$ is c.e. by definition; since $T$ is complete we have $A_T\sqcup B_T=\mathbb{N}$, and hence they're each computable; and since $T$ is "appropriate" we have $A\subseteq A_T$ and $B\subseteq B_T$. But this gives us a contradiction: just take $A,B$ to be a pair of computably inseparable c.e. sets.

Of course, how do we know that computably inseperable c.e. sets exist? Well, this in turn is a straightforward trick with a universal Turing machine: we set $$A=\{e:\varphi_e(e)\downarrow =0\}\quad\mbox{and}\quad B=\{e:\varphi_e(e)\downarrow=1\}.$$ By definition, $A$ and $B$ are disjoint c.e. sets (and note that if $\varphi_e(e)\uparrow$ then $e$ is not in $A$ or $B$).

Now suppose $C$ were a computable separator for $A$ and $B$; that is, $C$ is computable, $A\subseteq C$ and $B\cap C=\emptyset$. Let $\varphi_c$ be the total computable characteristic function of $C$ - that is, $$C=\{x:\varphi_c(x)\downarrow=1\}.$$ We now have two cases:

  • If $c\in C$, then $\varphi_c(c)=1$. But then we have $c\in B$, contradicting the assumption that $C\cap B=\emptyset$.

  • If $c\not\in C$, then $\varphi_c(c)=0$. But then we have $c\in A$, contradicting the assumption that $A\subseteq C$.

Note that crucially "$\varphi_c(c)\uparrow$" is not an option - since $\varphi_c$ is total.


There's no self-reference at all there: the closest we come is in the verification step of our construction of computably inseparable c.e. sets, but that's not actually self-reference (feeding an existing object its own "name" is different from building an object which somehow "knows its own name ahead of time"). This is exactly the diagonalization versus self-reference point.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ what do you mean by c.e and r.e $\endgroup$ – David Okogbenin Apr 13 at 17:36
  • $\begingroup$ @DavidOkogbenin "C.e." stands for "computably enumerable" (and "r.e." for "recursively enumerable" - they're synonymous, but I've edited so I only use one). There are many characterizations of c.e. sets; the one that's most useful here is probably "$X$ is c.e. iff for some $e$ we have $$X=\{n: \varphi_e(n)\downarrow=1\},$$ where $\varphi_e$ is the $e$th partial computable function according to some standard enumeration of such. $\endgroup$ – Noah Schweber Apr 13 at 18:01
  • $\begingroup$ Incidentally, you may also find this more broadly useful. $\endgroup$ – Noah Schweber Apr 13 at 18:04
  • $\begingroup$ Thank you. I am new to this so I’m not entirely clear. What is the difference between diagonalization and self-reference. When I read about it( and i did not understand all that I read though), it looked like the diagonalization(or the diagonal Lemma- i don’t think they’re the same thing) was a more subtle form of self reference. $\endgroup$ – David Okogbenin Apr 13 at 22:55
  • $\begingroup$ @DavidOkogbenin Think about infinite binary sequences for concreteness. Diagonalization can be applied to any array of infinite binary sequences: given such an array $D=(d_i)_{i\in\mathbb{N}}$ (so each $d_i$ is an infinite binary sequence), we get the "diagonal" sequence $n\mapsto d_n(n)$ (or if we prefer, we can get the "antidiagonal" sequence $n\mapsto 1-d_n(n)$). Note that a priori we don't care whether the sequence $e$ this produces is or is not one of the $d_i$s; for example, in Cantor's argument the conclusion is exactly that the antidiagonal sequence **is not** one of the "rows" of $D$. $\endgroup$ – Noah Schweber Apr 13 at 23:25

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.