Hierarchical Introspective Logics

      This research was initially stimulated by the announcement in
June 1993 of a proof of the FLT conjecture ("Fermat's Last Theorem").
Once again a mathematical question that might conceivably have been
unanswerable was being answered by the efforts of humans to find an
acceptable proof of a standing conjecture. 
     Earlier the famous 4 Color Conjecture had yielded to an attack 
aided by computers.
     So the question that arose in my mind was that of whether or not
there actually exists any mathematically interesting true mathematical
assertion (such as, for example, perhaps the Riemann Hypothesis) which
cannot be proved and which must ultimately be accepted as a new axiom
if mathematics is to proceed in terms of assertions and proofs (Satz; 
Beweis).
     I was of course aware of Goedel's establishment of the existence
of assertions concerning the natural integers that are not provable
modulo the proof rules of specific given formal systems and also of
the general results on undecidability which also imply the existence
of such assertions that are true but not provable in the context of
a given formal system.
     The specific sort of formula that is produced by the construction
of Goedel, or by Rosser's variation on Goedel's construction, is true
but not provable within the formal system on the basis of which it was
constructed. However an acceptable mathematical proof, in verbal form,
was given by Goedel of the truth of his constructed formula provided
that it could be assumed that the formal system at issue was ideally
consistent.
     Thus the Goedel formula or assertion is not really of itself
mysterious; it is provably true, on a common-sense basis, and it shows
therefore that the formal system studied must have been inadequate to
achieve the ideal goal of completeness. (It can be remarked that 
logical systems of a more limited application, specifically systems 
not adequate for the proof of general propositions of "number theory", 
for example the "calculus of sentences", can be complete. For systems 
with a narrower scope of applicability completeness does not introduce
paradoxes.)
     If a Goedel or Goedel-Rosser assertion is added to one of these
incomplete systems as an axiom then one obtains a new logical system
with similar characteristics to the original. It is thus again 
incomplete and again a Goedel assertion can be found within it, a 
formula that is true but that is not provable by the formal machinery 
of the system.
     But better than adding the Goedel or the Goedel-Rosser assertion
to the initial system as an axiom one can instead add to it an axiom
of consistency. That is one can add an axiom stating that the initial
system was formally consistent. This does not also say that the new
system including the added axiom is itself consistent.
    The axiom asserting formal consistency could be expressed with
the use of a scheme of Goedel numbering for the formulae expressible
in the initial system and also for proofs possible in that system. 
Then it simply asserts that no such proof can result in a formal proof 
of falsehood (which is represented by the second truth symbol of the 
pair of T and F).
    It is known that adding such an axiom of formal consistency to the
initial system makes it then possible, using the added axiom, to prove
either the Goedel assertion or the Rosser assertion for that system
(the initial system).


                             Extended Systems

    This sort of supplementary axiom, which serves naturally to deal 
with the incompleteness of a logical system, this supplementation 
produces a natural extension of the original system. This type of 
extension process was studied in the mid- and later 30's by Turing 
in a project that became his Ph.D. thesis at Princeton.
    One thing that is notable is that when an axiom is added that 
asserts formal consistency of an initial system that this added axiom 
is not itself included in relation to the consistency issue; so the 
extended system formed by the addition of that axiom is not itself 
asserted to be consistent by the added axiom. And thus, for the 
newly formed extended system to be itself axiomatically stated to 
be consistent requires the introduction of a second added axiom in 
a parallel proceeding.
    Turing considered this process in his paper (the thesis) "Systems 
of logic based on ordinals" published in 1939 in Proc. Lond. Math. 
Soc. But Turing did not construct his systems, his towers of 
extension, on a basis of "ideal ordinals", corresponding to the 
mathematician's traditional way of thinking of mathematical objects, 
but rather he worked in terms of arrays of ordinals which were indexed 
somehow by ordinary integers and described by a table of ordering by 
which the order relation of any two of the indexed entities was 
specified. And this order table was required to be specified by 
recursive functions.
    When I began to think about the same general theme, that of
axiomatically extending an initially specified logical system so as 
to "correct" or fill in for the incompleteness of the type discovered 
by Goedel, it occurred to me that Turing's concept of how ordinals 
could be used may have been intrinsically too limiting and that 
it would be desirable to explore what might be done with a less 
restrictive concept of ordinal numbers than that of the recursively 
presented sets of them used by Turing.
    There are many logical "paradoxes" that can arise if we speak 
loosely about ordinals and their definability. On the other hand I do 
think that Turing's concept of usable ordinals was too restrictive to 
allow the related extension scheme to proceed to really interesting 
results relating to incompleteness.


                     Another Form of Incompleteness

    The discovery of incompleteness by Goedel was supplemented in 
