The Limitations of Logic

- Consistency, completeness, and Gödel's theorems.

- This is not really a hint to SolvingConundrums, but it is a prerequisite for understanding some of the solutions properly.

What is a logic? What is a mathematics? It is a set of axioms and some rules for deducing true statements.

Logic is the set of rules and axioms we have agreed to use. I will assume that we agree on these. (I refer to the mainstream choice, I know there are other candidates, like fuzzy logic, and I may come back to that later.)

A consistent system is one in which not both 'P' and 'not P' is true. In other words, a system where there is no statement P that is both true and false. Why is it so bad to have one such statement in our logic? Well, assume that we have one such statement, and call it P. Then for any other statement Z we get that P implies Z, because P is false. Then, since P is true, we can deduce that Z is true. The conclusion is that every statement in our logic is true (including 'not Z'). This is senseless – there is no difference between true and false anymore!

A statement-complete system is one in which every statement is either true or false, so that there is no unknowable thing. Having an incomplete system means that we can't know everything, even in principle, and that is bad. (When doing science we often think that there is just a matter of time and patience before we understand something.) This concept, I just made up, and it is a bad concept. What is truth, really, in a logical system? We still want to avoid epistemology (philosophy), so what then is truth? It is something that can be proved by using the axioms and logical rules.

In Logic/Mathematics we desire proofs. If something is true (say 'P'), then we want there to exist a string of logical arguments showing that 'P' is true. If something is true, but there is no way of knowing that it is true, that is bad. Our definition of truth in a logical system is that which can be proved within the system. A system where every statement (which can be constructed in the system) is either provably true, or provably false, is known as a complete system. Wikipedia calls this syntactically complete, and gives a nice reformulation: A system is complete if and only if "no unprovable axiom can be added to it as an axiom without introducing an inconsistency."

Let me be clear: We will only use one concept, so that truth and provability is the same thing in Logic. It is possible to make a distinction between the two, but I don't want to do that.

What Gödel tellsus is that we can never have a complete system (given that it includes basic number theory and some extra technicalities). If humanity some day decides on a logical system to use for all eternity, then either that system is inconsistent or incomplete according to Gödel's proof. In other words, since we require our system to be consistent, there will be statements that are neither true nor false in our system.

What do we call these statements that are neither true or false in our logical system? We call them independent or undecidable. Examples of these are the axiom of choice (independent in ZF-logic), and the continuum hypothesis (independent in ZFC-logic). These examples are (to mathematicians) interesting statements, so the problem that Gödel found is not some weird technicality, but something we have to deal with.

What can be done with an independent statement? We can choose to add it as an axiom, or we can choose to add its negation as an axiom. Logic does not care which we choose, it will still be consistent regardless of our choice! If we want to model observable reality, however, we might care about which is "true", as in which choice results in the best model of reality.

When we have added our axiom (or its negation), then our logic is a new and more powerful logic, where more statements are provable (also known as 'theorems'), and where more statements can be constructed. Again Gödel's proof works, and we can find new (and possibly interesting) statements that are independent in this new logical system. And so on, and so on.

Here, those who are familiar with mathematics might want to try to cheat, and add an infinite sequence of axioms, each based on a previous level's known independent statements. Even this (and generalizations of this) will not work at all. The logic you end up with is either incomplete or inconsistent.

Gödels general examples that always work in a logical system T (not true nor false):

(A Gödel number is a proof translated to a number in number theory.)

"There is no Gödel number to this statement using the logical rules of system T"

(i.e.: There is no proof of this statement.)

"The logical system T is complete"