Higher-order KIF & Conceptual Graphs

fritz@rodin.wustl.edu (Fritz Lehmann)
Reply-To: cg@cs.umn.edu
Date: Fri, 5 Nov 93 03:35:37 CST
From: fritz@rodin.wustl.edu (Fritz Lehmann)
Message-id: <9311050935.AA03585@rodin.wustl.edu>
To: phayes@cs.uiuc.edu
Subject: Higher-order KIF & Conceptual Graphs
Cc: boley@dfki.uni-kl.de, cg@cs.umn.edu, interlingua@isi.edu

Dear Pat Hayes,                      phayes@cs.uiuc.edu

	Yes, I agree that we have been talking past each
other a bit, because I've said three or four times that A.
we need higher-order and mixed-order constructs for
practical reasons, B. if the mathematical logicians want
to call these mere "syntactic sugar" via some kludgy
reduction to FOL based on an equivalent countable number
of first order sentences on some arbitrary finite
vocabulary, that's fine with me, and C. if we need real
higher-order model-theoretic semantics (with a domain
closed under disjoint unions of direct products) as I
suspect, that's fine with me too.  So, there may be no
dispute between you and me.  Just make sure the language
has the constructs and handles them right in all cases
likely to be encountered in real life.

	KIF and Conceptual Graphs now make no provision for
higher-order concepts with any semantics at all.  Gruber's
Ontolingua makes a stab at it, as do Boley's DRLHs.  We
need relations among relations, relations between
relations and their own arguments, functions of functions,
and so on, not just relations among individuals.  (For
some purposes one might conceivably want relations defined
on connectives, as in the works of Zellweger, Menger or
Stern.)  I think I've cited examples of about five or six
kinds of higher-order things that users might want to say
for practical applications, which are simply impossible to
say in current (First-Order) KIF or CGs.  (If anybody out
there is sympathetic, please email to these lists a few
more examples of higher-order or mixed-order statements. 
If unsympathetic, send counterexamples showing how my
prior examples would appear in FO KIF or CGs.)

	Somebody earlier (I forget who) said KIF is like a
standard being developed without any user input.  That
seems right.  I don't think the potential users will give
a hoot about transfinite numbers, incompleteness,
nonstandard arithmetic, etc., nor should they.  We need to
trade taxonomies, exchange industrial PDES/STEP
descriptions, describe business enterprises, classify
scientific documents, etc.  -- as I said before, probably
no-one will need numbers any higher than Graham's Number
(a finite biggie from Ramsey Theory), let alone the
transfinite.  But users will indeed be bothered if they
can't say what they need to say.

	[Digressive Note: Your messages keep raising too many
interesting issues.  Such as the distinction between the
semantic reality of AND and uninterpreted VERY-BIG. 
"Semantic theft from the syntax" is a pet peeve of mine:
definitons of AND tend to steal its meaning (directly or
via intersection or truth tables) from a semantic feature
of our syntax.  Similarly, post-Princ.Math. purported
definitions of 42 steal the essential 42-ness from the
semantics of our _42_ syntactic meta-applications of
successor (or pure-set parentheses or the equivalent). 
But we can't explore such topics in this KIF/CG
discussion.  (I'll mercifully skip my "Non-Existence of
the Self" thesis.)  Your expounding to me on the hugeness
of uncountable numbers assumes that I'm recommending
higher-order KIF/CGs due to an expressed concern of mine
for consequences in uncountable domains.  Absolutely not. 
I don't even believe in them.  I said earlier that "I balk
at diagonalization and its progeny"; uncountables are
among the progeny.  You said you balk too.  But I mean it
-- someday I'll either A. Accept Cantor's Theorem, B.
Refute it, or C. Die without having done A or B.  B is the
outcome I prefer.  Until then, like other skeptics (many
of whom later became converts), I regard the diagonal
argument as a specious tissue of arrant nonsense and I
heartily endorse Sowa's phrase "uncountable garbage".  If
X is countably infinite then I'm currently happy with: X =
2+X = 2*X = 2^X = 2(^X)Xtimes, etc. so I'm Aleph-free and
excluded from Hilbert's "paradise".  As the support-group-
aholics like to say, "joyous, happy and free".  Mainstream
Cantor-following math types would say "benighted
ignoramus".  I don't necessarily expect others to share my
view -- at least not until event B.  Meanwhile there's no
point in you demonizing uncountability for me, since I
(privately) won't even acknowledge that closure under
classes and direct products makes a domain "uncountable"
in the first place.  (I might believe vaguely, like
Peirce, in a "real infinity" beyond all alephs which is
1/0.)  But back to KIF and CGs.]

	The potential success and dominance of an un-
expressive knowledge sharing standard could have bad
consequences.  In AI, scruffies typically innovate and
then later on the neats clean up the messes.  This was
true in semantic networks.  I want KIF/CGs to be logically
sound, but not to _stifle_ the future innovators.  (If you
want a field dominated by formalizing, take nonmonotonic
logics -- please!)  I fear that pure First-Order-ism will
be stifling.  Remember -- when I asked KIF author Mike
Genesereth about the relation between a relation and one
of its own arguments, he informed me that "there is no
such relation".  Is that the kind of (FO-inspired) answer
which knowledge standards will offer would-be users?

	You say:
>[R]eal systems will often be incomplete
>for all sorts of practical reasons.... traceable
>to, as it were, failures to search all of the space. But inmcompleteness of
>the underlying representation language is a gap in the search space itself,
>which is a more serious matter.

	Incompleteness in the space is practically serious
only if the locus of incompleteness has some likelihood of
actually being reached in practice.  Think of a very long
strip of linoleum; it's complete and intact for the first
zillion miles from one end, but at that distance small
cracks begin to appear.  It is still a usable,
"practically complete" piece if our activities take us at
most a few yards along it from the good end.  That is an
adequate standard for practical knowledge interchange, if
the alternative is crippling un-expressiveness.  First-
Order-ism gives us a truly crack-free infinite strip of
linoleum, but only an inch wide and patterned with big
holes.  We're better off with the wide, locally solid
piece, distant cracks and all.

>I was interested that when challenged to go above third order you
>cited category theory. Yes, I can believe that category theory
>might find some of the more rarified heights useful.

	Good.  I hope category theorists will not be denied the ability
to communicate in a knowledge interchange language due to its being
merely First-Order.  One reason catgory theory is a promising
addition to Krep is because it has an inherent "action-oriented"
pragmatism: the theory doesn't care what something is, only what it

>I would be very
>interested to find out more about Ontek's use [of 3rd and
>4th order logic]; is it in any way related to Montague?

	I don't know.  I think there might be a few Montagovians around
U.C.Irvine with whom Ontek has connections.  Since Ontek people get
these email lists, they can answer this.

>You ask for 'REAL EXAMPLES' of the trouble caused
>by incompleteness. But that misses the point.

	If you are creating a limiting standard for other
people to use which requires them to make some sacrifice,
it never misses the point to ask you for some practical
examples which would justify their sacrifice.

                        Yours truly, Fritz Lehmann
4282 Sandburg, Irvine, CA 92715 USA    714-733-0566