the 30's by the work of Turing, Church, and others who showed that 
there was "undecidability" with regard to the totality of assertions 
possible within a formal system of the same general category as those 
for which Goedel's discovery applied. This showed that it was not 
possible, systematically, to decide which assertions were true and 
which false. And consequently to that there could not exist proofs 
for all of the true assertions since that would make possible the 
systematic decision process. Thus a true but unprovable assertion 
MUST EXIST although this route, via "undecidability", did not produce 
any specific example.
    But much more recently a paper was published by Paris and 
Harrington showing that a popular form of Peano arithmetic called PA- 
(upper suffix -) was incomplete because of the lack of a sufficiently 
strong "axiom of infinity". This result was very interesting since it 
showed that incompleteness could have this sort of a connection with 
"knowledge of infinity" and with the possibilities for infinite 
arguments such as proofs by induction.
    Of course there are many long known paradoxes, or potential 
logical traps, that arise from talking about infinity. One of these 
can be illustrated by imagining two mathematical logicians named 
Adams and Bentley. So Bentley says "Let beta be the limit ordinal 
(number) which is the least ordinal that is larger than any ordinal 
alpha definable in the formal language of the system of Adams. This 
illustrates the paradoxes that inherently arise because we seek 
to "talk about" infinite concepts but we have only finite resources 
to use for the actual purpose of communication in words. Any book 
written by humans has a text that contains only a finite amount 
of information, a certain number of "bytes" as it were. And this 
illustrative paradox relates to the classical "Burali-Forti paradox" 
of logic and set theory.


                  Dangers of Paradoxes, Personal Caution

    I am speaking about a research project that is not fully complete
since I have not yet written up and submitted for publication any 
paper or papers describing the work. Also the details of what axioms 
to use and how to select the basic set theory underlying the 
hierarchical extension to be constructed are not fully crystallized.
    I have also a great fear of possible error in studying topics in 
this area. It is not rare, historically, for systems to be proposed 
that are either inconsistent or that have unexpected weaknesses. So 
I feel that I must be cautious and proceed without rushing to a goal. 
And this psychology of fear has also inhibited me from consulting 
other persons expert in logic before I could feel that I had gotten 
my own ideas into good shape.


                       The Overview Concept

    It is notable that Goedel's construction of an unprovable, yet 
true, proposition in a generic sort of formal system is accompanied 
also by a proof, under reasonable hypotheses, of the truth of that 
"unprovable" proposition. How is this achieved? Well, of course, the 
proof does NOT occur WITHIN the formal system for which the Goedel 
proposition was constructed, rather it is given verbally in the normal 
style of argument for published mathematical papers.
    But it can be observed that if another logical system were 
constructed with the specific goal of studying the first system 
and the proofs possible within it and if this "overview" system 
also included axioms to the effect that the machinery of procedure 
of the first system is truth-preserving and that the axioms of 
the first system are true then it would become provable, in this 
overview system, that the first system is consistent and also 
"Omega-consistent". And from these proofs would follow, in the 
overview system, the proof of the truth of a Goedel assertion for 
the first system.
    These observations relate to what Turing studied in his paper 
"Systems of logic based on ordinals". In hindsight one could say that 
Turing's concept of extension was (italicize) THE UNIQUE AND NATURAL 
CONCEPT so far as the range of the finite ordinal numbers is 
concerned. 
This results in an ascending ladder of systems in which each successor 
is more complete than any of its predecessors but this ladder ascends 
only through the finite ordinal numbers, 0th, 1st, 2nd, 3rd, 4th, 
5th, .... nth, ... and does not reach any transfinite levels.
    Of course Turing did actually concern himself with transfinite 
ordinal levels but he did not have a way of uniquely describing them. 
(This was the "invariance" problem in the terminology of his paper.)
    Although there seems to be essentially no confusion about the 
naming or proper description of finite ordinal levels, beyond that 
there are serious difficulties that are classically known. Thus 
mathematically there should be a non-enumerable totality of ordinal 
numbers each of which has only an enumerable set of predecessor 
ordinals. Then how many can we expect to properly name or describe 
in the words of any precise mathematical language? And what can be 
said about the description: "the least ordinal not thus properly 
describable"? Relating to this is the mathematical property of the 
ordinals that any subset of them has a least member. This shows 
by illustration how difficult it is to form an ideal concept of 
definable ordinals or of canonical names for ordinals.
    Turing's hierarchy of levels in any one of his systems was based 
