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

• Anonymous
  January 13, 2005
  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.

• Anonymous
  January 13, 2005
  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. :)

• Anonymous
  January 13, 2005
  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...
  

• Anonymous
  January 13, 2005
  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.
  

• Anonymous
  January 13, 2005
  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". ;-)

• Anonymous
  January 14, 2005
  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
  

• Anonymous
  January 14, 2005
  I can say that if such a proof existed, it would be both elegant and completely impossible for me to understand. :)

• Anonymous
  January 14, 2005
  "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?

• Anonymous
  January 14, 2005
  >> 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)
  

• Anonymous
  January 15, 2005
  The comment has been removed

• Anonymous
  January 15, 2005
  >> 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.
  

• Anonymous
  January 18, 2005
  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.

• Anonymous
  January 18, 2005
  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".

• Anonymous
  January 18, 2005
  The comment has been removed

• Anonymous
  August 22, 2007
  PingBack from http://tanveerbadar.wordpress.com/2007/08/23/how-smart-is-your-fridge/

• Anonymous
  March 24, 2008
  PingBack from http://caferestaurantsblog.info/antimail-another-puzzle-gdel-goldbach-and-other-g-names/