Goedel's Incompleteness Theorem is essentially a 2-part result, whose second facet establishes that all conventional axiom systems are unable to prove a theorem corroborating their own consistency. This latter effect, called the Second Incompleteness Theorem, is quite counter-intuitive because human beings seem to implicitly believe that their cogitation processes are consistent (in order for them to gain the needed motivational energy for cogitation). Yet quite surprisingly, the Second Incompleteness Theorem has demonstrated that conventional logics cannot corroborate such a seemingly very natural consistency assumption.

The main goal of Willard's research project will be to explore to what extent a logic formalism can wiggle around the Second Incompleteness Theorem and formalize a type of at least partial instinctive faith in its own consistency. Willard has already published several articles exploring boundary-case exceptions to the Second Incompleteness Theorem and generalizations of it, thus establishing the basic foundational concepts for this quite unorthodox research approach

Willard's planned investigation will have an inter-disciplinary emphasis, being germane to computer science, mathematics, the cognitive and information sciences, philosophy and linguistics. It will show that while self-justifying axiom systems have a very unconventional outer shell, they do retain an ability to simulate most of the practical computer-oriented knowledge of the data needed by any arbitrary logically valid axiom system. It will also show how computerized floating-point real number arithmetics behave very differently from integer arithmetics and how self-justifying formalisms retain an ability to expand their knowledge base by hopping and skipping form one formal self-justifying axiom system to another (via the use of Mind Change Theory and sundry trial-and-error experimental methodologies).

The Second Incompleteness Theorem is sufficiently robust that its evasion is feasible only in a limited context, where the specified logic possesses a component that is unconventional in a nontrivial way. The reason that such unconventional logics are of interest is that human beings evidently possess some type of innate instinctive understanding of their own self-consistencies (at least under some formal definitions of consistency). It is therefore desirable to understand what type of algorithmic processes and foundational precepts from symbolic logic can simulate a Thinking Being's conception of its own consistency (in either a full or partial sense). The goal of this research project will be to investigate the nature of and the potential uses and implications of logics that possess some type of well-defined partial knowledge of their own consistency.

Project Report

Goedel's Incompleteness Theorem is widely considered to be one of the great discoveries of the 20th century. Goedel was called ``one of the 20 greatest thinkers of the 20th century'' by the March 29,1999 issue of Time Magazine. Goedel's work on incompleteness was technically a 2-part discovery. His ``First'' Incompleteness Theorem specified that no logic or computer program can isolate all the true statements of arithmetic. The ``Second'' Incompleteness Theorem then showed that conventional logics cannot prove a theorem confirming their own consistency. This latter theorem is counter-intuitive because human beings implicitly presume that their cogitation process is useful (and thus consistent). However, the Second Incompleteness Theorem demonstrates that conventional logics cannot corroborate such a consistency assumption. The purpose of Professor Willard's research under grant CCR-0956495 was to help unravel this mystery. This topic is especially mysterious because a self-referencing methodology, discovered by Kleene, has established that essentially all conventional logics S can be expanded into a broader system, say S+ , which differs from S by recognizing its own consistency. In particular for a fixed deduction method D, the system S+ will differ from S by including an additional axiom, called SelfRef(S,D), which is defined below. It is a self-viewing axiomatic statement that enables S+ to look at itself and immediately presume its own consistency: @ The axiom system S+ (which represents the union of the axiom system S with THIS SENTENCE looking at itself) has the property that there exists no proof of 0=1 from S+ under D's deduction method. Kleene (1938) noted the statement @ was well defined. The resulting system S+ is, however, usually inconsistent (essentially because it gets confused via its own giddy self-confidence). These considerations led Kleene and most logicians to conclude that the statement @ is typically useless. In seven earlier papers published during 2001-2009 in the Journal of Symbolic Logic, Annals of Pure&Applied Logic and Information&Computation, Willard meticulously examined this paradigm for various different inputs of S and D (to determine which precise inputs (S,D) allow for an exception to the preceding paradigm). The barriers imposed by Goedel's Second Incompleteness Theorem are clearly quite real and formidable. The reason this research is of interest is that humans are presumably unable to develop the motivational energy for cogitation without possessing some type of well-defined instinctive belief in their own consistency. The main surprising aspect of Willard's most recent research concerned ``Reflection Principles''. It explored the well known fact that conventional axiom systems cannot prove the validity of the following ``Reflection Principle'' for arbitrary sentences X: # If an axiom system A proves the statement X as a ``theorem'' then X is true. The intuitive reason axiom systems A are unable to prove # for arbitrary sentences X is that X could be a ``Goedel Sentence'', which essentially states that ``There is no proof of me''. It is well known that if an axiom system A could prove the statement # for the case where X was such a Goedel Sentence then A would be inconsistent (making it entirely useless). This paradigm has caused many logicians to suspect that it is impossible to devise interesting versions of reflection that apply to Goedel sentences. Willard found, however, a method for escaping from this dilemma. It is to let X* denote a statement that has equivalent properties to X under logic's Standard Model and to change the last four words of #'s reflection principle to read as: ``then X* is true'' It turns out that Willard's self-justifying systems can prove the validity of this ``translational modification'' of # for a broad class of logical sentences. including the formidable ``Goedel sentences''. This result is appealing because it does not force Willard's self-justifying logics to either prove or disprove a forbidden Goedel sentences (which asserts ``There is no proof of me' ' ). This is because the self-justifying formalisms are unable to determine whether or not the sentences X and X* are actually equivalent. This new formalism suggests that an axiom system will know why it is profitable to prove a theorem X. (This is because such a proof will imply at least that X's counterpart of X* is true.) Many other surprising aspects of Willard's work are described in the report at http://arxiv.org/abs/1108.6330). None of these results, obviously, question the core robustness and significance of Goedel's Second Incompleteness Theorem. They do, however, suggest that a subtle distinction, between the purist and translational forms of reflection principles, enables a thinking being, whether human or computerized, to develop an operational appreciation of the underlying epistemology motivating its cogitation process. This essentially corresponds to an operational mathematical definition for roughly capturing the notion of Instinctive Faith. In summary, Willard's findings indicate that although the Incompleteness barrier will prevent a logic from recognizing its own consistency under the strongest definition of this construct (that Goedel's famous research had explored), it is, indeed, feasible for a logic, whether it either be computerized or have a human basis, to introspectively appreciate how its own thinking is a very useful exercise. Professor Willard would be glad to answer telephone inquires about the philosophical implications of this research at 518-442-4284,

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Application #
0956495
Program Officer
Dmitry Maslov
Project Start
Project End
Budget Start
2009-09-15
Budget End
2011-08-31
Support Year
Fiscal Year
2009
Total Cost
$100,000
Indirect Cost
Name
Suny at Albany
Department
Type
DUNS #
City
Albany
State
NY
Country
United States
Zip Code
12222