Propositions that are not provable

[xxxxtt]

I want to know more about propositions wich are true, but not provable.Can someone give some examples?
Is there a criteria for seeing that a statement is not provable?

[gauss202]

Statements which are true, but not provable from other statements, are called axioms. They are statements which are taken to be true on faith or from experience.

One such statement from Euclidean Geometry is that the sum of the interior angles of a plane triangle always equals 180 degrees. This statement is seen to be "true" from experience, but it cannot be proven from other statements.

All systems of logic, including mathematics, are based on axioms (or basic truths) and on well-formed definitions. From those axioms and definitions, you can go on to prove theorems using logic. This is how Euclid wrote and proved things in The Elements.

A more unsettling fact, however, was proven by Godel in the early 1900s. Godel showed that in any system of logic that includes arithmatic, there will either be some theorems which cannot be proven either true or false; or there will be some theorems which can be proven both true and false!! Simply put, any mathematical system will either be incomplete or inconsistent. Furthermore, Godel went on to show that you can never prove that any mathematical system is either complete or consistent.

This was very unsettling to mathematicians when it was discovered, but most mathematicians went on to have faith that our current mathematical system was consistent - even if they could never prove it. And they thought that any such theorems which showed incompleteness would have to be highly pathological.

An example of such a theorem was found, however, in the 1930s by Cohen. It's now called the Continuum Hypothesis. The theorem states that there do not exist a subsets of the real numbers with cardinality greater than that of the rational numbers, and less than that of the entire real set. While it's not obvious whether this statement is either true or false in any real sense, it must be either taken or rejected as an axiom. From the standpoint of the rest of mathematics the theorem is both true AND false!

[MindFlyer]

I think some of the above is quite inexact and may lead to the misunderstanding of critical facts. I'll try to clarify it a bit.

First of all, it's not necessarily true that no axiom of a theory can be proven from other statements. An axiom set is simply any set (finite of not) of logical statements, and a model of a theory is a structure (i.e a set endowed with some functions and relations...) that satisfies all the axioms of this theory. If an axiom can be proven using just the other axioms of the same theory, then it's redundant. It can be removed without changing the models of the theory, but it's OK also if we keep it. The axioms might even contradict one another, and in this case we say that the theory is inconsistent or contraditory. An inconsistent theory has no models, so any statement is both true and false in such a theory.

Then, it's not true that the statement of Euclidean Geometry "the sum of the interior angles of a plane triangle always equals 180 degrees" is an axiom. It's actually a theorem, in fact Euclidean Geometry has just 5 axioms, that are a lot "simpler" than this one, and can be combined to prove it. Of course, nothing changes if we take this one as an axiom as well (together with the classical 5), but it's just redundant, so Mr. Euclid wisely decided not to take it, and to prove it later on.

Moreover, G�del did NOT prove that there are some theorems which cannot be proven true or false. A theorem of a theory is by definition a sentence that CAN be proven in that theory. First, we must say that G�del's theorems are related just to First Ordel Logic (FOL), that is a simpler and less expressive logic in which we can use quantifiers just on variables, and not on relations. An example of a theory in Second Order Logic is the famous 2nd Order Peano Arithmetics, whose axioms are the classical ones related to the definition of successor, and of +, * and < (which are all First Order axioms, as they only quantify on variables), plus the induction axiom. This last axiom is a Second Order one, as it quantifies on unary relations (or, in other words, subsets of the structure). This theory is actually cathegoric, as it has just one model (up to isomorphisms...), that is obviously N (Dedekind's theorem).

On the other hand, we are not happy with 2nd Order Peano Arithmetics, as there's a theorem stating that we cannot define a formal system of logical inference to prove theorems in this theory, as the set of true sentences in N is not recursively enumerable. That is, there's no algorithm that can decide in a finite time if any given sentence is true in N. On the contrary, in FOL we can indeed define a formal mean of proving theorems (modus ponens, and so on...), and moreover there's a nice theorem (G�del's completeness theorem) stating that a sentence of FOL is true in every model of a theory if and only if it can be proven formally from the axioms of that theory.

