Gödel's Incompleteness Theorem

Hi,

I was wondering if someone could please provide an example of something that is "unprovable"? Is the Continuum Hypothesis such an example?

Also, I remember reading a while ago about the possible existence of theorems that were "unprovable" and so were true (because if they were false there would exist a counter-example, which would be a proof that they were false). However, surely this is a contradiction? Surely any example that could be proven false by a counter example cannot be proven to be unprovable?

I hope those questions make sense...

Am I right in thinking that the Axiom of Choice is unprovable? But its just taken as fact.

Quote:

---

Originally Posted by Swlabr

Hi,

I was wondering if someone could please provide an example of something that is "unprovable"? Is the Continuum Hypothesis such an example?

Also, I remember reading a while ago about the possible existence of theorems that were "unprovable" and so were true (because if they were false there would exist a counter-example, which would be a proof that they were false). However, surely this is a contradiction? Surely any example that could be proven false by a counter example cannot be proven to be unprovable?

I hope those questions make sense...

---

Unprovable in the sense required here means unprovable within a given axiomatic system (complete with rules of deduction), which (usually) is rich enough to contain arithmetic, meaning Russel and Whiteheads system from their Principia Mathematica.

If a theorem is unprovable (that is can neither be proven nor disproven) in such a system there can be no counter example since just displaying it is a proof that the purported theorem is false.

So any candidate for theoremhood within such a system that has a counter example cannot be unprovable, so all unprovable theorems posses no counterexamples.

(there is probably more than one fundamental error in the above)

CB

Quote:

---

Originally Posted by Swlabr

Hi,

I was wondering if someone could please provide an example of something that is "unprovable"? Is the Continuum Hypothesis such an example?

Also, I remember reading a while ago about the possible existence of theorems that were "unprovable" and so were true (because if they were false there would exist a counter-example, which would be a proof that they were false). However, surely this is a contradiction? Surely any example that could be proven false by a counter example cannot be proven to be unprovable?

I hope those questions make sense...

---

(There may as well be errors in my answer since I don't specialize in logic but that's the way I understand it, and I'd be pleased to have the opinion of someone more knowledgeable about it)

I think a theorem may be unprovable in two ways, relatively to its truth.

"Provable" presumes that a list of axioms has been chosen. A theorem is true if it is true in any mathematical model that satisfies the axioms. A theorem is provable if it can be deduced, step by step, using the axioms and usual deduction rules (this leads to a kind of constructive vision of truth: is "true" (= provable) what I can prove is true).

A theorem may be unprovable because:

1) The axioms are not sufficiently precise to settle the question: there are models where the theorem is true, others where it is false. This is the case of Euclid's fifth postulate, it can't be proved from the others (cf. non-Euclidean geometries). I think this is the case of CH (the continuum hypothesis) or for AC (axiom of choice), but I'm not sure, and I'm not sure we know or can know. In a sketchy way, that would mean that the abstract mathematical universe that is defined by the "usual axioms" is actually not completely defined by them, and some properties remain free, like CH. We can choose to work with a more precisely specified model of maths by choosing to take CH as a new axiom. Or by choosing to take its negation. Both choices are equally wise (logically), they induce no additional contradiction.

2) The axioms are sufficiently precise so that the theorem is true in every model, but the truth of the theorem can't be proved from the axioms. This is where Gödel's incompleteness theorem is involved: it gives an example of such a situation. But not a very simple or interesting one... A few "elementary" examples were found since then, the most well-know is Goodstein's theorem I think.

Quote:

---

Originally Posted by Laurent

2) The axioms are sufficiently precise so that the theorem is true in every model, but the truth of the theorem can't be proved from the axioms. This is where Gödel's incompleteness theorem is involved: it gives an example of such a situation. But not a very simple or interesting one... A few "elementary" examples were found since then, the most well-know is Goodstein's theorem I think.

---

Ah, okay. It is this case I am interested in. Thanks for the example.