**Mail folder:**Interlingua Mail**Next message:**Matthew L. Ginsberg: "Re: kif"**Previous message:**Giuseppe Attardi: "Re: FOL vs HOL vs MML"**Maybe in reply to:**David McAllester: "KIF"**Reply:**Matthew L. Ginsberg: "Re: kif"**Reply:**Giuseppe Attardi: "Re: kif"

Message-id: <9312152011.AA25350@Sunburn.Stanford.EDU> Date: Wed, 15 Dec 1993 12:10:31 -0800 To: interlingua@ISI.EDU From: genesereth@cs.Stanford.EDU (Michael R. Genesereth) X-Sender: mrg@sunburn.stanford.edu (Unverified) Subject: kif Cc: perlis@cs.umd.edu

Folks, Well, there has been some lively discussion on this mailing list of late; and I have read the exchange with considerable interest. I think that most of the key points have already been raised; but, in my role as editor of the KIF document, I wanted to emphasize a few of these points. (1) First of all, an historical note on the issue of first-order vs higher-order logics. Rich Fikes and I brought this issue before the interlingua committee in its meeting of July 1992. In that meeting we outlined the relative advantages and disadvantages of first-order and higher-order semantics and asked the committee for a decision. The principal benefit for higher order semantics was seen to be the power to represent complex concepts (like transitive closure and circumscription) that could not be represented in first-order without the danger of non-standard models. The disadvantages were seen as (1) a loss of compactness and completeness and (2) the necessary introduction of typed variables and all of the difficulties and confusion they engender in practical settings. Into this argument was injected the point that, while nonstandard models of things like transitive closure are a problem for knowledge REPRESENTATION, they are irrelevant to knowledge INTERCHANGE. The same conclusions can be drawn whichever semantics one chooses! Pat Hayes recently made this point in his responses to Fritz Lehman. Given this point and the disadvantages of higher order semantics, the committee voted to adopt a first-order semantics until and unless someone could discover a significant problem with this approach to knowledge interchange. I think we need to look carefully at Fritz Lehman's examples to determine whether any are sufficient examples to warrant a change to this decision. I, for one, plan to study these examples over the next few weeks and either produce renditions in KIF -or- suggest needed modifications to the semantics. But, so far as I can see after a brief look, none appear to warrant such a change, so long as we continue to concentrate on knowledge interchange. (2) As to the issue of apparent higher order constructs in a language with first-order semantics, I would like to refer you to the literature of mathematical logic. For those of you unfamiliar with how one can give a first order semantics to a language with second order syntax, you should look at the treatment of second order languages in Herb Enderton's book entitled ``A Mathematical Introduction to Logic''. In this particularly lucid account, Enderton distinguishes between general semantics and absolute semantics, the key difference being whether the relational quantifiers range over all relations on a universe of discourse or whether the quantifiers range over those relations in a particular set of relations. In the latter case, it can be shown that the semantics is effectively first-order, i.e. the logic remains compact and semidecidable. (3) The problem of set paradoxes is discussed in the KIF speification itself, at least briefly. The treatment follows that of vonNeumann Godel and Bernays, who show that there is a model for the basic axiom schemata given in the spec. Given that there is a model for any set of sentences, there can be no paradoxes (which, you will recall, are effectively self-contradictory sentences). If anyone is interested, I can also give the rationale for why we chose the slightly more complicated vonNeumann set theory over the apparently simpler Zermelo Frankel set theory. Hint: think about how you would define the lambda and kappa operators in ZF. (4) The problem of metalevel paradoxes is also mentioned in the specification, though in this case the discussion is even briefer. There are numerous ways to eliminate the metalevel paradoxes popularized by Montague. Kripke (Journal of Philosophy 1975) gives an axiomatic approach based on Kleene's strong three-valued logic. Feferman (Journal of Symbolic Logic 1984) provides a simpler axiomatization. Feferman's version is essentially equivalent to the one described by Perlis (AIJ 1986). Perlis's version is the one used in KIF. Perlis's article on self-reference proves that the axiom schema true(p)<=>p* is consistent with any theory not containing any occurrences of the true predicate. In other words, the semantics is not paradoxical, though one can write sentences that turn out to be false. The committee also considered a few weaker axiomatizations, which are not included in the current specification. These can still be incorporated in future editions by naming additional true-like predicates, each with different axiom schemata. Those interested in these isues should look at the book ``Truth and Modality for Knowledge Representation'' by Ray Turner (MIT Press), especially his proof of the equivalence of the KIF axiomatization to a variation of that described by Kleene. To summarize, we can be pretty well assured that the basic APPROACH taken in KIF is safe from paradox. The semantic basis for KIF has been documented, reviewed, and published in the mathematical and ai literature for years. We have not innovated here in any semantic way; we have just standardized notation. However, (1) we must continue to study the spec to be sure that no silly mistakes were made. Moreover, (2) we must continue to study some of our decisions to determine that these are the things we WANT in a language for knowledge interchange. (And, in so doing, we must be careful not to confuse knowledge interchange with knowledge representation. The criteria are different.) In conclusion, I would like to point out that the members of the Interlingua committee have done a lot of work on this spec, as have the outside reviewers. And more work is being done all of the time -- to refine the language, to document it, and to use it. This is no slapdash effort. I am personally gratified to see so much discussion on the mailing list. However, I would like to encourage us to concentrate on constructive criticism. The best questions are those based on uses of the language, accompanied by specific examples (like Lehman's list). The best kinds of criticisms are those that are based on proven difficulties, together with specific alternatives in the spirit of the language (like Gruber's criticisms eraly on in the effort and Sowa's more recent recommendations for extended quantifiers). I think we would all also welcome comparative studies (e.g. between kif's semantics and that of attardi and simi). The point of publishing the spec was to elicit just such discussion. If we work together constructively, I think we can produce a language that we can live with and that will serve the industry well as it begins to begins to support greater degrees of knowledge interchange. mrg PS: Unfortunately, I will be away from my email for the next two weeks. So, if you respond to this note, please do not be dismayed if you do not hear from me for a while. I will respond when I get back in the new year.