So, to get rid of the induction axiom of 2nd Order Peano Arithmetics, we introduce an infinite set of new First Order induction axioms, one for every sentence in FOL. So, instead of a big induction axiom, we have many small First Order induction axioms. Since the FOL sentences are countable many, and the subsets of N are not, it's obvious that these infinite axioms cannot substitute the big one without losing some subsets of the models, and in fact it happens that the so formed theory (1st Order Peano Arithmetics) is not cathegoric. Of course, there's N among its models, but there are also MANY non-standard models (i.e. models that are not isomorphic to N).

There are many interesting theorems about non-standard models of 1st Order PA, one of wich stating that there's no algorithm to compute the function + or * in any given non-standard model (i.e. they're not recursive: Tennenbaum's theorem). But the most famous result is G�del's incompleteness theorem, basically stating that there's a sentence that is true in some models of 1st Order PA, and false in some other models (G�del also showed how to "build" such a sentence). It immediately follows from this theorem and from G�del's completeness theorem that there are some First Order sentences which are true in N, but not provable from the axioms of 1st Order PA, i.e. they're true sentences, but not theorems.

Then, it's inexact that G�del proved the impossibility to prove the completeness or consistency of a theory. This is just what he did in his incompleteness theorem: he proved that 1st Order PA is incomplete! However, he did prove (in his 2nd incompleteness theorem) that any theory in any FOL language that can "encode" statements and proofs cannot prove its own completeness. For example, suppose you have an encoding for sequences of natural numbers with natural numbers (such an encoding is easily defined using the Chinese remainder theorem). Using this encoding, you can define another encoding for sentences and proofs. And then, you can say by G�del's 2nd incompleteness theorem that the sentence "for any sentence s, there's a proof of s or a proof of not(s)" cannot be proven in 1st Order PA. We need encodings for sentences and proofs so that we can form the sentence above just using quantifiers on numbers, and so getting a FOL sentence.

Finally, the Continuum Hypothesis is not an example of G�del's incompleteness theorem, as its statement is not in FOL. In fact, it quantifies on subsets of R, so forming at least a 2nd Order statement. Actually, the FOL theories of real numbers, complex numbers and Euclidean Geometry are all complete, meaning that they can formally prove or disprove any FOL sentence.

Note that G�del's completeness and incompleteness theorems have similar names, and this is sometimes source of much confusion, as they're not mutually contradictory, and actually cohexist in 1st Order PA. The completeness theorem states that in First Order Logic, a sentence is true in every model of a theory if and only if it's provable from the axioms of this theory (i.e. it's a theorem). The incompleteness theorem states that there are true sentences in N that cannot be proven from the 1st Order axioms of Arithmetics.

Of course, whether proving both a theorem called "completeness" and one called "incompleteness" just in a few years can drive a man to madness, I can't tell.

[kajal]

How can we prove that the set of sentences of A (A be an Axiom System)
that are true in all models of A is an r.e.(recursively enumerable) set.

[MindFlyer]

This is true in First Order Logic, and it's easy to prove indeed, using Godel's Completeness Theorem.
By this theorem we know that the set of sentences that are true in all models of a theory is precisely the set of sentences that are provable in that theory. By provable, we mean that these sentences can be derived from the axioms (and tautologies) by applying a finite set of inference rules (for example modus ponens). By applying again and again these inference rules to the axioms and to the theorems obtained so far, we obtain all provable sentences.
Now, we clearly see that this set is r.e.: take a sentence, and start building the tree of proofs within the given theory, comparing each theorem with the given proposition. Provided that the nodes of the tree are built in the correct order (for example in breadth-first order), then this algorithm stops if and only if the given proposition is a theorem.

[robert.milleker]

Example of an undecidable proposition:

'I am an idiot.'

(

Also, have a look at this:

http://www.geocities.com/robert.milleker

)