Incompleteness Theorem's General Idea

[NoahsArk]

I am interested, from a lay man's perspective mainly, in the incompleteness theorem but not sure I understand even on a general level what is being said. From what I recall, it states something like the following: in all formal mathematical systems there are certain statements that can't be proven. Firstly, I could not even find a definition of what is meant by "formal mathematical system". Secondly what does the theorem mean on a practical level? Does it mean we can't be sure of anything? Does it mean there are certain problems we will never be able to solve? If the later is true, which kind of problems.

Thank you!

 

[fresh_42]

The proof is not constructive, so we do not know which statements can be decided and which cannot. For all practical purposes you may assume that all statements we usually deal with can either be proven or a counterexample can be found. This is due to the fact that those statements range only over a very small part of all thinkable statements, and that they are worded in a way which is close to proofs or counterexamples. But in the end, we do not know. Fermat's last theorem took over 300 years until it could be proven. The Riemann hypothesis and the P=NP problem are both overdue. But the reasons we don't have proofs yet are not difficult to understand: for Riemann we have checked it for trillions of examples, but for all is still another step. Similar had happened with Fermat. For P=NP the difficulty is, that to prove lower bounds of complexity is hard, since it needs to be shown that something does not exist. So even if we cannot prove something, we know why. This is far from being undecidable.

Look at the proof why there are more real numbers than could be counted:
Imagine we had a count and had them all listed from one, two, three etc. Then we change the first digit of number one, the second digit of number two, etc. Now we write down the number which is obtained by all these changed digits, and this number was certainly not on our list. Hence we have found a number which wasn't counted, aka listed. This means the real numbers cannot be listed.

The proof of the incompleteness theorem goes along these lines. What you have asked is basically: which number wasn't listed? And there is no answer, since I didn't know your list. The point is, that the argument applies to any theoretical list. And the numbers which are not listed are simply too many to know. Nevertheless, we calculate with the numbers we have and our buildings do not crash.

 

[WWGD]

I am interested, from a lay man's perspective mainly, in the incompleteness theorem but not sure I understand even on a general level what is being said. From what I recall, it states something like the following: in all formal mathematical systems there are certain statements that can't be proven. Firstly, I could not even find a definition of what is meant by "formal mathematical system". Secondly what does the theorem mean on a practical level? Does it mean we can't be sure of anything? Does it mean there are certain problems we , never be able to solve? If the later is true, which kind of problems.

Thank you!

Edit: Essentially, for systems ( look up axiomatic formal calculus; a collection of axioms and rules of inference) beyond a certain level of complexity, it is impossible to prove its consistency inside, with methods of, the system. There is no algorithm that may take a finite collection of axioms, finite set of inference rules to deduce the whole of Mathematics.

 

[Periwinkle]

I suggest for context, do a search for the continuum hypothesis, an undecidable statement in ZFC and bring in questions. Essentially, for systems ( look up axiomatic formal calculus; a collection of axioms and rules of inference) beyond a certain level of complexity, it is impossible to prove its consistency inside, with methods of, the system. There is no algorithm that may take a finite collection of axioms, finite set of inference rules to deduce the whole of Mathematics.

I see that no one could ever find any relationship between the continuum hypothesis and the Gödel's incompleteness theorems.

Continuum hypothesis undecidability has nothing to do with Gödel's theorems.

 

[WWGD]

I see that no one could ever find any relationship between the continuum hypothesis and the Gödel's incompleteness theorems.

Continuum hypothesis undecidability has nothing to do with Gödel's theorems.

Yes, you're right, I was thinking of something else, let me edit. The rest is correct,though. My bad.
Edited.

 

[NoahsArk]

Thank you for the responses.

Look at the proof why there are more real numbers than could be counted:
Imagine we had a count and had them all listed from one, two, three etc. Then we change the first digit of number one, the second digit of number two, etc. Now we write down the number which is obtained by all these changed digits, and this number was certainly not on our list. Hence we have found a number which wasn't counted, aka listed. This means the real numbers cannot be listed.

I'm not sure I understand: if we write down 1,2,3,4,5, etc, then we change 1 to 5, 2 to 4, 3 to 2, 4 to 3, and 5 to 1, we now have 5,4,2,3,1. We still have the same numbers listed, just in a different order?

Also, what is the proof that there are more real numbers that can be counted?

Today I read this definition for the incompleteness theorem:

"Gödel’s incompleteness theorems show that pretty much any logical system either has contradictions, or statements that cannot be proven!"

Using the real numbers example that you gave, what part of that shows what a "logical system" is, and what about it can't be proven? Also, I am assuming that "logical system" is synonymous with "formal mathematical system" which is the term I used in my original post.

Essentially, for systems ( look up axiomatic formal calculus; a collection of axioms and rules of inference) beyond a certain level of complexity, it is impossible to prove its consistency inside, with methods of, the system.

I would appreciate if you can give some basic examples of this. Is chess (or tic tac toe), a logical system? If so, what makes it a logical system? What are examples of things that are not logical systems? With a game like chess or tic tac toe, if they are "logical systems" what are examples of statements that can't be proved?

I appreciate the help.

 

[fresh_42]

I'm not sure I understand: if we write down 1,2,3,4,5, etc, then we change 1 to 5, 2 to 4, 3 to 2, 4 to 3, and 5 to 1, we now have 5,4,2,3,1. We still have the same numbers listed, just in a different order?

If we do this with the complete (infinite) diagonal, then $5,4,3,2,1, \ldots$ cannot be on the list.

Also, what is the proof that there are more real numbers that can be counted?

Because any enumeration allows a number which wasn't listed, so there can be no complete enumeration.

Today I read this definition for the incompleteness theorem:

"Gödel’s incompleteness theorems show that pretty much any logical system either has contradictions, or statements that cannot be proven!"

