Thread: Examples of Gödel's incompleteness theorem

Dear all,

I'm wondering whether there are any other examples of Gödel's incompleteness theorem in action other than statements such as "this statement is not true" (i.e. formalizations of the liar's paradox)?

If not: then how exactly is his theorem relevant in the broader field of mathematics, seeing that only very specific kinds of metamathematical statements are involved?

Godels incompleteness theorem is a statement about formal systems at least as complex as the natural numbers. It says that we cannot design an algorithm that is capable of proving all true statements that a formal system could make. Because of it, we can not use a system to prove the internal consistency of the system itself. We can't pull ourselves up with our own bootstraps so to speak. It is completely relevant to the very broad fields of mathematics (logic); metalogic or set theory for example, or even computer science, where questions about the provability of formal statements comes into the fore ground. However, for most areas of mathematics it is of very little practical consequence.

One example is Continuum hypothesis. I don't know how important this is; i.e. whether any results with practical use would be affected if it were either true or false.

I think it is quite fundamental so far as the question is concerned of whether there is a Theory of Everything that can be described in terms of mathematics. Is maths complete enough to explain everything in the universe, including the universe itself ? Is that even possible ?
Do I have an answer ? No.
Comments, anyone ??

I suppose one way of looking at it is that mathematics is a tree of possibilities. Wherever there is an undecidable theorem (like the continuum hypothesis) you end with two different branches depending whether you assume it is true or fasle.

A bit like geometry: you can choose Euclidean (parallel lines never meet) or different forms of non-Euclidean. It isn't necessarily that one is right and one is wrong, they have different applications.

ER, well don't get too carried away guys!

Here's a fun way to think of one Goedel's 2 theorems, but it is just for illustration

The set of symbols - letters - that make up an alphabet is finite, and therefore countable. In our case it has cardinality 26

Suppose we make use of this fact to enumerate these, and, for reasons I will explain shortly, designate as follows: A = 10, B = 20, C = 30 etc.

Then a word will be of the form 2050140 = BEN. This is clearly a number, i.e. an element in . Now I can stick these words together to make a sentence, sentences to make a paragraph, paragraphs to make a book, etc, and I will still have an element in . (Incidentally, I can include capitals, punctuation and spaces, and the following argument is the same)

OK, so I simply used zero as a delimiter to avoid under-counting, that is, I know that 1020 = AB and not L = 12, which could happen if 12 = AB or L. So we see there is no word, sentence, paragraph, library, or even collection of libraries (Congress of Libraries??) that cannot be expressed as an element in the countable set

Now is the powerset on the natural numbers - it is the set of all subsets of . Cantor's diagonal argument can be used to show this is uncountable. So, let us say that in a complete theory of numbers, for each element (subset recall) of the powerset there must be at least one true statement (using words, sentences, paragraphs,....), so there must be uncountably many true statements of number theory.

{Edit in red follows, thanks to Strange's eagle eyes} Now "removing" a countable set of any cardinality, even if it infinite, from an uncountable set set still "leaves" us with an uncountable set. Therefore, there must be uncountably many MORE potentially true statements of number theory than there are words, sentences, paragraphs, books or libraries (since these are countable).

It follows that any system that tries to describe number theory as a complete set of true statements is doomed to failure. This is example of an incompleteness theorem.

Originally Posted by Guitarist

Now "removing" a countable set of any cardinality, even if it infinite, from an countable set set still "leaves" us with an uncountable set.

I assume that should be uncountable?

Yes, well spotted. Edit progress

I have a question/comment related to the first post on this thread. The question whether any other examples existed of "unprovable" statements other than the liar's paradox one that Godel referenced in the proof of his incompleteness theorem.

If other such "unprovable" statements did exist (which I do not believe), how would you know when you encountered one? e.g. for years, Fermat's last Theorem may have been "unprovable" - but it finally was proven some years ago. Is Goldbach's Conjecture unprovable? how abut the various conjectures related to the infinite number of twin primes, etc.? Are they unprovable?

This leads me to think that the only statements that are unprovable are only these self-referencing ones (for which there are an infinite number of, to be sure) - but are there any others? and how would you know if you encountered one?


Can we say they're unprovable just because they have not yet been proven.

My point is that it would be impossible to construct a list of all truths

Originally Posted by ggimpoli

Can we say they're unprovable just because they have not yet been proven.

There are two classes of unprovable theorems: those we can prove are unprovable and those we can't.

Originally Posted by ggimpoli

I have a question/comment related to the first post on this thread. The question whether any other examples existed of "unprovable" statements other than the liar's paradox one that Godel referenced in the proof of his incompleteness theorem.

If other such "unprovable" statements did exist (which I do not believe), how would you know when you encountered one? e.g. for years, Fermat's last Theorem may have been "unprovable" - but it finally was proven some years ago. Is Goldbach's Conjecture unprovable? how abut the various conjectures related to the infinite number of twin primes, etc.? Are they unprovable?

This leads me to think that the only statements that are unprovable are only these self-referencing ones (for which there are an infinite number of, to be sure) - but are there any others? and how would you know if you encountered one?


Can we say they're unprovable just because they have not yet been proven.

My point is that it would be impossible to construct a list of all truths

But ,list or not...cardinality aside, Shouldnt there be a set containing all truths needed to describe everything in a certain moment?

Isnt there a logical space? Containing all possibilities?

In a vacuous way yes, for example consider the theory of arithmetic where we take as axioms all true statements about arithmetic (the so called true arithmetic). This is a complete theory and so everything that is true about the natural numbers is provable in it (kind of by design) but there is no way to determine if a general statement is an axiom of this theory.

Originally Posted by river_rat

In a vacuous way yes, for example consider the theory of arithmetic where we take as axioms all true statements about arithmetic (the so called true arithmetic). This is a complete theory and so everything that is true about the natural numbers is provable in it (kind of by design) but there is no way to determine if a general statement is an axiom of this theory.

Hi! You surprise me. How is a proof achieved? How do we search through the axioms? Youre not pulling my leg,are you?
Sigh...I wish I were a Mathematician...First thing I would do would be to prove the Banach Tarski theorem wrong

A proof of X in this theory consists of pointing at the axiom X if it is true and at the Axiom ~X if it is false. Hence the vacuous nature of the theory.

Why do you want to prove the Banach-Tarski theorem wrong? That would be like proving the parallel postulate in Euclidean geometry?

Originally Posted by river_rat

A proof of X in this theory consists of pointing at the axiom X if it is true and at the Axiom ~X if it is false. Hence the vacuous nature of the theory.

Why do you want to prove the Banach-Tarski theorem wrong? That would be like proving the parallel postulate in Euclidean geometry?

Isnt it the one where you disassemble a sphere and then use the pieces to build two spheres identical with the first?
I either misunderstand or it cant be so, since then a perpeetum mobile seems possible.
Just turn the second sphere into energy and repeat the process ad inf.

Er... wait a minute... (pinching my arm...yes i AM on speaking terms with a mathematician...)

Would you perhaps help me by checking an argument of mine for errors?

Suppose:
1 x = "x is not true"
Then:
2 x is true if and only if "x is not true" is true
And:
3 x is true if and only if x is not true
Therefore:
4 It is not true that x = "x is not true" (QED)

Is the argument valid?

Edit: Oh well if you understand Tarski then I might as well show the whole argument:

Look at the following system:

1 x is not true
2 x = "x is not true"

For some values of x sentence 2 is empirically true:_

1 sentence 1 is not true
2 sentence 1 = "sentence 1 is not true

And out of 1 and 2 we get:
3 sentence 1 is true

but if sentence 2 is BOTH logically false and empirically true it is not well formed,
and therefore sentence 3 doesnt follow after all! (QED)

PS: If so far I am not in error then next stop is Goedel.

A goedel sentence is a selfreferential sentence x such that x = "x is not provable"

Let us see if such "undecidable" sentences may exist...Suppose:

1 x = "x is not provable"
Then we get:
2 x is provable if and only if "x is not provable" is provable
And since provable sentences are true we get:
3 x is provable if and only if x is not provable

And the conclusion is unavoidable (?):

4 There is no sentence x such that x = "x is not provable"

This is an indirect proof perhaps, but isnt it valid nonetheless?

There are no undecidable sentences unless you break the laws of logic!