Higher-order KIF & CGs

fritz@rodin.wustl.edu (Fritz Lehmann)
Reply-To: cg@cs.umn.edu
Date: Wed, 29 Sep 93 05:56:25 CDT
From: fritz@rodin.wustl.edu (Fritz Lehmann)
Message-id: <9309291056.AA25086@rodin.wustl.edu>
To: cg@cs.umn.edu, interlingua@isi.edu
Subject: Higher-order KIF & CGs

	Jim Fulton, replying to MacGregor's KIF critique, said:
>I am uncomfortable with this suggestion.  It seems equivalent 
>to saying that formal logic is incomplete without a single 
>ontology for its semantics.  

	The problem is that KIF is NOT based on "formal logic", 
but merely on the First Order part.  Formal logic includes 
higher-order logic, not just first-order, and Pat Hayes has 
mentioned this as a possible drawback of KIF and Conceptual 
Graphs. I agree.

	In knowledge rep. and natural language, higher-order 
logic is used freely.  It has been routine in philosophy for 
thousands of years.  KIF cannot now express that "Aristotle 
has all the virtues of a philosopher" (other than by using a 
semantically opaque "holds").  Patrick Winston's perennial 
block-arch diagram used a semantic net which included higher-
order relations-between-relations like "opposite of". IS-A 
itself is higher-order and so is relational IS-A.  Individual 
identity/equality can only be defined in higher order logic; 
the same is true (for those who accept Peano Arithmetic and 
Principia Mathematica) of natural numbers.  Also, we should be 
able to say that for some particular individual, all of a 
certain kind of functions on that individual take a certain 
kind of value (impossible in FOL).

	The usual objections to higher-order logic are that it is 
undecidable, uncompact, lacks the 0-1 property, etc.  These 
are extraneous theoretical matters of interest only in 
infinite, transfinite or infinitary domains.  They have no 
practical importance for transmission of descriptions of real-
world entities.  (To be crude, Turing-undecidability seems 
even theoretically irrelevant since no computer has the 
infinite storage to make it formally equivalent to a Turing 
machine. And why should "universal" KIF or CGs be unable to 
describe a simple paradox? I assume "the chicken has already 
flown the coop" on this issue for KIF since KIF users are now 
treated to the complication of Goedel-Bernays-Von Neumann Set 
Theory to avoid Russell's paradox etc., along with an odd 
theory of truth to disallow "this is false".)

	KIF and CGs should be strongly higher-order, i.e. not 
only have predicates of predicates and relations between and 
among relations, etc., but also quantification over any n-
order predicate or relation (typing n-order variables with a

not-perniciously-high "TOP" type is OK I suppose). They should 
also have "mixed-order" relations, such as the relation 
between a function and its own arguments.

	I asked Mike Genesereth at a lunch, "How could KIF handle 
the relation between a relation and one of its arguments?"  
Mike said: "There is no such relation."  Huh?  Mike, please 
explain simply why you believe this.  Even speaking purely

extensional-model-theoretically, it exists straightforwardly.  
Its model includes a subset of the Cartesian product R x D 
where R refers to a subset of D x D.  It just doesn't happen 
to be First Order.  In a semantic theory of "case relations" 
such a relation is likely to be characterized, compared with 
others and put in a taxonomy.  Several KL-ONEs have relation 
hierarchies.  They are implicit in the inclusion order in 
cylindric algebras.  In Conceptual Graphs these relations may 
be circles with AGT, INST, etc. and classified in a type 
hierarchy according to their qualities.  Model-theoretically, 
to my knowledge, there is no loss of rigor in extending the 
universe D to its closure under direct products as I 
recommend.  Perhaps someone can correct me if I'm mistaken.  
Harold Boley's DRLH (Directed Recursive Labelnode Hypergraphs) 
knowledge representation language already appears to do it 

	Mike said: Don't use relations for acts, define acts in 
advance as concepts (duly predicated individuals together with 
the appropriate binary roles).  It's no good to advise 
everybody to make such an act a concept first, rather than a 
relation.  Suppose we first characterize the act type by the 
tuples of its participants using KIF's relation-forming kappa-
abstraction, and THEN we later want to further 
characterize/analyse the meanings of its "columns".  I don't 
see how KIF allows this.  A hierarchy of relations may be so 
derived using Rudolf Wille's "concept-lattices".  And we may 
want to examine the two new mini-relations R1 and R2 which pop 
up as soon as we get any new dyadic R (i.e. those between R 
and _its_ arguments) and so on.  In Euclidian Between(a,b,c), 
a's relation to the betweenness has qualities lacked by b's 
and c's.

	As I pointed out in an earlier message on this point, Jim 
