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...

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.

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. 🙂

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…

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.

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". 😉

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

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

"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

reallyimpact 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?

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

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.

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".

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

isrepugnant 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. 🙂

PingBack from http://tanveerbadar.wordpress.com/2007/08/23/how-smart-is-your-fridge/

PingBack from http://caferestaurantsblog.info/antimail-another-puzzle-gdel-goldbach-and-other-g-names/