**Mail folder:**Interlingua Mail**Next message:**Fritz Lehmann: "Equality; higher order KIF/CGs"**Previous message:**sowa: "Re: Standardizing FOL"**Reply:**Fritz Lehmann: "Re: Higher-order KIF & CGs"

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 describe a simple paradox? I assume "the chicken has already 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 ============================================================