Fulton's SUMM (Semantic Unification Meta Model) already has 
this feature of being able to name, compare and characterize 
the participations (roles, argument-positions) in a relation.  
Having higher-order and mixed-order relations would 
accommodate SUMM and, I surmise, most of MacGregor's and other 
KL-ONEers' concerns.

	Sowa answered Hayes by suggesting semantically opaque 
(quoted) contexts.  This handles meta-meta-meta etc. but 
not true higher and mixed order logic.  Hayes has said this 
more than once without satisfactory reply.  Sowa says:
>We have several different hierarchies in KIF and CGs: the 
>hierarchy of types (or sorts, or colors, or flavors, ...); 
>the hierarchy of nested contexts; and the hierarchy of 
Very nice, but none of these is the hierarchy of logic orders.

There's no way of telling, in Sowa's reified-relation first-
order method, that an "x" in the world-model is a predicate or 
relation, as opposed to, say, a chair.  We get a world with an 
individual p in it and "P(x)" and either "[PREDICATE: p]" or 
"[TYPE:p]" but how do we know _semantically_ that p=P?  I'm 
all for reifying relations when needed (hypostatic 
abstraction, as Peirce said, is one of man's greatest 
faculties), but their relational character must not be lost 
when they join the world of individuals.

	Similarly, Tom Gruber later said of his frame ontology:
>The frame ontology, for example, is an
>extension of KIF's relations ontology that brings in the 
>notion of class (as a unary relation) and defines a family of 
>second-order relations such as those used in frame systems to 
>specify slot cardinality and type constraints. 
>. . .    One could define a
>second-order relation called TYPE, and assert (type Tx).

Again, how does this frame ontology, written in first-order 
KIF, accomplish second-order relations semantically?  How does 
calling Tx a TYPE cause the system to act upon it any 
differently from calling it a CHAIR?

	Later, Menzel:"...we lose completeness and most of those
other nice, friendly properties of first-order logic."
Hayes and Chris Menzel discussed the idea of using "Henkin 
semantics" in which every apparently second-order relation is 
really first order and has an associated first-order version 
of a "comprehension" sentence (EF)(x1)...(xn)(Fx1...xn iff A) 
attached to it..  Menzel said this 
>"is both appropriate and expressively adequate for certain 
>KRep needs, but which doesn't sacrifice the virtues of FOL."

	Why pussyfoot?  As mentioned, the "virtues" of FOL (like 
completeness, compactness, 0-1) are not relevant to practical 
transmission of real-world descriptions.  We need to transmit 
finite taxonomies and descriptions of real world things and 
laws and relations, in large but finite domains, ideally with 
the full (logical) expressiveness of very careful and precise 
natural language.  (Far from needing the transfinite, we might 
not even need the countable -- I rather doubt that any AI 
application will use any numbers higher than, say, Graham's 

	Maybe requiring formal decidability was already discussed 
and decided upon (for some reason) in this INTERLINGUA list 
before I joined.  Otherwise, designers of KIF (or Sowa), you 
should refute this persuasively or else cave in to higher-
order-ism.  It's not enough to say "I like my logic to have 
formal completeness" -- demonstrate the practical penalty of 
incompleteness (in real world AI communication among our 
finite computers) or what ever else ails you about n-order 

	It is the latter-day _restriction_ of most predicate 
logic to first-order that is artificial (due not just to 
decidability but partly, I suspect, to prejudices of young 
Quine), not any so-called "extension" to higher-order.  An AI 
system should not be prevented (by prematurely fossilized KIF 
or CG) from saying simple things like "North is the opposite 
of South," "The thief is to robbery what the beloved is to 
love," or "Bart has all the virtues of a philosopher," and 
meaning just what it says.

                                      Fritz Lehmann

(P.S. Jon Barwise told me that Montague in some fashion 
reduced higher orders to second-order.)

4282 Sandburg, Irvine, CA 92715 USA   714-733-0566