universal, formulas, statements, sentences, consistent, provable, Goldbach conjecture, Berry paradox, Goldbach, conjecture, paradox, Berry, incompleteness
Back to title page.
Left |
Adjust your browser window |
Right |
Let us consider the famous Goldbach's Conjecture from 1742 by Christian Goldbach (1690-1764): every even number greater than 2 can be expressed as a sum of two prime numbers. For example (the really interesting numbers are shown in bold),
4=2+2, 6=3+3, 8=5+3, 10=5+5, 12=7+5, 14=11+3, 16=13+3, 18=13+5, 20=17+3, 22=19+3, 24=19+5, 26=23+3, 28=23+5, 30=23+7, 32=29+3, 34=31+3, 36=31+5, 38=31+7, 40=37+3, 42=37+5, 44=41+3, 46=43+3, 48=43+5, 50=47+3, 52=47+5, 54=47+7, 56=53+3, 58=53+5, 60=53+7, 62=59+3, 64=61+3, 66=61+5, 68=61+7, 70=67+3, 72=67+5, 74=71+3, 76=73+3, 78=73+5, 80=73+7, 82=79+3, 84=79+5, 86=83+3, 88=83+5, 90=83+5, 92=89+3, 94=89+5, 96=89+7, 98=79+19, 100=97+3, 102=97+5, 104=97+7, 106=103+3, 108=103+5, 110=107+3, 112=109+3, 114=109+5, 116=113+3, 118=113+5, 120=113+7, 122=109+13, 124=113+11, 126=113+13, 128=109+19, 130=127+3, 132=127+5, 134=131+3, ...
See also http://mathworld.wolfram.com/GoldbachConjecture.html.
Assume, you are a Platonist believing that Goldbach's Conjecture is, "in fact", true. I.e. if you take any even number n, it can be expressed as a sum of two primes. If it can, you can determine these two primes p1+ p2 = n simply by trying n = (n-3)+3, n=(n-5)+5, n=(n-7)+7, n=(n-11)+11, etc. up to n=k+k. Any particular true equality p1+ p2 = n, i.e.
(1+1+...+1) + (1+1+...+1) = (1+1+...+1)
p1 times ------ p2 times ------- n times
can be proved in PA (see Exercise 3.4a).
Let Go(x) be a formula expressing in PA the following (computable) predicate go(x):
"If x is an even number greater than 2, then x is a sum of two primes",
for example,
Ey(y<x & x=y+y) & 2<x ->Ep1Ep2(p1<x & p2<x & prime(p1) & prime(p2) & x=p1+p2),
where:
a<b is a shortcut for Ec(a+c+1=b), and
prime(z) is a shortcut for ~EuEv(u<z & v<z & z=u*v).
Formula Go(x) contains only bounded quantifiers. As we know from Exercise 3.4b, for each natural number n, if Go(n) is true, then PA proves Go(n) (n is the numeral representing the number n).
Now, Goldbach's Conjecture can be represented as the formula AxGo(x).
Thus, we have the following situation. If Goldbach's Conjecture is true, then, for each natural number n, PA proves Go(n). Could we conclude from this that PA |- AxGo(x), i.e. that PA proves Goldbach's Conjecture?
In general, no. Because, "for each n, PA |- Go(n)" means that there is an infinite sequence of proofs, a separate proof for each formula Go(n). Could we hope to convert this infinite sequence into a single finite proof of the formula AxGo(x)?
In general, no. For example, Goedel's self-referencing formula G, used in the incompleteness proof of PA, asserts "I'm not provable in PA". It is equivalent to the formula Ay~PRF(G, y), where the formula PRF(x, y) expressies the predicate "y is a PA-proof of x" (more precisely, "y is Goedel number of a PA-proof of the formula having Goedel number x") As we know from Section 5.3, if PA is a consistent theory, then G cannot be proved in PA, i.e. the formula ~PRF(G, n) is true for each n (G is the Goedel number of G). Hence, for each n, PA |- ~PRF(G, n). Could we conclude from this that PA |- Ay~PRF(G, y), i.e. that PA proves Goedel's formula G? No, because this would mean that PA is inconsistent! Hence, if PA is a consistent theory, then the infinite sequence of PA-proofs of the formulas ~PRF(G, n) cannot be converted into a single finite PA-proof of the formula Ay~PRF(G, y).
On the other hand, let us assume that Goldbach's Conjecture is false. Then there is an even number n>2, which cannot be expressed as a sum of two primes. Then, as we know from Exercise 3.4b, since the formula ~Go(x) contains only bounded quantifiers, we can prove in PA the formula ~Go(n). Then, of course, PA |- ExGo(x), and PA |- ~AxGo(x). Hence, if Goldbach's Conjecture is false, then PA "proves this fact".
And thus, if we could prove that PA cannot prove that Goldbach's Conjecture is false, then we would have a proof... that Goldbach's Conjecture is true! Since
"PA cannot prove that Goldbach's Conjecture is false"
is equivalent to
"PA + Goldbach's Conjecture is a consistent theory".
Hence, if we could prove that Goldbach's Conjecture is consistent with the axioms of PA, then we would have a proof that Goldbach's Conjecture is true!
The only specific property used in the above chain of reasoning, is the following: for all n, if Go(n) is false, then PA |- ~Go(n), so, a more general formulation of the above statement should be possible. Let us try to produce it.
Let T be any formal theory in the language of PA, and M - a fundamental theory. We will use M as a meta-theory of T.
F(x) is a formula containing exactly one free variable x.
PRT(y) is a formula intended to assert that "the formula having the Goedel number y is provable in T".
SUB(x, y, z) is a formula representing in PA the so-called substitution function (see Section 5.2):
sub(x, y) = "Goedel number of the formula obtained from the formula having the Goedel number x by substituting the numeral y for all of its free variables" (if x is not a Goedel number of a formula, then let sub(x, y)=0).
Suppose, T and M are powerful enough in the sense that
M proves: "For all natural numbers n, if ~F(n), then T |- ~F(n)".
More precisely (~F is the Goedel number of the formula ~F),
M |- An(~F(n) -> Ay(SUB(~F, n, y)->PRT(y))) .
Hence,
M |- An(~Ay(SUB(~F, n, y)->PRT(y)) -> F(n)), -------------- (*)
i.e. M proves that for all n, if T does not prove ~F(n), then F(n) is true.
(1) Suppose, T, M and PRT satisfy the following uniform derivability condition:
M proves: "For all n, if T |- D(n), then T |- ExD(x)".
More precisely (D and ExD(x) are Goedel numbers of the formulas D(x), ExD(x)),
M |- An[Ay(SUB(D, n, y)->PRT(y)) -> PRT(ExD(x))].
Hence,
M |- An[~PRT(ExD(x)) -> ~Ay(SUB(D, n, y)->PRT(y))],
and,
M |- ~PRT(ExD(x)) -> An[~Ay(SUB(D, n, y)->PRT(y))],-------------- (**)
i.e. M proves that, if T does not prove ExD(x), then for all n, T does not prove D(n).
(2) Suppose, T, M and PRT satisfy Hilbert-Bernays-Loeb derivability conditions (see Section 5.4).
Now, from (*) and (**) we obtain directly that
M |- ~PRT(Ex~F(x)) -> AnF(n).
Since T |- Ex~F(x) -> ~AxF(x), then, by (3), we obtain that
M |- PRT(Ex~F(x)) -> PRT(~AxF(x)),
M |- ~PRT(~AxF(x)) -> PRT(Ex~F(x)),
and
M |- ~PRT(~AxF(x)) -> AnF(n) ------------ (***).
Thus, we have proved the following
Theorem 6.7.1 (Author(s)? Folklore?). Suppose, T is any formal theory in the language of PA, M is a fundamental theory, and they satisfy the above-mentioned derivability conditions (1, 2). If, for the formula F(x) containing exactly one free variable x,
a) M proves: "For all natural numbers n, if ~F(n), then T |- ~F(n)",
b) M proves that ~AxF(x) cannot be proved in T,
then M proves AxF(x).
Corollary 6.7.2 (Author(s)? Folklore?). Suppose, T is any formal theory in the language of PA, M is a fundamental theory, and they satisfy the above-mentioned derivability conditions (1, 2). If, for the formula F(x) containing exactly one free variable x,
a) M proves: "For all natural numbers n, if ~F(n), then T |- ~F(n)",
b) M proves that T+AxF(x) is a consistent theory,
then M proves AxF(x).
Proof. "M proves that T+AxF(x) is a consistent theory" - what, precisely, does it mean? The formula Con(T+AxF(x)) can be defined as "T does not prove AxF(x)->0=1", i.e. as ~PRT(AxF(x)->0=1). Since T |- ~AxF(x) -> (AxF(x)->0=1) (Axiom L10), then, by (3), we obtain that
M |- PRT(~AxF(x))->PRT(AxF(x)->0=1),
M |- Con(T+AxF(x)) -> ~PRT(~AxF(x)).
By (***),
M |- Con(T+AxF(x)) -> AnF(n).
Q.E.D.
Corollary 6.7.3 (Author(s)? Folklore?). Suppose, T is any formal theory in the language of PA, M is a fundamental theory, and they satisfy the above-mentioned derivability conditions (1, 2). If
a) M proves: "For all natural numbers n, if ~Go(n), then T |- ~Go(n)",
b) T + Goldbach's Conjecture is a consistent theory,
then M proves Goldbach's Conjecture.
Proof. Immediately, from Corollary 6.7.2.
Corollary 6.7.4 (Author(s)? Folklore?). Suppose, M is a fundamental theory, PA and M satisfy the above-mentioned derivability conditions (1, 2). If M is powerful enough to prove that PA + Goldbach's Conjecture is a consistent theory, then M proves Goldbach's Conjecture.
Proof. As we established above,
"For all natural numbers n, if ~Go(n), then PA |- ~Go(n)."
These verifications can be formalized in PA:
PA |- An(~Go(n) -> Ay(SUB(~Go, n, y)->PRT(y))).
Hence, since M is a fundamental theory, then, by Corollary 6.7.3, Q.E.D.
According to Corollary 6.7.3, instead of PA, we could use any weaker axiom system T such that for all natural numbers n, if ~Go(n), then T proves ~Go(n). Thus, if we could prove that Goldbach's Conjecture is consistent with the weakest known of such axiom systems, then we would have proved that Goldbach's Conjecture is true! The weaker the system T, the easier should be the consistency proof of T + Goldbach's Conjecture? Yes, but - the weaker the system T, the more difficult becomes proving of "for all natural numbers n, if ~Go(n), then T |- ~Go(n)". This proof is very easy for PA, but the consistency proof of PA + Goldbach's Conjecture seems to be very difficult...
Strange and/or crazy situation? A kind of paradox?
Further reading:
Online comments by William G.Dubuque at http://www.math.chalmers.se/~bo/internetguiden/listexempel.html#9
Kemeny, J. G. "Undecidable Problems of Elementary Number Theory." Math. Ann. 135, 160-169, 1958.
Kreisel's Conjecture - see at http://mathworld.wolfram.com/KreiselConjecture.html
The idea that Berry's Paradox could inspire an incompleteness theorem, which would be, in a sense, stronger than Goedel's Incompleteness Theorem (which was - in a sense - "inspired" by the Liar's Paradox) is due to Gregory J.Chaitin. He tells in his 1993 lecture at the University of New Mexico that in 1974 he tried to check the reaction of Goedel himself to this idea. Unsuccessfully.
In this section, I will try to follow Chaitin's idea in a more traditional fashion - in order to obtain a pure syntactic incompleteness theorem I will avoid using the algorithmic information theory.
In its classical form Berry's Paradox is as follows. Let us consider the following phrase, consisting of fourteen English words:
The first natural number, which cannot be defined by using under fifteen English words.
Thus, "the first natural number, which cannot be defined by using under fifteen English words" can be defined by using fourteen English words!
Unfortunately, very little can be found on the web about the author of this paradox. According to http://mathworld.wolfram.com/BerryParadox.html, "There are several versions of the Berry paradox, the original version of which was published by Bertrand Russell and attributed to Oxford University librarian Mr. G.Berry." And according to Jeff Whittington, "George Godfrey Berry devised Russell-type paradoxes." (try opening www.echonyc.com/~velvim/rr.htm - now, a dead web-site?). Thus, most probably, Berry, or Mr. G.Berry could be, in fact, Oxford University librarian George Godfrey Berry.
The above-mentioned Russell's 1906 paper:
B.Russell. Les paradoxes de la logique. "Revue de Metaphysique et de Morale", 1906, 14, pp.627-650.
Of course, Berry's Paradox is not the only paradoxical thing that can be expressed "by using English words". Some people try "solving" paradoxes by introducing language rules allowing to avoid them. Still, on the other side, each paradox contains its specific creative potential. For example, by formalizing the Liar's Paradox one can prove Goedel's Incompleteness Theorem (see Section 5.3). Which kind of incompleteness theorem could be derived from Berry's Paradox?
First of all, let us free the paradox of its "English flavour" by introducing the following phrase B0(n):
The first natural number, which cannot be defined by using under n-character string.
If n is the unary representation of n (fifteen = 111111111111111), then B0(n) is an 85+n-character string. Thus, "the first natural number, which cannot be defined by using under n-character string" can be defined by an 85+n-character string. Hence, B0(n) does not yield a paradox.
Now, let us modify B0(n) by introducing the following phrase B1(n):
The first natural number, which cannot be defined by using under 2*n-character string.
If n is the unary representation of n, then B1(n) is an 87+n-character string. Thus, "the first natural number, which cannot be defined by using under 2*n-character string" can be defined by an 87+n-character string. Thus, if 87+n < 2n (i.e. if n > 87), then B1(n) yields a paradox! Indeed, if n > 87, then "the first natural number, which cannot be defined by using under 2*n-character string" can be defined by an 87+n < 2n-character string.
Now, let us try to formalize this form of Berry's paradox.
Let T be any fundamental theory (i.e. a formal theory covering the first order arithmetic). Let us say that T defines the number k, iff there is a (first order arithmetic) formula F(x) with exactly one free variable x, such that T |- F(k) & Ax(F(x) -> x=k). I.e., if T proves that k is the only natural number possessing the property expressed by the formula F.
Of course, the formula x=k defines the number k in the first order arithmetic (called also Peano arithmetic, or PA). Thus, of course, all numbers are definable in PA (and, hence, in any other fundamental theory).
Exercise 6.8.1. a) Verify that, if T is inconsistent, then the formula x=0 defines in T any number k.
b) Verify that, if T is consistent, then each formula F(x) defines in T none or one number k.
Still, some numbers k can be defined by formulas much shorter than x=k (note that k is longer that the unary representation of k: 2 is 1+1, 3 is (1+1)+1, 4 is ((1+1)+1)+1, etc., i.e. the length of k is 4*k-5, and the length of the formula x=(k) is 4*k-1). For example, the formula
x = min { x | Ey(y2-109*x2=1) },
or, more precisely, the following first order arithmetic formula F1(x):
Ey(y*y=(109)*x*x+1)&Ax1(x1<x -> ~Ey(y*y=(109)*x1*x1+1))
defines in PA the number 15 140 424 455 100 (it is a part of the smallest solution of the equation y2-109*x2=1 - according to Edwards [1977], Table 1.7). The total length of the formula F1(x) is only about
43+2*length(109) = 43+2*(4*109-5) = 905 characters!
How to produce a number that cannot be defined in theory T by formulas F(x) shorter than n characters? Or, more generally - by formulas F(x) shorter than f(n) characters, where f is some computable function?
The lemmas and theorems established below hold for any method of measuring the size of formulas that satisfies the following two conditions:
a) The size of a formula is computable from the text of it.
b) For any number t there is only a finite set of formulas having sizes <=t. More precisely, there is an algorithm that (given a number t) prints out all formulas having sizes <=t, and halts.
So, let us try simulating the Berry's Paradox by the following process PT,f(n). The number n is the only input parameter of PT,f(n), and, for each n, this process will generate a set of natural numbers. First, it generates the number 0. After this, let us use the program that is generating all theorems of theory T, and, among these theorems, let us search for formulas having the form F(k) & Ax(F(x) -> x=k) with F(x) shorter than f(n). If we meet such a formula F(x) and the number k, let us generate the number k+1 (in this way we may hope to generate a number that cannot be defined in T by formula shorter than f(n)). If we meet the same formula F(x) another time (i.e. with a different number k), let us ignore it (in fact, this could happen only, if T is an inconsistent theory - see Exercise 6.8.1(b)).
Thus, independently of the consistency of T:
a) If, for some values of k, T |- F(k) & Ax(F(x) -> x=k) with F(x) shorter than f(n), then the process PT,f(n) will generate k+1 only for one of these values.
b) For each formula F(x) shorter than f(n), the process PT,f(n) will generate none or one number k+1.
c) Since there is only a finite number of formulas shorter than f(n), for each n, the process PT,f(n) will generate only a finite set of numbers.
Let us denote by BT,f(n) the maximum of the numbers generated by the process PT,f(n) (Berry's function).
Lemma 6.8.1. If T is a consistent theory, then, for each n, the number BT,f(n) cannot be defined in theory T by a formula shorter than f(n).
Proof. If BT,f(n) could be defined in theory T by a formula F(x) shorter than f(n), then the corresponding (T-provable) formula F(k) & Ax(F(x) -> x=k) with k=BT,f(n) would appear in the process PT,f(n). And, if T is consistent, then F could not appear in the process with k other than BT,f(n) (see Exercise 6.8.1(b)). Hence, then the process PT,f(n) would generate the number BT,f(n)+1. This is impossible because BT,f(n) is the maximum of the numbers generated by the process PT,f(n) "ad infinitum". Q.E.D.
As a function of n, Berry's function BT,f(n) may be non-computable, because, when the process PT,f(n) is still going on, we never know, will it generate a greater number than before, or not. Still, we can produce a formula MT,f(n, x) asserting that BT,f(n)=x. First, let us note that the following predicate is computable:
"after t steps of the process PT,f(n) a maximum number x has been generated".
Hence, by the Representation Theorem, there is a formula MXT,f(n, t, x) expressing this predicate in PA. Then, the formula MT,f(n, x):
Et0At (t>=t0 -> MXT,f(n, t, x)) --------------------- (1)
will assert that x is the maximum number generated by the process PT,f(n), i.e. that BT,f(n)=x.
Exercise 6.8.2. Thus, the predicate BT,f(n)=x can be defined in the language of the first order arithmetic by a formula Et0At G(n, x, t0, t), where the formula G expresses a computable (recursive) predicate. I.e. BT,f(n)=x belongs to the class of the so-called SIGMA2-predicates. Verify that the negation ~(BT,f(n)=x) also belongs to the class of SIGMA2-predicates. Hence, BT,f(n)=x is a SIGMA2-predicate and a PI2-predicate BT,f(n)=x simultaneously, i.e., in fact, it belongs to the class of the so-called DELTA2-predicates, and thus, Berry's function belongs to the class of DELTA2-functions ( DELTA2 is defined as the intersection of SIGMA2 and PI2).
Lemma 6.8.2. In PA, we can prove that BT,f is a total function. More precisely, for an appropriate formula MXT,f,
PA |- AnEk (MT,f(n, k) & Ax (MT,f(n, x) -> x=k)), or, shorter, PA |- AnE1k MT,f(n, k).
Proof. Read once more the description of the process PT,f(n). For an appropriate formula MXT,f(n, t, x), you can formalize this description in PA. Note, that you do not need to know, is T a consistent theory, or not. Q.E.D.
We know that the formula MT,f(n, x) asserts that BT,f(n)=x. Could it happen that the formula MT,f(n, x) defines the number BT,f(n) in theory T? If so, then BT,f(n) could be defined in T by a formula consisting of
size[MT,f(n, x)] = bT,f*n+cT,f characters,
where the two constants bT,f, cT,f depend on the definition of theory T, and on the program that computes the function f ( i.e. on how "complicated" they are). If bT,f*n+cT,f < f(n), then this would mean a contradiction in T. Indeed, by Lemma 6.8.1, if T is a consistent theory, then the number BT,f(n) cannot be defined in theory T by a formula shorter than f(n).
Note that, if f(n) is growing faster than linearly (for example, if f(n)=n2), then bT,f*n+cT,f < f(n) for any sufficiently large n. If f(n)=n2, then bT,f*n+cT,f < f(n), if n>max(bT,f, cT,f).
Lemma 6.8.3. For an appropriate formula MXT,f, , there are two constants bT,f, cT,f such that, for each number n such that bT,f*n+cT,f < f(n): if T |- MT,f(n, BT,f(n)), then T is inconsistent.
Proof. If T |- MT,f(n, BT,f(n)), then, by Lemma 6.8.2,
T |- MT,f(n, BT,f(n)) & Ax ( MT,f(n, x) -> x=BT,f(n)).
Since size[MT,f(n, x)] = bT,f*n+cT,f, for some numbers bT,f, cT,f, then, if bT,f*n+cT,f < f(n), then, for some k, the formula MT,f(n, k) & Ax (MT,f(n, x) -> x=k will appear in the process PT,f(n). And, if T is consistent, then this can happen only with k=BT,f(n). But then the process will generate the number BT,f(n)+1. This is impossible, because BT,f(n) is the maximum number generated by the process PT,f(n) "ad infinitum". Q.E.D.
Lemma 6.8.4. For an appropriate formula MXT,f,
PA |- At0Ax0[ MXT,f(n, t0, x0) -> AxAt(x<x0 & t>= t0 -> ~MXT,f(n, t, x))].
Proof. The above formula asserts that, if, at some moment t0, the process has generated the maximum number x0, then at any further moment t it can't generate a maximum number x less than x0. For an appropriate formula MXT,f, the proof of this assertion can be formalized in PA. Q.E.D.
Lemma 6.8.5. For an appropriate formula MXT,f, if k<BT,f(n), then PA |- ~MT,f(n, k).
Proof. For a number n, there is a time moment t0, when BT,f(n) has been already generated. At this moment the formula MXT,f(n, t0, BT,f(n)) becomes true, hence,
PA |- MXT,f(n, t0, BT,f(n)).
Then, by Lemma 6.8.4,
PA |- AxAt(x<BT,f(n) & t>= t0 -> ~MXT,f(n, t, x)).
Substitute k for x,
PA |- At(k<BT,f(n) & t>= t0 -> ~MXT,f(n, t, k)),
Since k<BT,f(n) is true,
PA |- At(t>= t0 -> ~MXT,f(n, t, k)).
And, since MT,f(n, k) is Et0At (t>=t0 -> MXT,f(n, t, k)), we obtain that PA |- ~MT,f(n, k). Q.E.D.
Lemma 6.8.6. For an appropriate formula MXT,f, if k>BT,f(n), then there is t0 such that
PA |- At (t>=t0-> ~MXT,f(n, t, k)).
Proof. For a number n, there is a time moment t0, when BT,f(n) has been already generated. Hence, if k>BT,f(n), then at any moment t>=t0 the formula MXT,f(n, t, k) is false. For an appropriate formula MXT,f, this can be formalized in PA. Q.E.D.
Now, we can prove a pure syntactic incompleteness theorem inspired by Berry's Paradox.
Theorem 6.8.7. If T is a fundamental theory, and f - a computable function, then there is a DELTA2-formula MT,f(n, x) such that:
a) PA |- AnE1k MT,f(n, k),
b) There are two constants bT,f, cT,f such that, for each number n such that bT,f*n+cT,f < f(n): if k=BT,f(n) and T |- MT,f(n, k), then T is inconsistent.
c) If k<>BT,f(n) and T |- MT,f(n, k), then T is inconsistent.
Proof. The formula MT,f(n, x) is defined as (1).
a) By Lemma 6.8.2.
b) By Lemma 6.8.3.
c1) If k<BT,f(n) and T |- MT,f(n, k), then, by Lemma 6.8.5, PA |- ~MT,f(n, k), i.e. T is inconsistent.
c2) Now, let k>BT,f(n).
T |- MT,f(n, k), means T |- Et0At (t>=t0 -> MXT,f(n, t, k)). By Lemma 6.8.6, there is t1 such that T |- At (t>=t1 -> ~MXT,f(n, t, k)), hence, T |- Et1At (t>=t1 -> ~MXT,f(n, t, k)). Thus, by "taking t2 = max(t0, t1)",
T |- Et2At (t>=t2 -> MXT,f(n, t, k) & ~MXT,f(n, t, k)),
i.e. T is inconsistent.
Q.E.D
Corollary 6.8.8. If T is a fundamental theory, then there is a DELTA2-formula MT(n, x) such that:
a) PA |- AnE1k MT(n, k),
b) There is n0 such that for each n>=n0: if, for some k, T |- MT(n, k), then T is inconsistent.
Proof. Take f(n)=n2. Q.E.D.
...
To be continued.
Open Problem? Could a SIGMA1- , or PI1-formula MT(n, x) be possible?
Note. About George Boolos's 1989 paper, where Berry's Paradox is used to prove incompleteness:
G.Boolos. A new proof of the Goedel incompleteness theorem. "Notices of the American Mathematical Society", April 1989, vol. 36, N4, pp.388-390.
See also http://bureau.philo.at/phlo/199711/msg00080.html: "George Boolos gave a proof which he said that Kripke told him he had noticed in the early 60's."
Back to title page.
universal, formulas, statements, sentences, consistent, provable, Goldbach conjecture, Berry paradox, Goldbach, conjecture, paradox, Berry, incompleteness