4
$\begingroup$

Ebbinghaus' Mathematical Logic on p184

7.8 Gödel's First Incompleteness Theorem. Let $\Phi$ be consistent and R-decidable and suppose $\Phi$ allows representations. Then there is an $S_{ar}$- sentence $\phi$ such that neither $\Phi \vdash \phi$ nor $\Phi \vdash \neg \phi$.

p185

7.10 Gödel's Second Incompleteness Theorem. Let $\Phi$ be consistent and R-decidable with $\Phi \supset \Phi_{PA}$. Then $$ \text{not} \quad \Phi \vdash Consis_\Phi.$$

On the relation between the two theorems, p184 says

A refinement of the above argumentations (in Godel's first Incompleteness Theorem) leads to results concerning the consistency of mathematics. In particular, Godel's Second Incompleteness Theorem, which we shall now derive, shows that the consistency of a suffi- ciently rich system cannot be proved using only the means available within the system.

and https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Second_incompleteness_theorem says

This theorem (Godel's second incompleteness theorem) is stronger than the first incompleteness theorem because the statement constructed in the first incompleteness theorem does not directly express the consistency of the system. The proof of the second incompleteness theorem is obtained by formalizing the proof of the first incompleteness theorem within the system F itself.

I have trouble understanding the relation between the two theorems in the above sources.

Does the first theorem roughly say that if a set of sentences can represent all the computable functions, the deductive theory derived from the set can't have both proof consistency and proof completeness: either one of them, or neither?

Does the second theorem say almost the same as the first theorem, except that while the first theorem does not give a specific sentence which can be neither proved nor disproved from the set, the second theorem provides $Consis_\Phi$ as such a sentence?

Does the second theorem imply the first?

$\endgroup$
3
  • $\begingroup$ Good question, I don't understand the votes. $\endgroup$
    – user400188
    Mar 13, 2021 at 5:29
  • 2
    $\begingroup$ @user400188 the OP is suspended for a year and used a sockpuppet to ask the question while suspended - this was discovered, and the accounts merged. My guess would be that voters are reacting to the gaming of the system more than the content of the post. $\endgroup$
    – KReiser
    Mar 13, 2021 at 8:16
  • 3
    $\begingroup$ I’m voting to close this question: Because it was asked by a sockpuppet of this account, Tim's sock puppet, during his suspension first earned in Jan 2021, and now extended to March 13th 2022 for having attempted to use another account to ask questions during his first year long suspension. $\endgroup$
    – amWhy
    Mar 14, 2021 at 16:43

1 Answer 1

4
$\begingroup$

Does the first theorem roughly say that if a set of sentences can represent all the computable functions, the deductive theory derived from the set can't have both proof consistency and proof completeness: either one of them, or neither?

Sure, that's one way to think about it (though you left out the crucial assumption that the set of sentences should also be decidable).

Does the second theorem say almost the same as the first theorem, except that while the first theorem does not give a specific sentence which can be neither proved nor disproved from the set, the second theorem provides $Consis_\Phi$ as such a sentence?

Not quite. The second theorem provides $Consis_\Phi$ as a sentence that cannot be proved from $\Phi$. However, it's possible that $Consis_\Phi$ could be disproved from $\Phi$. Intuitively, this means that "$\Phi$ proves its own inconsistency". You might think that this means $\Phi$ must be inconsistent (contrary to the assumption that it was consistent), but that's not necessarily the case--the sentences that $\Phi$ proves don't necessarily have to be true (when interpreted in the natural numbers). For instance, if you start with a set of sentences $\Phi$ and then let $\Phi'=\Phi\cup\{\neg Consis_\Phi\}$, then $\Phi'$ proves $\neg Consis_\Phi$ and thus also $\neg Consis_{\Phi'}$. But $\Phi'$ is still consistent, exactly because $\Phi$ did not prove $Consis_\Phi$, so adding its negation to the theory does not lead to a contradiction.

Does the second theorem imply the first?

No, as explained above. The second theorem implies a weaker version of the first where you add an additional assumption that implies $\Phi$ does not prove its own inconsistency. For instance, you could assume that every sentence in $\Phi$ is actually true when interpreted in the natural numbers, and so $\Phi$ cannot prove any false statement about the natural numbers. In particular, since $\neg Consis_\Phi$ is false (i.e., $\Phi$ is not actually inconsistent), this means $\Phi\not\vdash \neg Consis_\Phi$.

$\endgroup$
3
  • $\begingroup$ (1) "that's one way to think about it". Can you give a way that is most natural to you for the meaning of the first theorem? (2) Can you give a way to think about the second theorem, as close to the first theorem as possible? So I can see what they have in common? $\endgroup$
    – Tim
    Mar 10, 2021 at 18:15
  • 1
    $\begingroup$ Then why the heck are you answering, @Noah, when you know the account was a sockpuppet to a suspended user? And you nor Eric had the integrity to delete your answers?? $\endgroup$
    – amWhy
    Mar 12, 2021 at 22:24
  • 1
    $\begingroup$ @amWhy Fine, whatever. $\endgroup$ Mar 12, 2021 at 22:59

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.