Just a simple question about Godel incompleteness: suppose you have a certain statement $p$ that can't be proved in a formal system $S$ but it can be proved in another ("superior"?) system $S'$.In that case what is the relation between $S$ and $S'$? I mean, does $S'$ contain all the axioms and theorems of $S$ plus extra ones or not necessarily?


Not necessarily.

For example, $\sf PA$ cannot prove $\operatorname{Con}\sf (PA)$. But Gentzen proved that $\sf PRA$ augmented by induction up to $\varepsilon_0$ can in fact prove $\operatorname{Con}(PA)$.

However, $\sf PRA$ is a weak fragment of $\sf PA$, and the induction axioms add nothing to "correct of the missing part".

Other, sillier examples, include $\sf ZFC$ which cannot prove $\operatorname{Con}\sf(ZFC)$, but $\sf PA+\operatorname{Con}(ZFC)$ clearly proves $\operatorname{Con}\sf (ZFC)$.


As an even sillier example, take the language of arithmetic and extend it with a new binary operator $\circledast$. Then let $S$ be the theory consisting of all PA axioms plus $0\circledast 0=0$. Apply the Gödel procedure to this and get a true sentence $G$ that $S$ does not prove.

On the other hand if we let $S'$ be the PA axioms plus $G$ itself, then that certainly does prove $G$ -- but $S'$ will not prove $0\circledast 0=0$, because we can make a model of $S'$ where $0\circledast 0=0$ is false by taking the ordinary natural numbers with the ordinary addition and multiplication, and then interpret $\circledast$ as the function that always returns $1$. (Here it is important that Gödel's construction always results in an arithmetical sentence, so we know there are no $\circledast$s in $G$).

All this is assuming the only thing you know about $S'$ is that it is something that can prove your Gödel sentence.

It seems somewhat more likely that you have read a description where $S'$ is not just any system with this property, but where you specifically construct $S'$ by taking $S$ and adding the Gödel sentence as a new axiom. In that particular case, it is of course true that $S'$ proves all of the theorems and axioms of $S$ -- simply because every $S$-proof is still a valid $S'$-proof.


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.