on association of the levels with ordinals which were themselves 
associated with natural integers through a recursive description of 
a subset of all ordinals. Unfortunately this specification did not 
have uniqueness, or "invariance" as he called it, a property that 
he knew was most desirable.
    In my own thinking, after a long period of study and after 
encountering the problem that although one could talk about "ideal" 
(or mathematical) ordinals one would need names for them in order to 
be able to refer to them in formulae of a formal system. Ultimately 
I came to the idea that instead of associating the levels of a system 
with ordinal numbers they could instead be associated with definitions 
of ordinals. This is not the same as indexing the levels by ordinals. 
Two quite different definitions might easily define the same 
mathematical ordinal yet also it could be very difficult to determine 
the precise comparative relationship of two different definitions, 
each of them stating the definition of a specific mathematical 
ordinal.
    And it is also easily observed that any specified language would 
enable the formation of only an enumerable array of finite formulae 
to serve as definitions for ordinals while mathematically the number 
or cardinality of the ordinals is unlimited. (And as was mentioned 
above, even the set of ordinals where each has only enumerably many 
predecessors, this set should itself be of higher cardinality and 
non-enumerable.)


                        An Hierarchy of Levels
 
    So we evolved the idea that the formal system serving to extend a 
given basic system (or "ground level") could be structured by making 
use of special functions enabling references to levels. In effect, 
if we used references indicating a higher level then it would become 
permissible to "overview" the formulae and procedures of a lower 
level.
     And the basic idea, at least at the beginning of the construction 
of an hierarchy of extension levels, is quite like Turing's concept
in that the first extension level, the first level above the ground 
level, incorporates the possibility to prove as a theorem the Goedel 
assertion for the logical system of the "ground level".
     The first higher level, corresponding in our approach to any 
acceptable definition of the first ordinal number, would be such that 
the Goedel assertion from the ground level would now become provable 
if that Goedel assertion had been simply added as an axiom usable on 
the higher level. Or instead it would be effective to introduce as an 
axiom an assertion of formal consistency of the ground level logic. 
This type of assertion can be seen to imply the assertion of Goedel's 
type. Formal consistency is the assertion to the effect that "on the 
ground level nothing false can be proved."
     The verbal argument for the truth of Goedel's formula depends 
in effect on an overview of the specific formal system in which 
it is stated and on the basis of the axioms, etc. of which it was 
constructed. Also this argument depends on the assumption that that 
formal system is actually perfectly consistent. Our idea of extension 
and of "hierarchical introspective logics" is that there is to be 
considered an hierarchy of levels of logic such that higher levels 
have an "overview" of the proceedings and results obtainable on lower 
levels. Thus the totality is "introspective" because it is looking 
inward to study itself but this self-study is not unrestricted. And 
effectively a higher level is supposed to be able to see the truth of 
a Goedel assertion deriving from a lower level by a process analogous 
to the verbal argument originally known for the truth of the Goedel 
assertion in a formal system although there is no proof of that 
assertion in that original formal system.
    A logical system cannot effectively state its own consistency; 
this relates to the incompleteness originally found by Goedel. But 
one logical system CAN easily state the formal consistency of another 
system. We use this idea in creating our hierarchy of levels so that 
on a higher level it is possible to, in effect, assume the validity 
and the consistency of proceedings possible on lower levels.


                   Axioms and Special Functions

   (This portion of the talk should make use of transparencies 
presenting the axioms or axiom schemata and the special functions 
introduced.)
    Our design for the extension hierarchy has the feature that 
certain special logical functions are introduced as components of 
formulae on all levels of the hierarchy except the ground level, 
the ground level being simply the formal logic that we are extending. 
The initial or ground level system should be adequate to be of the 
sort studied by Goedel and to be able to deal with "number theory",  
"functional calculus", and "set theory". And we prefer the viewpoint 
of Zermelo, that sets can be based on ur-elements which are not 
themselves sets. Also we like to think of ordinal numbers as being 
basically a special type of mathematical objects such that they 
satisfy appropriate axiomatic properties. Thus the ordinals, as 
mathematical entities, are analogous to the quaternions. Of course 
this doesn't really matter, it's a question of taste.
     We assume, for convenience, that a specific "canonical" 
