Godel's Theorem: Discuss and Explain

  • Thread starter drag
  • Start date
  • Tags
    Theorem
In summary: So, in summary, Godel's completeness theorem states that a sentence is provable if and only if it is true in all models of the theory. This leads to the question of whether we can pick our axioms cleverly enough to decide all statements, and Godel's Incompleteness Theorem says that under certain conditions, we cannot. These conditions require the theory to be consistent and to include a subset of the axioms of arithmetic. The theory must also have axioms that are reasonable, meaning they can be explicitly defined through some function, computer program, or method.
  • #1
drag
Science Advisor
1,105
1
Greetings !

I bet the "2" got the attention of all
the people this is mainly intended for...

But, it's not what you might think, it's
just that I have a similar thread (without
the "2" :wink:) in the Philosophy Forum and
I invite you people, aspecialy the experts,
who may've not visited it for a while(like
Hurkyl for example) to make your comments
and ASPECIALY explanations there.

Of course, in order for this thread not to
be wasted as a mere announcement I'd like to
hear your opinions here too. Maybe a more
technical and expert duscussion can start here.
(In which my humble role will probably only be
to read the words of wisdom of other members.)

Thanks !

Live long and prosper.
 
Mathematics news on Phys.org
  • #2
Which one? He has a Completeness Theorem and two Incompleteness Theorems?
 
  • #3
Originally posted by damgo
Which one? He has a Completeness Theorem
and two Incompleteness Theorems?
Really ?!
Let's hear'em ! :smile:
(Completeness Theorem ? Sounds fascinating... )
 
  • #4
Defs: A "theory" is the set of sentences derivable from some set of (not necessarily finite) axioms. For example, the theory of arithmetic contains the basic axioms of addition, multiplication, etc, and all sentences provable from them. A "model" is a particular 'real' mathematical entity or structure, such as the normal natural numbers. The natural numbers are a model of the theory of arithmetic; but there are other models (nonstandard natural numbers.)

Godel's completeness theorem states that a sentence S in part of some theory T if and only if S is true in all models of T. So, if we can't prove some statement S from our axioms, there exists a mathematical structure modelling the axioms where S is true, and a different one where "not S" is true.

This leads to the question, well, can we pick our axioms/theory cleverly enough so that we can always prove either "S" or "not S"? In other words, make it so that we are fully specifying the model we want and don't leave any questions undecided? Godel's Incompleteness Theorem says that under certain conditions, no. There is always some statement that can't be proven or disproven.

The conditions require that the set of axioms be reasonable, and the theory be strong enough -- it has to include 'Q', a subset of the axioms of arithmetic.

---

Two examples of this sort of thing are the continuum hypothesis and the axiom of choice. Neither are provably true nor false in standard ZF set theory. We could choose to add them as axioms, of course, and get the theory ZFC+CH; but Godel's Incompleteness theorem assures us that we can't ever get rid of these types of undecidable statements. No matter how many you add as axioms, there will always be more.
 
  • #5
Originally posted by damgo
The conditions require that the set of axioms
be reasonable, and the theory be strong enough
-- it has to include 'Q', a subset of the
axioms of arithmetic.
Could you elaborate on those 2 points a bit,
please, damgo ?
Does "reasonable" mean that the axioms mustn't
conflict with each other ?

Thanks !
 
  • #6
Thats especial :)
 
  • #7
Actually, that whole blurb I gave assumes the theory is consistent, ie the axioms don't conflict with one another. If your axioms are inconsistent, then you can prove every statement and the theory is worthless.

OK, 'Q' is just a slightly watered-down version of arithmetic: you have the number 0, a successor function, addition, multiplication, and most but not all (eg there is no commutativity of addition) of the axioms of arithmetic. Oftentimes people just say Godel's IT applies to any theory that includes arithmetic, which is true, but technically you need slighly less than all of arithmetic.

The reason for this condition is that the proof of Godel's IT makes use of a "Godel numbering," a way of assigning a unique natural number to any sentence in the theory. If our theory can handle enough of arithmetic, then we can manipulate Godel numbers and use them as a way to 'talk' about the theory inside the theory. For example, there is a formal logical sentence that defines (all the sentences that are true of their own Godel number.)

---

The 'reasonable' condition is one of those technical ones that are confusing to formally explain but rather intuitive. We could 'go through' all possible sentences S, decide which of S or (not S) we want to be true (when consistency does not choose for us), and imagine adding those to our axioms. Then we would have an infinite set of axioms -- in fact our axioms would include every true statement (ie everything in the theory) -- and the theory would be complete, Godel's IT would not apply.

But obviously this is dumb. Axioms are supposed to be something we explicitly specify, not that we pull in via cheap nonconstructive definitions. The formal condition usually used is that the set of axioms be 'recursively enumerable'; this corresponds to the intuitive notion of being able to explicitly define them through some function, computer program, method, etc. IIRC there are various strengthenings and versions of the incompleteness theorem that use slightly different conditions here -- sigma-consistency comes to mind -- but I don't remember them well, and anyways, that's a rather tangential point.
 

What is Godel's Theorem?

Godel's Theorem, also known as Godel's Incompleteness Theorem, is a mathematical proof that states that in any formal axiomatic system, there will always be true statements that cannot be proven within that system.

Who discovered Godel's Theorem?

Godel's Theorem was discovered by Austrian mathematician Kurt Godel in 1931.

Why is Godel's Theorem important?

Godel's Theorem has significant implications for mathematics, logic, and computer science. It shows that there are limits to what can be proven or known using formal systems, and it has led to further developments in these fields, such as the study of undecidable and uncomputable problems.

Can you give an example of Godel's Theorem in action?

One example of Godel's Theorem in action is in the field of number theory. Godel's Theorem shows that within any formal system for arithmetic, there will always be true statements that cannot be proven within that system. This means that there will always be unsolvable mathematical problems.

How does Godel's Theorem relate to other mathematical theories?

Godel's Theorem is closely related to other mathematical theories, such as the Halting Problem and the Theory of Computation. These theories also deal with the limits of formal systems and what can be proven or computed within them.

Similar threads

Replies
1
Views
2K
  • General Discussion
Replies
15
Views
3K
  • Art, Music, History, and Linguistics
Replies
1
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
2
Views
2K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
1
Views
2K
  • Sticky
  • Feedback and Announcements
Replies
2
Views
494K
Back
Top