Using the real numbers example that you gave, what part of that shows what a "logical system" is, and what about it can't be proven? Also, I am assuming that "logical system" is synonymous with "formal mathematical system" which is the term I used in my original post.

This was only an analogy, a - maybe overly - simplification. There is more to do to prove Gödel. The idea is, that which ever finite alphabet we use to write down all of our proofs, there are still theorems which we have not proven.

I would appreciate if you can give some basic examples of this. Is chess (or tic tac toe), a logical system? If so, what makes it a logical system? What are examples of things that are not logical systems? With a game like chess or tic tac toe, if they are "logical systems" what are examples of statements that can't be proved?

I appreciate the help.

https://en.wikipedia.org/wiki/Logic#Logical_systems
The most used system is first order logic, or predicate logic.

I don't know of examples which cannot be decided.

 

[WWGD]

An example of a logical system is that of Euclidean geometry with , say, A-->B and A then B as a rule of inference . You have a collection of statement s you take to be true and rules that allow you to conclude a new statement S' from a collection of axioms and/or other statements.

 

[hyksos]

Firstly, I could not even find a definition of what is meant by "formal mathematical system".

Mathematicians began to create proofs of theorems where every individual character in each word of the proof is in the right place. They call these "well-formed formulas" or wffs. The proof proceeds by very mechanical deductions following rigid rules (almost like programming languages are rigid). They call these Hilbert-Style proofs. They very much could be checked over by a machine.

Once a proof exists, the leading statement is called a "theorem" and then it can be used in other proofs and this forms a bootstrapping system called a Deductive System. Deductive System is a synonym for "formal mathematical system".

Most humans don't actually write proofs like this, preferring to skip over laborious sections that are obvious to the reader. But in the backs of everyone's mind , we all know that it could be written out in a formal way in a Hilbert-Style proof.

Secondly what does the theorem mean on a practical level?

Before Godel's theorems entered mathematics, a conjecture would either be false, or it would be true. One or the other. After Godel, a conjecture can be three possible things: (1) True (2) False (3) Undecidable.

There is a very dramatic history about how undecidibility entered mathematics, involving Georg Cantor and Godel. Cantor practically went insane while manipulating different kinds of infinite sets.

Does it mean we can't be sure of anything?

No. Godel also wrote Completeness Theorems too. I had to prove one of them in a uni math course, but generally, nobody has heard of them. Completeness theorems ensure us that 2+2 does actually equal 4.

The Incompleteness Theorems touch on topics that have not come up in civilization since the time of Athenian Greece. It turns out that mathematics cannot prove every conjecture it can state. Worse : not all conjectures follow from others logically.

Does it mean there are certain problems we will never be able to solve? If the later is true, which kind of problems.

We know today that it is impossible to decide whether a string of bits can be compressed losslessly. More specifically, such an algorithm cannot exist in the general case.

A lot of cryptography used on the internet assumes that factoring numbers is hard. There may exist a shortcut to factor large numbers quickly, instead of trying every combination by rote. Nobody knows if such an algorithm exists. Godel Incompleteness allows for the existence of such an algorithm to be "undecidable". If that were the case, mathematicians would have a good reason to stop hunting for it.

 

[Periwinkle]

I have to say that I cannot agree with all the assertions made. I just want to comment on the Gödel theorem.

Before Godel's theorems entered mathematics, a conjecture would either be false, or it would be true. One or the other. After Godel, a conjecture can be three possible things: (1) True (2) False (3) Undecidable.

It cannot be said at all that Gödel would have proved that mathematical statements can be categorized in this way. On the contrary, he showed that there is an arithmetic statement that is true but cannot be proved in formal arithmetic.

 

[hyksos]

Yes. The theorem is still "true" in another axiomatic system.
Decidable versus Undecidable would act like an orthogonal attribute of a theorem against True versus False.

 

[phyzguy]

Most people view Godel's incompleteness theorem negatively, in that it gives boundaries on what can be proven. In Penrose's "The Emperor's New Mind", Penrose argues that it is wrong to view Godel's incompleteness Theorem negatively, and it should be viewed in a positive sense. I'm probably mis-stating what he said, but as I recall he is saying that, since there are statements that are true, but cannot be proven within the axiomatic system, this means that we are able to "rise above" the axiomatic system and see the truth of statements which cannot be proven.

 

[member 656954]

I am interested, from a lay man's perspective mainly, in the incompleteness theorem but not sure I understand even on a general level what is being said

Have you read Hofstadter's book, Gödel, Escher, Bach: An Eternal Golden Braid? It is a reasonably accessible - if very long - treatment of this topic and should very much answer any question you have regarding incompleteness.

 

[pinball1970]

Have you read Hofstadter's book, Gödel, Escher, Bach: An Eternal Golden Braid? It is a reasonably accessible - if very long - treatment of this topic and should very much answer any question you have regarding incompleteness.

Ill look check this out as I have been reading about this while looking up Russell and Frege
This is featured on numberphile too, a great series on YT.

 

[Jarvis323]

This is a good watch, along with the associated links.



For something simplistic, read this:

George Boolos (1989) built on a formalized version of Berry's paradox to prove Gödel's Incompleteness Theorem in a new and much simpler way. The basic idea of his proof is that a proposition that holds of x if and only if x = n for some natural number n can be called a definition for n, and that the set {(n, k): n has a definition that is k symbols long} can be shown to be representable (using Gödel numbers). Then the proposition "m is the first number not definable in less than k symbols" can be formalized and shown to be a definition in the sense just stated.

https://en.wikipedia.org/wiki/Berry_paradox#Formal_analogues
And here is a translation of Gödel’s seminal proof.

http://hirzels.com/martin/papers/canon00-goedel.pdf