"Goedel numbering" has been chosen, both for formulae (wff's) and 
for "strings" of formulae that are presented as proofs. This is with 
regard to the extended system, not just the "ground level". Then 
each wff or string of wff's has its index which is simply one of the 
natural integers. And the special functions that we introduce are 
to be understood to use these index integers as arguments. We favor 
the convention that the formula or string that is indexed may be 
substituted for the indexing integer in an instance of any of these 
special functions.
     
   (Give oral verbal description with display of transparencies for 
axioms and special functions. Explain that ORDDEF( "delta" ) is to 
be affirmed or true ONLY when "delta" is a definition in a standard 
form using only notation/symbols appropriate for the ground level. 
And explain also that such a definition, to be approved, must be 
recognizable as PROVABLY the def. of an unique ordinal by the logic 
of the GROUND LEVEL. And remark that the function ORDDEF(~~) is NOT 
recursive but is definable from a set of recursive functions relating 
to provability and form.)

    Regarding axioms, we are not sure that we have the final set of 
main axioms and also we see some overlapping or redundancy of axioms 
dealing with the KT(~~,~~) or "known true" function. It is also a 
technical need that certain axioms should be present that simply 
assert that the special functions are what they are supposed to be. 

    
               Inductive and General Incompleteness 

    The incompleteness found and exhibited in the paper of Paris and
Harrington has a relation to proofs by induction and the possibility 
of achieving desired results by that means given favorable "axioms of 
infinity". Parallelwise, for our system of extension, which builds 
upon a given initial system or ground level, the extension process 
naturally ends as the range of definable ordinals becomes exhausted.
    So an extension system of our type is incomplete, which is fitting 
in relation to general undecidability results, but the extension 
process can be easily revived and renewed provided that new "axiomatic 
ordinals" are introduced. That is, it is always possible to add an 
axiom or axioms specifically directed to the theme of the existence 
of ordinal numbers so that it becomes possible to define a "new" 
ordinal level, with the validity of the "orddef" associated with this 
level dependent on the new axiom or axioms, and such that the new 
definable ordinal is larger than all of those that were previously 
usable. And then the extension process is renewed and in the 
re-extended system the proof of formal consistency of the system 
as it was before becomes possible because the former range of the 
system is all subject to overview from the perspective of levels 
depending on the new axiom or axioms.
    The interesting possibility is that it now becomes plausible or 
conceivable that the incompleteness phenomenon will not cause us to 
need to add anything like the Riemann Hypothesis or the Goldbach 
Conjecture as an axiom (because of the impossibility of otherwise 
establishing their truth) but rather that appropriate set theoretic 
axioms relevant to the existence of ordinal numbers may be added as 
needed.


                         Cultural Evolution

    If it had been possible to achieve logical completeness with a 
system like Principia Mathematica then all of mathematical research
to the extent of its not depending on tasteful definitions and
inspired inventions of topics, and thus perhaps all "number theory",
in the sense of the study of questions of classical elementary form, 
could be worked out straightforwardly by a robot operating in an
isolation chamber simply on the basis of the rules.
    But the history of human progress in science and mathematics
reveals that observation of the phenomena of Nature has always
played a large ro^le. Mathematics itself can be viewed as having
evolved from the "language of precise quantitative communication" 
and many precise logical concepts have become included with the 
quantitative concepts. The Sumerian scribes wrote down records for 
the quantities of grain received or sent from their central granaries.
    So mathematical logic itself looks like a language that is
naturally capable of evolution like also mathematics as a language 
and as an encyclopedia. But we feel that a "translatability" property
should hold true here. Thus, for example, a relatively modern proof
in geometry by Pascal should be translatable into a form, written in
Greek, that Euclid would have found acceptable. Or the proof of the
FLT by Wiles should be translatable into a version in French or Latin
such that, with its introductory material developing the theory of
elliptic curves and modular functions, it could have been studied and
accepted by Fermat, if he could devote enough time to the effort.
    In this context of the theme of cultural evolution, as applied
specifically to mathematical logic, it seems possible that a system of
logic of the future could be translated into a form corresponding to a
system of the present time with the addition of a few axioms that give
what is needed to give the potentialities of the future system. Our
concept of an "hierarchical introspective logic" suggests that for
"number theory" at least that there might be no need to adopt any new
axioms other than essentially axioms of infinity that make it possible
to assert the existence of ordinals that otherwise could not be 
thought of as definitely existing.
     Already we have in set theory a variety of popular potential  
axioms. It is not yet generally assumed, but the "Axiom of Choice" 
is an extremely popular option in set theory. And if the adoption 
of conceivable or popular axioms went further then the GCH or 
"Generalized Continuum Hypothesis" could be adopted.
     It seems plausible or at least conceivable that knowledge 
actually gained from the study of Nature, plus cultural evolution, 
would in time lead to decisions, positive or negative, about the 
adoption of axioms relating to set theory that seem to us now as 
quite optional in merits.