Gödel' Incompleteness Theorem (GIT) states that certain theories $T$ (formal systems that are of sufficient complexity to express the basic arithmetic of the natural numbers and which are consistent, and effectively axiomatized) e.g. Peano Arithmetic, are incomplete, i.e. there are statements $S_k$ that can't be proven right or wrong within the theory, by which I mean composing the axioms of the theory.

The way out is to accept the unprovable statement $S_1$ either as true or false, which by GIT leads to another theory that is again incomplete. In fact even two theories! Let's choose "false" for the moment and I'll write $\lnot S_1$ for that. If we go on (turning coffee into theorems), we'll reach the next unprovable statement $S_2$ (which might depend on $S_1$ being false) and are left with another decision, whether to accept this as true or false. Now we already have five(!) theories:

  • $T_0$
  • $T_0\cup\{S_1\}$
  • $T_0\cup\{\lnot S_1)\}$
  • $T_0\cup\{\lnot S_1,S_2\}$
  • $T_0\cup\{\lnot S_1,\lnot S_2\}$

This approach can be continued. Our resulting (incomplete) theory is described by a sequence of unprovable, but as true or false accepted, statements. Properly arranged this looks like a tree graph.

What is known about this tree? Does it have loops? (No loops, see Alex' comments)

I'm also looking for references...

  • $\begingroup$ "What is known about this tree?" Isn't it obviously just a complete binary tree? By asking about loops, I guess you're wondering if two theories in the tree might be equivalent? The answer is no, since every node in the tree is a consistent theory, and given any two theories $T$ and $T'$ in the tree, either one properly extends the other (i.e. $T'$ is below $T$ in the tree, so it contains a sentence which is not provable from $T$), or $T$ and $T'$ disagree about the truth of some sentence (the sentence $S$ chosen by incompleteness for the greatest common ancestor of $T$ and $T'$ in the tree). $\endgroup$ – Alex Kruckman Jan 23 at 19:52
  • $\begingroup$ @AlexKruckman what about a theory that has two unprovable statements, and accepting the first also proves the second, but denying it has no consequence on the second. Is this possible? If, then the binary tree wouldn't be complete... $\endgroup$ – draks ... Jan 23 at 20:02
  • $\begingroup$ Oh, maybe I misunderstood how you are constructing the tree. I thought you picked $S_2$ (in the example in your question) to be independent from $T_0\cup \{\lnot S_1\}$. Then in the other branch, you would pick a sentence $S_2'$ independent from $T_0\cup \{S_1\}$, giving 4 theories: $T_0\cup \{S_1,S_2'\}$, $T_0\cup \{S_1, \lnot S_2'\}$, $T_0\cup \{\lnot S_1, S_2\}$, and $T_0\cup \{\lnot S_1, \lnot S_2\}$. $\endgroup$ – Alex Kruckman Jan 23 at 20:05
  • 4
    $\begingroup$ If instead you start with some fixed enumeration $S_1, S_2, S_2, \dots$ of sentences independent of $T_0$, then the structure of the tree will of course depend heavily on the particular enumeration of the $S_n$. $\endgroup$ – Alex Kruckman Jan 23 at 20:06
  • $\begingroup$ @Alex do you think the case of Peano arithmetics is properly invertigated? Any idea where to look? $\endgroup$ – draks ... Jan 24 at 22:11

Your Answer

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

Browse other questions tagged or ask your own question.