Fermat's Library | Hierarchical Introspective Logics annotated/explained version.

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.

Comments

Products

Project