Monday, 03 January, 2005

I've known for a while that in an inconsistent system of axioms it is possible to prove any statement. What I did not know is just how easy this fact is to prove. A system is inconsistent if you can prove a statement and its negation is true within the axioms of that system.

Here's how to prove any statement in an inconsistent system. Statement A is the statement you want to prove. Statement B is the inconsistency: both the statement and the negation of the statement can be proven. Initially we don't know that we can prove A but we know we can prove B. Let's define a function called "IsProvable" that returns true if the sentence passed to it is provable and false if it is not. We know IsProvable(B) is true but at this stage we're unsure of what value IsProvable(A) wil take. If we take the logical OR of IsProvable(A) and IsProvable(B) the result will be true. However, we know that the negation of B is also true. So IsProvable(~B) is true which implies that IsProveable(B) is false. We already know that IsProvable(A) OR IsProvable(B) is true and since IsProvable(B) is false we must conclude IsProvable(A) is true.

That might seem like a bizarre argument but the proof is sound mathematically. The argument is bizarre because the system is inconsistent.

The fact any statement can be proved in an inconsistent system should not be confused with undecidability. A sentence is undecidable in a system if there is no proof of the sentence or its negation within the axioms of that system. In an inconsistent system a proof for both the sentence and its negation can be found.

Simon

13:25:06 GMT | #Randomness | Permalink