I remember when I was young and first learned about prime numbers. I thought, how many of them are there? I asked my teacher and he said they go on forever and pointed to the following famous proof in a book:
Suppose that p1=2 < p2 = 3 < … < pr is all of the primes. Let P = p1p2…pr+1 and let p be a prime dividing P; then p can not be any of p1, p2, …, pr, otherwise p would divide the difference P-p1p2…pr=1, which is impossible. So this prime p is still another prime, and p1, p2, …, pr would not be all of the primes.
Being young, this took some effort to understand the concept expressed by the language.
It depends on exactly what you mean by a “statement about the natural numbers”, but if you are satisfied by the translation as “a statement of first-order arithmetic” (i.e., a statement that can be written with equality, the operations + and × (you can throw in power, it won’t change anything) and all quantifiers ranging over the set of natural numbers), then the answer is no: every statement of first-order arithmetic that can be proved using ZFC (+GCH if you will) can, in fact, be proved in ZF.
The way this (I mean, the meta theorem I just stated) is proved is by using Gödel’s constructible universe, which is a class of sets L, definable in ZF, which is a model of ZF, in which the axiom of choice (+GCH) automatically holds; and this class L has the same set ω of natural numbers as the universe. So if you can prove something from ZFC(+GCH), it is true in L, and if it is an arithmetical statement, then it speaks about ω which is the same in L as in the universe, so the statement is true in the universe.
Leave a Reply