Re: Higher-order KIF & Conceptual Graphs
Message-id: <>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Fri, 21 Jan 1994 21:17:27 +0000
To: interlingua@ISI.EDU
Subject: Re: Higher-order KIF & Conceptual Graphs
Cc: (Fritz Lehmann),,
At  5:04 AM 1/21/94 -0600, Fritz Lehmann wrote:
>     The "logical foundations" KIF committee which Pat Hayes is
>to head should have some balance, if it is to properly address
>the issue of whether to use real, classical higher-order semantics,
>or just a schema-based First-Order imitation for the sake of
>completeness and compactness.  Pat himself, although he first
>raised the higher-order question some months ago, seems to have
>come very firmly down on the side of First-Orderism (partly based
>on his demand for completeness for full "logical grounding").  If
>the rest of the committee consists only of other KIF-ites who
>originally voted for First-Orderism in the first place, the
>imprimatur of the committee will mean little.  (Echoes of Matt

Well, lets keep this discussion rational. Matt made very strong accusations
basically of incompetence, and his criticism was aimed directly at the
issue of finding ANY semantics for KIF which supported the self-reference
machinery described in the KIF document, a notoriously tricky area
requiring special care to avoid inconsistency. And Matt found some genuine
errors in the document at this very place. So we need to check the
foundations here. 

But the issue of classical vs. Henkin interpretations of higher-order
quantification is much more a matter of design choice. Both semantic styles
are well-understood and both admit coherent design stances. Fritz' tastes
are made clear by his choice of vocabulary, but this particular design
issue is not one which I expect we will consider in any depth. The task we
have taken on is to define a semantics for KIF which properly supports the
inferential machinery described in the KIF Manual. It is not to address
every semantic issue which might arise, nor to make final conclusions on
these issues, and still less to draw any such conclusions on a democratic
basis. I have no particular first/higher order axe to grind, in fact, but
will be happy to see any coherent model theory at all. I think it very
likely that if we can construct a coherent first-order semantics then a
classical higher-order one can afterwards pretty easily be constructed from
it, and vice versa.

>Specifically, there should be some people with actual
>higher-order logic (and model theory) expertise, or the committee
>might be as uninformed on this issue as is customary. Someone
>should actually understand the work of Fraisse, Ehrenfeucht,
>Shelah et al.  

I have been seeking people who have the necessary competence and interests
and are willing to cooperate. Some have been hard to locate by email: in
particular, does anyone know how to contact Ray Turner at the University of


>P.P.S. Must we totally neglect intension?  Sinn?  Two facts
>are: A. There are too many different discordant notions of
>what "intensions" are and many are hard to formalize neatly,
>whereas everybody pretty much understands extensions as a formalism.
>B. Notwithstanding fact A., intensions really matter more than
>extensions.  Triangularity is the thing to know about, not the set of
>triangles.  Same goes for Democracy, puffinhood and FAX machines.

Well, yes, is needed in discussions like this. For a start, it
is notoriously difficult to say what intensions ARE: so difficult, in fact,
that one begins to be suspicious that maybe the primal intuition is rather
faulty. I hove now reached the stage where I really have no idea what
'triangularity' means, and suspect it means many different things in
different philosopher's mouths. Secondly, even if we agree that an account
of intensions is needed, history seems to strongly indicate that little
progress is made until we develop what might be called an extensional
approach to them. Thus for example modal semantics was a very confused
business until Kripke developed an EXtensional account of the semantics of
these INtensional languages. So while agreeing that Sinn should be our
subjectmatter, I would be very, very reluctant to step outside set language
as our conceptual apparatus for describing model-theoretic structures.

>Who really cares about arbitrary extensional sets of objects?

I do! The set-theoretic account of an interpretation indeed maps terms to
arbitrary sets. But rather than a criticism of the theory, this is a
strength. These formal languages in fact DONT have their meaning fixed:
they COULD mean any one of these set-theoretically proscribed
possibilities. The arbitrariness of these modeltheoretic constructions in
fact precisely exhibits the expressive weakness of the formalisms, the
extent to which they can consistently be reinterpreted without affecting
their deductive behavior, hence, the extent to which this deductive power
fails to capture intended meanings. See why the completeness results are so
central? I want to be able to use these formalisms to capture meanings, and
I want a semantic theory to give me an honest account of the range of
things that my representational expressions might mean. If this fails to
fit with what I, the user, had in mind, I want the semantic theory to
report this to me so that I can expand or change my representation, not be
obliged to redefine its semantics so that I can pretend it meant what I
hoped it would mean.

Ahem. Sorry about that, Fritz has that effect on me. Now let me step down
>From my pulpit, put my chairmans hat back on and agree that a working model
theory for a KILanguage should allow for the possibility of declaring a
priori that, say, numerals will denote the integers, and following through
the model-theoretic consequences of such interpretive assumptions. So to
reassure Fritz, I anticipate that we should be able to give particular
interpretations to some nonlogical symbols, especially some computational

>Extensional logic is neat and easy, but it's just a constraint on
>the logic that matters. 

Yes and no. If 'extensional logic' means the logic of extensional language,
I agree. But if it means a logic whose semantics are defined extensionally
(ie using an explicit set-theoretic - which is no more than another way of
saying mathematically precise - metalanguage), then I'm afraid I will
reserve approval until you explain what foundations you propose to rest the
theory on.

> Pegasus is not a golden mountain,
>for one thing, even if their empty extensions are the same.
>This is a big issue for Knowledge Representation, or should be.

I agree. We need to give a better account of meaningless terms than their
having no denotation. There are lots of ideas about how to do this, and
they all, I believe, can be expanded into ontological ideas (such as
possible worlds) which are expressible in extensional set-theoretic terms.
Even Situation Theory rests on a set theory, albeit I confess a rather
radical one.

Pat Hayes

Beckman Institute                                    (217)244 1616 office
405 North Mathews Avenue        	   (217)328 3947 or (415)855 9043 home
Urbana, IL. 61801                                    (217)244 8371 fax  or