Logic – Why Gödel’s Incompleteness Theorem Applies to ZFC

incompletenesslogic

Okay, so I'm reading Smullyan's book on Gödel's incompleteness theorems, and I've just about finished the part where he shows that Peano arithmetic is incomplete using Tarski's truth set (chapter IV).

My only issue is that I cannot see how this applies directly to any axiom system apart from that specific variant of P.A.. The proof relies heavily on the symbols used and seems a far cry from the (badly quoted) "Any system capable of expressing P.A. is incomplete".

Why does this proof of the incompleteness of a very particular axiom system have any bearing upon other systems which could subsume it? I can see how I could modify the proof to apply the theorem to ZFC, perhaps, but I see nothing general here. Is this some theorem of logic that has not been mentioned?

Best Answer

See Gödel's Incompleteness Theorems.

"Preliminary" formulation :

First incompleteness theorem : Any consistent formal system $F$ within which a "certain amount of elementary arithmetic" can be carried out is incomplete; i.e., there are statements of the language of $F$ which can neither be proved nor disproved in $F$.

Precise formulation :

Gödel's First Incompleteness Theorem : Assume $F$ is a formalized system which contains Robinson arithmetic $\mathsf Q$. Then a sentence $G_F$ of the language of $F$ can be mechanically constructed from $F$ such that:

If $F$ is consistent, then $F ⊬ G_F$.

If $F$ is $1$-consistent, then $F ⊬ ¬G_F$.

$\mathsf {ZFC}$ is precisely such a formalized system $F$ (i.e. "a formal system within which a 'certain amount of elementary arithmetic' can be carried out").


Gödel's original proof in his Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I ("On Formally Undecidable Propositions of Principia Mathematica and Related Systems I") does not use $\mathsf {ZFC}$ nor $\mathsf {PA}$.

His proof is relative to a "variant" of Principia Mathematica system; but his proof - in addition to esatblish the result now know as Gödel's Incompleteness Theorems - provides also a method applicable to many formal systems, provided that they satisfy some "initial conditions".

All the systems known as $\mathsf Q, \mathsf {PA}, \mathsf {ZFC}$ satisfy these conditions.


Relevant to your question, you can see :

It can be interesting to note that Melvin Fitting's thesis advisor was Raymond Smullyan.