Another puzzle: Gödel, Goldbach and other “G” names…


Mr Blobby posted an excellent comment in my previous post, outlining in a few words Gödel’s proof of incompleteness of arithmetics. This is a mind-boggling result, which essentially states the following:

There are certain statements (I would not say “theorems”) in the body of Arithmetics, which are either true or false. But there is no way to find a proof for either of these two statements. Because there is no such proof.

So, let’s take for example an unproven statement, Goldbach conjecture. This conjecture simply states that any even natural number (greater than 2) is a sum of two primes. Despite its apparent simplicity, this simple conjecture has no known proofs up to date! But even if there is no proof, assuming that you have infinite time (and patience) you can verify it manually by taking every even number and trying to express it as a sum of two prime numbers. But even if this statement is true, or false, there might be no proof for it after all! We don’t know yet…

But let’s go now a little bit further. OK, so let’s assume that the Goldbach conjecture is unprovable after all. Assuming this, what if there is a proof that says that Goldbach is unprovable? What can we say about this statement?

Exercise to the reader…

Comments (16)

  1. Dmitriy says:

    We can say that number theory is incomplete (and it is) and choose to extend it by taking either the Goldbach Conjecture, or its negation, as an axiom. Both resulting systems will be consistent (yet still incomplete).

    Euclid’s Fifth Postulate is unprovable within absolute geometry (the first four postulate). Therefore, absolute geometry can be extended into Euclidean (Fifth Postulate assumed true) and non-Euclidean directions.

  2. Dmitriy says:

    An interesting question is what happens when we extend the number theory in either direction.

    Since we assume that the GC is unprovable, that means there are no statements in number theory that either contradict GC or its negation. Therefore we are free to assume either without worrying about creating an inconsistent system.

    The GC is generally thought to be true, and if we assume it to be true, we’ll probably get something that closely resembles our familiar number theory. Probably.

    But what if we assume the negation of GC to be true? Well, the GC states that for any number n ≥ 2, there exists a pair of primes p and q such that p + q = 2n. So the negation of GC, our new axiom, states that there exists a number n for which p and q don’t exist!

    But the rub about the GC is that this property of being a sum of two primes is verifiable using a predictably terminating algorithm. All we have to do is test all primes up to 2n and we’re guaranteed to get an answer within a predictably finite amount of time.

    4 = 2 + 2

    6 = 3 + 3

    8 = 5 + 3

    10 = 7 + 3

    12 = 7 + 5

    Hmm…

    I don’t think I’m getting anywhere. And I probably won’t. Since GC is undecidable within number theory, I’m never going to find a counter-example to it this way. Yet our new axiom states that this number n does exist! If this number is not 2, 3, 4, 5, 6, or any finite number… then this number n must be fundamentally different from these finite numbers.

    You can probably prove a handful of things about these new numbers. There’s probably more than one. There’s probably a way to add and multiply them together. You can probably multiply them by natural numbers too. And probably someone has already sat down and worked these things out. 🙂

  3. Adi Oltean says:

    By the way, I don’t necessarily believe that the Goldbach conjecture is unprovable. There might be a proof after all… I don’t know!

    I just picked up this conjecture as a possible example of an unprovable statement, to give a practical illustration of how the Godel theorem might impact arithmetics.

    P.S. And, no, you are actually on the right track…

  4. Adi Oltean says:

    One more thing – GC can be considered as a separate axiom only if the GC is true. If it is false, then obviously you have a counterexample which would be inconsistent with the existing set of axioms.

  5. PatternGuru says:

    Guess you’ve all been reading GEB (http://www.amazon.com/exec/obidos/ASIN/0465026567) by Douglas R. Hofstadter, huh…? And if not, then definately do so!

    P.S. The name if actually "Gödel" or "Goedel". 😉

  6. Mark Mullin says:

    I thought that was where you were headed with your previous post – however, since you work at a company more known for languages and systems than for advanced theoretical math, consider this

    What are the implications of Goedels work with respect to languages and systems ?

    1) For any language L, define a language mL which can be used to define elements that are not computable in L, but are by definition computable

    2) For any system S repeat the drill in #1.

    The inverse of this is more interesting in todays world, i.e. how do you define a language where business processes are computable and viruses are not

  7. Jeremy says:

    I can say that if such a proof existed, it would be both elegant and completely impossible for me to understand. 🙂

  8. Dmitriy says:

    "One more thing – GC can be considered as a separate axiom only if the GC is true. If it is false, then obviously you have a counterexample which would be inconsistent with the existing set of axioms."

    It can only be considered as a separate axiom only if it’s unprovable. If it’s true, it can only be considered a theorem. 🙂

    And Gödel’s theorem doesn’t really impact arithmetics. Arithmetics is still arithmetics and everything we think to be true is still true in the face of Gödel’s Incompleteness Theorem. It’s just that we now know that once a system reaches a certain level of complexity (and the bar is set quite low), it gains the ability to express statements that are unprovable within that system.

    "But even if there is no proof, assuming that you have infinite time (and patience) you can verify it manually by taking every even number and trying to express it as a sum of two prime numbers. But even if this statement is true, or false, there might be no proof for it after all!"

    If the statement is unprovable, it’s neither true nor false. It is simply "outside" the system. If all you know is absolute geometry, is Euclid’s Fifth Postulate true or false?

  9. Adi Oltean says:

    >> But let’s go now a little bit further. OK, so let’s assume that the Goldbach conjecture is unprovable after all. Assuming this, what if there is a proof that says that Goldbach is unprovable? What can we say about this statement?

    The answer to the puzzle: there is no way to find a proof that says “GC is unprovable”. (GC being the Goldbach conjecture).

    The demonstration is quite straightforward. First, let’s assume the reverse, i.e. let’s assume that there is a certain proof that concludes that GC is unprovable.

    Now, in reality, GC is either true or false. The condition that an even number can be decomposed in two primes either stands or not for all numbers greater than two.

    So, let’s start first by assuming that GC is false. Then, obviously there is at least a number X which cannot be written as a sum of two primes. More than that: in this hypothesis, enumerating all possible ways on which X can be decomposed as a sum of two other natural numbers constitutes a proof that GC is false. But we already said that we have a proof that concludes that GC is unprovable. Contradiction!

    Therefore, GC must necessarily be true. But hold on a second. Not only that GC is true but, we just built an actual proof that says that GC is true! And this again contradicts the original assumption – we have a proof that GC is unprovable.

    To conclude, our original assumption (that there is a proof that says "GC is unprovable") is false. Therefore, there is no such proof.

    Now, what’s the significance of all this? The first surprinsing consequence is that if GC is unprovable, we will never know it for sure!

    In other words, we will never know if GC is a "good example" for one of these unprovable statements predicted by the Gödel’s theorem… (unless of course, GC turns out to be provable)

  10. Dmitriy says:

    You’re actually wrong and I’ll tell you how.

    First of all, let’s examine the concepts of truth and falsity in a formal system like Number Theory.

    NT, as any formal system, is composed of two things: a set of axioms and a set of transformation rules. Axioms are your starting point. These are the basic statements you assume to be true without proof. Transformation rules are rules used for transforming one statement of the formal system into another.

    For example, one of the axioms of NT is that for any number x, x + 0 = x. An example transformation rule is addition.

    Using the axioms and transformation rules, you can now build up a system of true statements – theorems. You take an axiom, you (correctly) apply a transformation rule to it, and you get a theorem. You take a theorem, you apply a transformation rule to it, and you get another theorem. The reverse is also true. If you want to determine the truth value of a statement, you apply a series of transformation rules to this statement until you get a theorem or an axiom. False statements – falsehoods – work much the same way. In order to prove a statement false, you need to apply transformation rules to it until you reach a a known falsehood. Incidentally, this means that if you accept one falsehood as a theorem, you accept them all. And that’s why inconsistency is such a bitch.

    For example, we can apply addition to the above axiom. For any two numbers x and y, x + 0 + y = x + y. A true statement – a theorem.

    To put it simply. A statement of NT is a theorem (a true statement) if and only if there exists a set of transformation rules that transform this statement into an axiom or a theorem. A statement is false if and only if there exists a set of transformations that link this statement with a falsehood. That is the definition of truth and falsity in formal systems.

    Your demonstration is circular. You assumed that a statement must be true or false and then you proved it. What Gödel showed us is that there are statements that NT can express, but cannot link to an existing theorem or falsehood – that is, they have no proof or disproof. And since truth value is contingent on there being one or the other, these statements have no truth value. They are simply undecidable.

    Certain statements HAVE been proven as undecidable. Gödel’s statement is an obvious example and was outlined in the previous post. The Continuum Hypothesis is another. Euclid’s Fifth Postulate is undecidable within Absolute/Affine Geometry. You can Google for these terms if you like, as well as various statements like "undecidability," "undecidable conjectures," and the like.

    As an exercise to the blogger, attempt to prove Euclid’s Fifth Postulate as true or false using only the first four postulates. 🙂

    -D

  11. Adi Oltean says:

    >> You’re actually wrong and I’ll tell you how. […] To put it simply. A statement of NT is a theorem (a true statement) if and only if there exists a set of transformation rules that transform this statement into an axiom or a theorem. A statement is false if and only if there exists a set of transformations that link this statement with a falsehood. That is the definition of truth and falsity in formal systems.

    Not really. There are essentially two different ways to define the concept of truth in any logic.

    1) The proof-based method – defined as you mentioned above. You constructively establish the truth of certain statements by mathematical proof. This is your definition of “mathematical truth” which is good enough for most of the mathematics (but not in our case). Sometimes, truths established this way are called "syntactic truths" because a proof is an algorithm that operates at the expression syntax level.

    2) The semantic-based method. This is based on a completely different (and more complex) approach. The basic idea is to establish a set of valid interpretations for a certain logical expression. The definition of semantic truth is this: Given a set of axioms A, a statement S is true (in semantic sense) if and only if ALL interpretations that are true for the set of axioms A are also true for the statement S.

    The concrete form of an interpretation depends on the type of the underlying logic. In the case of the propositional logic, an interpretation of a formula F(x,y,z…) is simply a certain true/false assignment of the underlying ground terms (x,y,z,..) coupled with a precise method that evaluates a composite formula to be either true or false. As an anecdotic fact, there is also a generalized theory of semantic-based interpretations called Model Theory. This theory provides a nice algebraic framework that rigorously defines interpretations for most flavors of mathematical logics.

    The notion of semantic truth might be confusing at first but it is really the cornerstone of modern logic. I will give three examples:

    a) In propositional logic, the “interpretation” of an expression X assigns to each free term in the expression with a certain value (either true or false). Let’s verify the classical Modus Ponens deduction rule: (((P) AND (P-> Q)) -> Q). In propositional logic, this is statement is always true semantically. It is not hard to see why. All you have to do is to verify the Boolean expression above for the four cases when both P and Q can be either true or false.

    b) For the first-order predicate logic, things are a little bit more complicated. The semantic truth for this statement: S1 = “Every X in set A has property P(X)” (where P(x) is a certain predicate) can be determined in this way:

    Truth(S1) = AND[for every x in A] P(X)

    In other words, if A = {x0, x1, x2, …} then Truth(S1) = P(x0) AND P(x1) AND …

    So, if there is at least one x0 for which P(x0) is false, i.e. zero, the entire expression (and therefore its semantic truth value) is false. Otherwise it’s true.

    The semantic truth for the predicate P is recursively determined in the same manner.

    c) Let’s pick one more example. In the particular case of the Goldbach conjecture (in NT, to follow your notation), the semantic truth is again always well-defined:

    Truth(GC) = AND (foreach n natural > 2) IsDecomposableInPrimes(n)

    Where:

    IsDecomposableInPrimes(n) = (there are at least two primes X and Y such that n = x + y);

    So, irrespective to the fact that GC is provable or not, its semantic truth is ALWAYS well defined, according to the expression above!

    In general, there is a big difference between semantic truth and syntactic truth. Interestingly enough the relation between these two concepts is tightly coupled with the soundness/completeness of the set of axioms.

    – The set of axioms is sound if and only if the syntactic truth of an expression X implies it semantic truth. (I.e. any provable statement is semantically true, relative to the particular set of axioms)

    – The set of axioms is complete if and only if the semantic truth of an expression X implies it syntactic truth. (I.e. there is a proof for any semantically true statement – again, relative to the axioms in discussion)

    The good news is that in the simple cases of propositional logic and first-order predicate logic these two concepts are demonstrated to be equivalent, following from the Herbrandt’s soundness and completeness theorems.

    However, in the particular case of first-order arithmetics we know for sure that semantic truth and syntactic truth are sometimes different, following from the Godel’s first incompleteness theorem.

    >>> As an exercise to the blogger, attempt to prove Euclid’s Fifth Postulate as true or false using only the first four postulates. 🙂

    This is statement is obviously unprovable since we have all these Euclidean and non-euclidean geometries. But note that this doesn’t imply that it’s semantic truth value is either true or false. Same thing goes for the Continuum hypothesis, etc.

  12. Dmitriy says:

    Sorry for the late reply.

    I see what you’re saying about semantic truth vs. syntactic truth, but the problem is that semantic truth is largely irrelevant in modern theoretical math (whereas it was prior to 1936). Semantic truth is intangible. You can’t use the innate truth of a statement unless you have a purely syntactic proof of the truth.

    Yes, the truth of the GC is well defined, even in the absence of proof, given a certain set of axioms. Number Theory may not be the set of axioms in question. In which case, the GC will remain undecided.

    As a final, anecdotal piece of evidence, I give the fact that mathematicians a lot smarter than us are still working hard at proving the GC unprovable.

  13. Adi Oltean says:

    You are right about the semantic truth being intangible. The way it is defined doesn’t allow us to calculate its value except for very simple cases. Yet, it’s still there, and it’s well defined.

    On the other side, I am puzzled by your statement that mathematicians are still looking for the proof that GC is unprovable – I just demonstrated above that there is no such proof saying that GC is unprovable… it is very unlikely that such a simple demonstration would be overlooked by dedicated mathematicians.

    That said, I admit that I might be wrong after all – if you see any mistakes in this demonstration please let me know! Note however that by "GC being true" I meant that "GC is semantically true".

  14. Dmitriy says:

    First, I’d like to say with no hint of ill will that the discussion of interpretations of formal systems (like NT) is a bit of a red herring. A formal system is not dependent on an interpretation. You can assign it one and use it to think about the formal system, but whatever truths you deduce from the interpretation do not have to be consistent with the underlying formal system.

    And this is the problem.

    You are coming into this discussion with a preconceived notion of NT as a means of manipulating whole, natural numbers. That’s NOT what NT actually is. NT is a system of axioms and transformation rules. None of this is ambiguous. But NT, as well as geometry and other formal systems, also contains the notion of "undefined terms." In geometry, these terms are point, line, etc. In NT, these are "number", the symbols "there exists a number," and "for any number," as well as some others. Our different interpretations of formal systems come from different interpretations of these undefined terms.

    Truths in NT are syntactic or "actual" truths. Truths in our understanding of natural numbers are semantic or "vacuous" truths that depend on a particular interpretation.

    If I may digress for a minute, I’d like to point out the parallel to Geometry once again because it’s such a very good example. Saccheri set out to prove that the negation of the Fifth Postulate was repugnant to the nature of numbers. Of course, it is repugnant to our understanding of geometry (our interpretation, if you will), but the formal system of Geometry – the first four postulates – does not bear that out. So Saccheri assumed the negation of the Fifth Postulate and ended up proving a great deal of facts about this non-Euclidean geometry that were clearly incorrect in the face of common sense, but never once found a contradiction.

    Saccheri’s notion of Geometry was based on the conventional interpretation of the undefined terms of "point" and "line." If you take a different interpretation – with "point" meaning a pair of antipodes on a sphere and "line" being a great circle – you get the perfectly consistent and unrepugnant Spherical Geometry.

    The Fifth Postulate has been proven to be unprovable within Affine Geometry. Gödel’s statement, the Continuum Hypothesis, and a few others have been proven to be unprovable within NT. That is, neither these statements, nor their contradictions, add an inconsistency to NT. It’s not really that hard to see with Gödel’s statement, and the same argument would apply to the GC if it were proven to be unprovable.

    Gödel’s statement is commonly described as "this statement has no proof." More specifically, it says "the Gödel number corresponding to the proof of this statement does not exist." Gödel numbers, if you recall, specify a way to "encode" statements (and sequences of statements) into numbers. If it’s true, that means that there does not exist a Gödel number corresponding to the proof of G (Gödel’s statement). Simple enough, right? If it’s false, that means there does exist such a number.

    This is where it gets really interesting, and I hope I can explain it correctly. Please let me know if some of my language is unclear.

    Let’s assume that it actually is false and try to find the contradiction.

    We can assemble a set of statements that say something to the effect of:

    1 is not the Gödel number corresponding to the proof of G

    2 is not the Gödel number corresponding to the proof of G

    3 is not the Gödel number corresponding to the proof of G

    …and so on. In addition, we have our statement that we want to show to be contradictory:

    There exists a Gödel number N corresponding to the proof of G

    This seems to be a contradiction, doesn’t it? And it is, in a way. It’s called an omega-inconsistency and it comes from our interpretation of the formal system of NT. If we reinterpret the symbol "there exists a number" as "there exists a generalized number" and "for any number" as "for any generalized number," the apparent contradiction goes away. This introduces the possibility of numbers other than naturals into our formal system and our system of statements above only enumerates all the natural numbers.

    This reinterpretation completely encompasses our previously known truths about natural numbers. Any theorem we’ve already proven is still true, it’s just that we know that NT allows for some numbers that don’t fit in with our old interpretation. These numbers – supernatural, transfinite, or just infinite numbers – form the basis for such mathematical disciplines as Nonstandard Analysis, Nonstandard Number Theory, and Transfinite Theory.

    If you abandon your notions of NT dealing with only familiar, natural, finite numbers, neither G nor ~G introduces a contradiction! The same exact argument, which I attempted to outline in brief in my second post, will apply to the GC if it is proven to be unprovable.

    A part of this post was paraphrased from the book recommended in previous comments – Gödel, Escher, Bach by Douglas R. Hofstadter. He really does a wonderful job of explaining it, so if you don’t quite agree with the above, you might want to check it out. Or just reply and I’ll try to explain it a bit more clearly. 🙂