Re: Recursive Defs
Organization: Universitaet des Saarlandes
              D-6600 Saarbruecken FRG
Message-id: <>
To: Ramesh Patil <>
Subject: Re: Recursive Defs 
In-Reply-To: Your message of Fri, 27 Jul 90 14:35:38 -0700.
Date: Mon, 30 Jul 90 16:28:16 N

>After looking at Bernhard's definition of human, I am not sure
>that that example serves as a good example for testing fixed point

>There are a number of problems, first our understanding of
>human is a ``natural kind'' not a defined concept.  


>Second if
>every human being had two parents as defined, then we do not have
>the base case for induction, we need to posit that Adam and Eve
>are human and then one has a base case.

Despite the fact that without disjunction it is not possible to
express the base case, I would claim that for our
common-sense understanding it is not necessary to worry about whether there was
a first human or not. Everbody I know has 2 parents.

>Similarly, we cannot say that offsprings of human are human.  The definition
>only states that offsprings of TWO humans are human. 

I guess you are referring to KIT Report 58, Figure 7. In that case, we
have for all x,y: human(x) and offspring(x,y) => human(y), i.e. we
only need one parent to infer the humaness of the offspring. In turn,
it follows that y has two parents who are humans.

>Thus the counterintutive
>results derieved from least and greatest fixed point are really not
>counterintutive, given the definition.

Well, well, "counter-intuitive" is a very relative word -- namely,
relative to your intuition. One intuition could be that the definition
of a term specifies the "recognition conditions", i.e., an individual
belongs to the denotation of a concept if it satisfies all conditions
in the definition. Obviously this intuition is at odds with the idea
that a definition selects a unique denotation for a concept relative
to given denotations (see message to Dave). 

In any case, least fixed
points are counter-intuitive in a terminological logic where you
have only (and C D), (all R C), and (exists R) since concepts that use
(exists R) and are defined circularly over R have an empty denotation.

[Of course, once you have understood why the denotation is empty, it's
not any longer counter-intuitive, but it follows straightforwardly
>From the definition of the least fixed point. Nevertheless, it looks
unnatural and prohibits the use of such constructions which seems to
be useful sometimes.]

>It is also not surprising that
>defintion of human is no different from that of dog or cat or any other animal.
>TThis should be expected given the definition of human and given that there
>is no special meaning attached to the names of these definitions.

I agree! Funny enough, the descriptive semantics (which just the usual
first-order semantics) assigns a special meaning to the names.

>I think as dave Mcallester suggests, we need to give fixed point
>semantics more serious consideration.

I agree as well. There is one VERY BIG problem though: Least and
greatest fixpoints have the property to be very rare. If you add, for
instance, negation to the language I described above, LFP's and GFP's
do not exist any longer. There is a similar situation in logic
programming. If your program is really Horn (i.e. head and body
contain only positive literals), then its least Herbrand model is the
least fixpoint of a certain operator. If we allow for negation in the
body of a clause, usually there is no least Herbrand model or least
fixpoint and you have to use a lot of machinery in order to identify
other "interesting" models which are in some sense "least".

-- Bernhard