# 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
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
right.

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
>metalevels.
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
Number).

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
logic.

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
fritz@rodin.wustl.edu
============================================================

```