1
$\begingroup$

Gödel's incompleteness theorem states that: "if a system is consistent, it is not complete." And it's well known that there are unprovable statements in ZF, e.g. GCH, AC, etc.

However, why does this mean that ZF is consistent? What does "relatively consistent" actually mean?

  • 5
    Your statement of the incompleteness theorem is wrong. The system must also be assumed to be sufficiently powerful to allow you to encode arithmetic in it. (You probably know this, but other visitors to the site might get confused.)2012-08-16

2 Answers 2

4

We have to hedge quite a bit in what you said. First, there are many complete theories: the theory of all groups of order 7 is complete, as an example. However, Gödel showed that any "nice enough" (read: "recursively enumerable") consistent first-order theory capable of encoding basic arithmetic is incomplete. (There is a complete theory of number theory, usually denoted $\mathrm{Th}(\mathbb{N})$, which consists of all sentences that are true in the standard model of number theory; unfortunately, this is not a "nice enough" theory — it's impossible to program a computer to print out all and only the axioms of this theory!)

Also, these statements that you gave, $\mathsf{(G)CH}$, $\mathsf{AC}$, are not provably unprovable in $\mathsf{ZF}$. However, it is provable that they are unprovable in $\mathsf{ZF}$ only if $\mathsf{ZF}$ is itself inconsistent.

This is what a relative consistency result means: it is a result that says the consistency of one theory implies the consistency of the other. Kurt Gödel proved that if $\mathsf{ZF}$ is consistent, then so if $\mathsf{ZFC}+\mathbf{V}=\mathbf{L}$ (and also that $\mathsf{ZFC}+\mathbf{V}=\mathbf{L}$ implies $\mathsf{GCH}$). Paul Cohen proved that if $\mathsf{ZF}$ is consistent, then both $\mathsf{ZF}+\neg\mathsf{AC}$ and $\mathsf{ZFC}+\neg\mathsf{CH}$ are consistent. More elementarily, with $\mathsf{ZF}$ one can construct the natural numbers, and so the consistency of $\mathsf{ZF}$ implies the consistency of $\mathsf{PA}$. These are fundamentally relative consistency results, and cannot be improved to straight consistency results. This stems from Gödel's Second Incompleteness Theorem. Because of this the acceptance of the consistency of $\mathsf{ZF(C)}$ is an article of faith (though one I'm happy to believe in).

I recommend that you look at the first page of George Boolos's Gödel's second incompleteness theorem explained in words of one syllable (Mind, vol.103, pp.1-3). It is a quite entertaining look at the meaning of Gödel's Second Incompleteness Theorem.

  • 0
    @PeterHeinig I'm pretty sure that "recursively enumerable" is enough. I've edited the answer to make this all more explicit.2017-07-16
2

Relatively consistent means that if some other system is consistent, then so is the given system. For example, ZF is relatively consistent with ZF-Foundation (and vice versa), and relatively consistent with ZFC (and vice versa). For a unidirectional example, the axioms of Peano arithmetic are relatively consistent with ZF. However, the consistency of Peano arithmetic does not entail the consistency of ZF. (Thanks again, Henning.)

  • 0
    Actually, it is precisely what I meant to say...I was simply wrong (thanks for the benefit of the doubt). I was under the (apparently mistaken) impression that statements such as AC are provably unprovable in ZF, and based on that false premise was able to derive a false conclusion. I guess I need to look into that again.2012-08-16