# Provability Check

I have heard of (still not learnt) Gödel's incompleteness theorem which says that there are some statements unprovable.

Now suppose we suspect that there is some rule. And the rule remains unproven despite several decades', or several centuries' effort (just as the conjectures). Then we suspect a possibility that actually the rule itself is unprovable.

So, is there some trivial method to determine whether a statement is provable or not? I guess there is, for scientists have marked some statements as axioms and have left them unproven.

If this question is not too stupid to be answered, and any of you like to answer it, please provide an example where the unprovability of a well-known axiom is proved (preferably, simple geometric axiom such as playfair's axiom).

• Playfair's axiom is not unprovable : "in the context of Euclidean geometry it is equivalent to Euclid's parallel postulate"; thus, we can prove it assuming Euclid's fifth postulate. – Mauro ALLEGRANZA Mar 17 '15 at 18:23
• Well, then please prove that the parallel postulate is unprovable. – Ayan Biswas Mar 18 '15 at 1:07
• You are "mixing" two different concepts : in an axiom system, an axiom is independent ffrom the others when it is not provable from them. In this sense, the parallel axiom is independent from the other axioms of Euclidean geometry. G's Theorem applies to formal system; in the context of a formal system, the axioms are obviously provable because in this context to say that a sentence $\varphi$ is provable means : "there is a derivation from the axioms ending with $\varphi$". Thus, any axiom is derivable with a 1-line derivation, and so is provable. – Mauro ALLEGRANZA Mar 18 '15 at 12:47

Assume that T is a set of axioms and $\varphi$ is a rule. If you can find a model which makes T true, but $\varphi$ false, then according to Gödels completeness theorem, we can not deduce $\varphi$ using only the axioms in T.

To provide a visual example if you have only the axiom "There exists three points", then you may not prove the statement "There exists three points which are in a line", since we may have a model which consist of three non-colinear points. Hence our axiom is true, yet not the statement.

This method is a good way, if you have a nice set of axioms, to prove that they can not prove each other. However this method is not trivial in general. If there would exist a trivial way to show that a statement is provable or not, we would not have so many unproved theorems.

Axioms should not bee seen as unproven statements, but rather original assumptions. Many different axiom systems may be considered when doing mathematics, but the most common is the so called "Peano arithmetic" which describes the axioms for regular counting. The important part of a set of axioms is that they are consistent, i.e. do not contradict each other. At times, assumptions made are found to be inconsistent, in which case all mathematics done for it can essentially be discarded. One part of Gödels incompleteness theorem is that we can not, using only the axioms of Peano arithmetic, show that they are consistent.

There is in general no trivial method to show that a statement is or is not provable in a given axiom system. We usually call such statements independent.

In set theory and foundational mathematics we often talk about consistency of statements. For example CH (the continuum hypothesis, which is the statement that there are no sets whose size is strictly bigger then the size of the natural numbers and strictly smaller then the size of the real numbers) has been proven independent of the ZFC axiom system.

The proof of independent usually consists of two parts. I will focus on CH over ZFC just to simplify the exposition.

You must prove that ZFC + CH is consistent assuming that ZFC is consistent. For CH this is usually done by referring to L or Godel's constructible universe.

Then you must also prove that ZFC + $\neg$ CH. In case of CH this is usually done by using a technique called forcing.

Even though CH is probably one of the easier (sensible) statements that can be proved independent neither of the two parts is particularly easy to do.