what is the "all" in KIF's forall ?

Tom Gruber <Gruber@HPP.Stanford.EDU>
Full-Name: Tom Gruber
Message-id: <2964235057-2656021@KSL-Mac-69>
Date: Mon, 6 Dec 93  22:37:37 PST
From: Tom Gruber <Gruber@HPP.Stanford.EDU>
To: interlingua@ISI.EDU
References: <01H61EPH75PE92000I@delphi.com>, 
Subject: what is the "all" in KIF's forall ?
[EXECUTIVE SUMMARY: Yes, you can quantify over relations in KIF, any
relations you want.  It's all there in the spec.  I'll explain why
I think "it's that simple".]

The point of an knowledge interchange format is to interchange
knowledge among people and their programs.  The meaning of knowledge
in the programs of today, and for the foreseeable future, is
ATTRIBUTED by humans who build and use them.  We say what it means; It
doesn't.  Whether this is inescapable, as the social constructivists
would have it, or just the state of our craft, isn't relevant to the
knowledge interchange business.  (In his Knowledge Level paper, Newell
blurs the distinction by casting this philosophical point of view in
purely engineering terms.)

The bottom line is, in every KB or knowledge exchange among agents
there will be some CONVENTION about the conceptualization that is
specified by and for humans.  Convention appears in three places:

  [1] the syntax of the encoding language and how syntactic operations
produce semantic results
  [2] a description of the universe of discourse and
  [3] definitions of the words in the shared vocabulary

The KIF spec and the social process underlying it (of which this
message is a part) is an attempt to establish a convention of type
[1].  Throughout the manual, greek letters and other such notational
conventions dress up the fact that we need to agree on some basics
like conjunction and denotation.  And we do, without complaint.  How
about the Tarskian semantics -- anybody out there think that this is
going to be a show stopper for exchanging knowledge among programs and
people?  The big jump being taken with the whole KIF/ontologies
approach is the basic commitment to declarativism, which opens up
world of things we can know about but can't tractibly compute about.
By adopting the declarativist strategy, we have the luxury (and
burden) of being clear about what we mean.

Consider the semantics of quantification, carefully specified in the
KIF manual.  To put it a bit simply, it says that when you see a
sentence of the form
   (forall ?x (p ?x)) 
then the sentence (p ?x) is true for every assignment of ?x to some
element in the domain of discourse.  The spec actually goes into some
detail on exactly what this means, using a notion of interpretation
and logical entailment [see chapter 4, Semantics].

Ontologies are an attempt to specify [3].  Within an ontology, there
are primitive words and other words that are completely (and
axiomatically) defined in terms of the primitives.  We can impose some
formal constraints on the primitives, but their "complete meaning"
will always be communicated by some other convention (e.g.  social
agreement of the sort achieved by collaborating engineers).  That's
life.  Good theorists of every stripe try to reduce the number of
primitives in their theories, but never expect to dispense Meaning
>From a purely formal construction.

But what about [2]?  Is the specification of a universe of discourse
different?  I claim it's something we just agree on.  So let's.  

Genesereth has already done a good job at describing the issue.  In
Chapter 3, he describes a model of the business of knowledge
representation and how it relates to knowledge sharing.  Different
users will have different universes of discourse.  However, they
overlap.  In particular, all users of KIF agree that [their shared]
universe of discourse has the following things in it:
  o the words used in the KIF sentences
  o a complex numbers
  o all sequences and sets of anything else that is in the universe of discourse
  o the object called BOTTOM, for denoting the value of
     functions when they are undefined

Did you see relations in there?  Well, you have to know about another
commitment in KIF -- a very fundamental one.  In Chapter 8 [an
ontology of relations], the KIF spec says quite clearly that relations
are sets of objects in the universe of discourse, and therefore the
relations themselves are in the universe of discourse.  Functions are
a special case of relations.  It doesn't say that relations are the
predicates that are named in some knowledge base or description
lattice [although you can define such a notion using the indexical
constant KNOWLEDGE-BASE or the metalinguistic relation ANALYTIC-TRUTH,
both of which in are KIF].  If a relation is defined over objects in
the universe of discourse, then that relation is in the universe of
discourse.  How big is the set of relations?  Well, one of them is +,
which is the set of all tuples of arbitrary finite length whose last
item is the sum of its first items.  That's a lot of tuples.  Enough,
I'd imagine, to satisfy Carl Sagan.

So let's get back to the business of making useful conventions about
things we want our programs to talk about.


P.S.  Attached are the relevant excerpts from the KIF 3.0 spec.  The
LaTeX source and postscript for this document, and others about
knowledge sharing, are available by anonymous ftp at
  ksl.stanford.edu: /pub/knowledge-sharing/papers/
On the WWW, dial


The formalization of knowledge in KIF, as in any declarative representation,
requires a {\it conceptualization} of the world in terms of objects,
functions, and relations.


A {\it universe of discourse} is the set of all objects presumed or
hypothesized to exist in the world.  The notion of {\it object} used here is
quite broad.  Objects can be concrete (e.g. a specific carbon atom, Confucius,
the Sun) or abstract (e.g. the number 2, the set of all integers, the concept
of justice).  Objects can be primitive or composite (e.g. a circuit that
consists of many subcircuits).  Objects can even be fictional (e.g. a unicorn,
Sherlock Holmes).

Different users of a declarative representation language, like KIF, are likely
to have different universes of discourse.  KIF is {\it conceptually
promiscuous} in that it does {\it not} require every user to share the same
universe of discourse.  On the other hand, KIF is {\it conceptually grounded}
in that every  universe of discourse {\it is} required to include certain {\it
basic} objects.  

The following basic objects must occur in every universe of discourse.


\item{$\bullet$} Words.  Yes, the words of KIF are themselves objects in the universe
of discourse, along with the things they denote.


\item{$\bullet$} All complex numbers.


\item{$\bullet$} All finite lists of objects in the universe of discourse.


\item{$\bullet$} All sets of objects in the universe of discourse.


\item{$\bullet$} $\bot$ (pronounced ``bottom'') -- a distinguished object that
occurs as the value of various functions when applied to arguments for which
the functions make no sense.


Remember, however, that to these basic elements, the user can
add whatever {\it non-basic} objects seem useful.

\section{Functions and Relations}

A function is one kind of interrelationship among objects.  For every finite
sequence of objects (called the {\it arguments}), a {\it function} associates a
unique object (called the {\it value}).  More formally, a function is defined as
a set of finite lists of objects, one for each combination of possible
arguments.  In each list, the initial elements are the arguments, and the final
element is the value.  For example, the $1+$ function contains the list
$\langle 2,3\rangle$, indicating that integer successor of $2$ is $3$.

A  relation is another kind of interrelationship among objects in the universe
of discourse.  More formally, a {\it relation} is an arbitrary set of finite
lists of objects (of possibly varying lengths).  Each list is a selection of
objects that jointly satisfy the relation.  For example, the $<$ relation on
numbers contains the list $\langle 2,3\rangle$, indicating that $2$ is
less than $3$.


\chapter{8}{Functions and Relations}

In KIF, we can describe specific functions and relations by naming
them with function constants and relation constants and then writing
sentences in which those names occur in functional or relational
position.  For most purposes, this is adequate; but in some cases it
is also useful to describe functions and relations more generally --
to name their properties (such as associativity and transitivity) and
to write axioms relating these properties (possibly quantifying over
the functions and relations possessing these properties).  In order to
do this, we need to treat functions and relations as objects in our
universe of discourse.  

By definition, functions and relations are sets of lists of objects
>From our universe of discourse.