Rosser Systems

Our first proof of the incompleteness of P.A. was based on the assumption that P.A. is correct. Gödel’s proof of the last chapter was based on the metamathematically weaker assumption that P.A. is ω-consistent. Rosser [1936] subsequently showed that P.A. can be proved incomplete under the still weaker metamathematical assumption that P.A. is simply consistent! Now, Rosser did not show that the Gödel sentence G of the last chapter is undecidable on the weaker assumption of simple consistency. He constructed another sentence (a more elaborate one) which he showed undecidable on the basis of simple consistency. Our first proof of the incompleteness of P.A. boils down to finding a formula that expresses the set P̃* (or alternatively one that expresses R*). Gödel’s proof, which we gave in the last chapter, boils down to representing one of the sets P* and R* in P.A. and the only way known in Gödel’s time of doing this involved the assumption of ω-consistency. [This assumption was not needed to show that the sets P* and R* are enumerable in P.A.—it was in passing from the enumerability of these sets to their representability that ω-consistency stepped in.] Now, Rosser did not achieve incompleteness by representing either of the sets P* and R*, but rather by representing some superset of R* disjoint from P*—this can be done under the weaker assumption of simple consistency—and it also serves to establish incompleteness, as we will see. The axiom schemes Ω4 and Ω5 of the system (R) will play a key role in this and the next chapter. We shall say that a system S is an extension of Ω4 and Ω5 if all formulas of Ω4 and Ω5 are provable in S. We will prove the following theorem and its corollaries. Theorem R. Every simply consistent axiomatizable extension of Ω4 and Ω5 in which all Σ1-sets are enumerable must be incomplete. Corollary 1. Every simply consistent axiomatizable extension of Ω4 and Ω5 in which all true Σ0-sentences are provable must be incomplete. Corollary 2. Every simply consistent axiomatizable extension of the system (R) is incomplete.