Monday, February 1, 2016

Incompleteness

Some curious results surrounding consistency and inconsistency.

A system is called inconsistent if it proves a statement is true while also proving the negation of that statement is also true.

A system is called consistent if it is not inconsistent.

result #1: in an inconsistent system, every statement formulated in that system is both provable (thus considered true) while its negation is also provable (thus considered false).

In an inconsistent system, every statement is both true and false, and provably so. Thus inconsistent systems are viewed as kind of useless.

result #2: Russell proved in 1901 that what was current set theory in his time, the basis for most math, was inconsistent. Thus set theory in Russell's time was rendered useless because the statement like 2+2=Pi is both provable and 2+2 doesn't equal Pi is also provable.

So set theory was revamped in such a way that Russell's result and all other known problems with naive set theory (as it is now called) were avoided. The hope was that set theory would be consistent and that its consistency would be provable. Also, the hope was that set theory would be complete: every true statement was provable.

Gödel came along and proved something that was considered shocking at the time:

result #3: if a system can both express arithmetic and is consistent, then it is incomplete. Incomplete means there is a statement in that system which is both true but not provable.

That's kinda crazy sounding: a system like set theory should be able to express arithmetic. And it can. Now if a system is also assumed consistent (and remember inconsistent systems are "useless"), then there is a statement in that system which is both true and not provable.

Said differently, any system in which all statements in that system which are true are also provable and which can express arithmetic are also inconsistent. This was considered to be a shocking result.

Gödel did so in 1931 by concocting/discovering a way to formalize the statement "This statement is not provable."

For ease/indolence, let S be the statement that says "S is not provable."

Again in bivalent logic, there are two possibilities:
S is true or
the negation of S is true.

Option 1: S is true. Then S is not provable.
Option 2: S is false. Then S is provable. We define every statement which is provable to be true (in that system).

Option 2 is ruled out because we assume the system is consistent in Gödel's theorem. Since the system is assumed to be consistent, it is never the case that a statement and its negation are both true. In option 2, we proved that S is false and true which would make the system inconsistent.

Therefore, option 1 must be the case. IOW, there is a statement (namely S) which is both true and not provable.

Loosely speaking, a system is called incomplete if there is a statement in that system that is both true and not provable. This concludes the sketch of the proof that if a system can express arithmetic and is consistent, then it is incomplete.

If you're working on a problem involving trying to prove something, you might be faced with the possibility that that something is true (which is good in a sense) yet cannot be proved (no matter how much time you have or how clever you are).

This is bad. You might have picked a statement which is true but you will never be able to prove it!

Now the statement S which says "S is not provable" might seem like a trick to push through this argument but several examples of more interesting statements like the "halting problem" are neither provable nor disprovable. Such statements are called formally undecidable.

Incidentally, the existence of a statement S = "S is not provable" is called a self-referencing statement. This is basically where arithmetic is used and needed in the hypothesis of Gödel's incompleteness result: one needs arithmetic in what's now called Gödel numbering in order for S to exist and be a statement.

Also, there are different versions of incompleteness in many-valued logics (ones that "extend" classical logic to more than two truth values) but I am not super familiar with the interaction of incompleteness and many-valued logic. It has been extensively studied; I can say that much.