There are many proofs based on a "tertium non datur"-approach (e.g. prove that there exist two irrational numbers a and b such that a^b is rational).


But according to Gödel's First Incompleteness Theorem, where he provides a constructive example of a contingent proposition, which is neither deductively (syntactically) true nor false, we know that there can be a tertium.


**My question:** Are all proofs that are based on that principle useless since now we know that a tertium can exist?



Is no proof based on "tertium non datur" sufficient any more after Gödel?
You are confused.


The best way out of your confusion is to maintain a very careful distinction between strings of formal symbols and their mathematical meanings. Godel's theorem is, on its most primitive level, a theorem about which strings of formal symbols can be obtained from other strings by certain formal manipulations. These formal manipulations are called proofs, and the strings which are obtainable in this way are called theorems. For clarity, I'll call them formal proofs and formal theorems.


In particular, let G be a string such that G is not a formal theorem and neither is NOT(G). It is still true that G OR NOT(G) is a formal theorem. Moreover, if G IMPLIES H and NOT(G) IMPLIES H are both formal theorems, then H will be a formal theorem; because there are rules of formal manipulation that allow you to take the first two strings and produce the third. I believe that Douglass Hofstader discusses this in a fair bit of detail when he goes over Godel's theorem.


The above is mathematics. Next, some philosophy. I don't find it helpful to say that G is neither true nor false. It find it more helpful to say that our systems of formal symbols and formal manipulation rules can describe more than one system. For example, Euclid's first four axioms can describe both Euclidean and non-Euclidean geometries. This doesn't mean that Euclid's fifth postulate has some bizarre third state between truth and falsehood. It means that there are many different universes (the technical term is models) described by the first four axioms, and the fifth postulate is true in some and false in others.


However, in any particular one of those universes, either the fifth postulate is true or it is false. Thus, if we prove some theorem on the hypothesis that the fifth postulate holds, and also that the fifth postulate does not hold, then we have shown that this theorem holds in every one of those universes.


There are fields of mathematical logic, called constructivist, where the law of the excluded middle does not hold. As far as I understand, that issue is not related to Godel's theorem.


