W3C home > Mailing lists > Public > www-webont-wg@w3.org > February 2002

Re: The Peter paradox isn't.

From: Peter F. Patel-Schneider <pfps@research.bell-labs.com>
Date: Tue, 19 Feb 2002 09:20:53 -0500
To: phayes@ai.uwf.edu
Cc: dieter@cs.vu.nl, www-webont-wg@w3.org
Message-Id: <20020219092053D.pfps@research.bell-labs.com>
Here is my reply to Pat's comments that the restriction I presented does
not indicate a paradox in the same-syntax extension layering of OWL on top
of RDF.




		The Same-Syntax Extension Paradox


Here is a more-detailed derivation of the paradox that I see when producing
same-syntax extensions of RDF.

There are two roads to a paradox.  One of these roads uses features that
are not in DAML+OIL, but exist in some DLs.  The other, longer, more
complicated road uses only features that are in DAML+OIL.

The basic methodology here is to extract the properties of a same-syntax
extension building on the new RDF model theory.  This is mostly done by
determining what entailments (or derivations, if you like) are needed and
seeing what constraints this places on OWL (or OWL+, a more-powerful
version of OWL) interpretations.  I've tried to stay as close to the
terminology in the new RDF model theory as possible.

The summary of all this is that if you want to be a same-syntax extension
of the RDF model theory and you have
a) rdf:type as a property;
b) defined classes, like DAML+OIL restrictions;
c) some sort of complement or negation; and
d) self reference
then you have a semantic paradox.  The first requirement, of course, is
satisfied by RDF itself.


1/ First, consider classes defined as intersections.

   If John is in both A and B, 
   then John is in the (an) intersection of A and B.

   <John, rdf:type, A>, <John, rdf:type, B> 
   |= <John, rdf:type, :_1>, <:_1, owl:intersectionOf, :_2 >,
      <:_2, owl:first, A>, <:_2, owl:rest, :_3>, 
      <:_3, owl:first, B>, <:_3, owl:rest, owl:nil>,

   This is only a valid entailment if all satisfying OWL interpretations of
   the first two statements contain an intersection class for A and B.

   This example motivates the inclusion of lots of things that must be in
   OWL interpretations.  In particular, if A and B are classes, then there
   must be a list whose members are A and B, in that order, and there must
   be a class that is the intersection of this list.  Note that I have not
   shown that there has to be a unique list consisting of A and B in that
   order, just that there must be at least one.  Nor have I shown that
   there has to be a unique class that is the intersection of this list,
   just that there must be at least one.

   Also, there are lists and classes that have to be in all OWL
   interpretations.  For example, in all OWL interpretations there must be
   at least one list whose sole member is the denotation of rdfs:Class and
   there must be a class that is the intersection of this list.


2/ Now, consider classes that are finite sets.

   rdfs:Class is always in the class consisting of rdfs:Class

   |= <rdfs:Class, rdf:type, :_1>, <:_1, owl:oneOf, :_2 >,
      <:_2, owl:first, rdfs:Class>, <:_2, owl:rest, owl:nil>

   This example motivates the existence of finite sets in OWL
   interpretations.  In particular, if i is an object, then there must a
   list whose sole member is i, and there must be a class that is the oneOf
   of this list.

   Some of these classes must be in all OWL interpretations.  For example,
   there must be a class in all OWL interpretations that is the oneOf of a
   list whose sole member is the denotation of rdfs:Class.


3/ Next consider DAML+OIL restrictions.

   If John has a child that is a Person, then John belongs to the
   Restriction that requires that its members have a child that is a
   Person.

   <John, child, Joe>, <Joe, rdf:type, Person>
   |= <John, rdf:type, :_1>, <:_1, rdf:type, owl:Restriction>,
      <:_1, owl:onProperty, child>, <:_1, owl:hasClass, Person>

   This is only a valid entailment if all satisfying OWL interpretations of
   the first two statements contain a restriction of the above form.

   This example motivates the inclusion of lots of restrictions in OWL
   interpretations.  In particular, if p is a property and c is a class,
   then there must be a restriction on p having class c.  Again I have not
   shown that there must be a unique restriction of this form, just that
   there has to be at least one.  So, in general if the objects mentioned
   in a restriction exist in an OWL interpretation then there must be such
   a restriction in the interpretation.

   As above, there are restrictions that have to be in all OWL
   interpretations.  In particular, in all OWL interpretations there must
   be a restriction on the denotation of rdf:type having class the
   denotation of rdfs:Class.


Now there are two roads that can be pursued.  The easier road is to go
outside of the expresssive power of DAML+OIL, allowing an identity property
and local relationships between properties.  I'll call this more-powerful
version of OWL OWL+.


4/ A restriction that consists of those objects where rdf:type is not a
   superproperty of the identity property can be constructed using the
   above features.  There is no syntax for this, but one way might be

   <:_1 rdf:type owl:Restriction>
   <:_1 owl+:onProperty owl+:identity>
   <:_1 owl+:notSuperProperty rdf:type>

   This is the Russel set, as an object belongs to this restriction if and
   only if it is not related to itself by the rdf:type property.  

   More fully, is this restriction related to itself by the rdf:type
   property?  Well if it is, then it is not an instance of itself because
   it violates the conditions in the restriction, and thus it is not
   related to itself by the rdf:type property.  However, if it isn't, then
   it is an instance of itself because it satisfies the conditions in the
   restriction, and thus it is related to itself by the rdf:type property.
   So rdf:type is ill-defined on this restriction and thus it has no
   satisfying OWL+ interpretations.

   However, this restriction only mentions objects that exist in all OWL+
   interpretations.  Therefore a restriction of this form exists in all
   OWL+ interpretations.  Therefore all OWL+ interpretations are
   ill-formed, so OWL+ has a semantic paradox.


The harder road stays within DAML+OIL, using circular or self references
instead of an identity property.


5/ First, a simple kind of self-reference.

   If John is in a restriction C whose p's all belong to C, 
   then John is in some restriction whose p's all belong to it.
   If Bill has no p's, then then Bill is in some restriction whose p's all
   belong to it. 

   <John, rdf:type, C>, <C, rdf:type, owl:Restriction>,
   <C, owl:onProperty, p>, <C, owl:toClass, C>
   |= <John, rdf:type, :_1>, <:_1, rdf:type, owl:Restriction>,
      <:_1, owl:onProperty, p>, <:_1, owl:toClass, :_1>

   This is a valid entailment, showing that restrictions can point back to
   themselves. 


6/ Now, a self-referential restriction that is entailed by statements that
   are not self referential.

   If John has no p's, then John is in some restriction whose p's all
   belong to it. 

   <John, rdf:type, :_1>, <:_1, rdf:type, owl:Restriction>,
   <:_1, owl:onProperty, p>, <:_1, owl:maxCardinality, "0">
   |= <John, rdf:type, :_2>, <:_2, rdf:type, owl:Restriction>,
      <:_2, owl:onProperty, p>, <:_2, owl:toClass, :_2>

   From the previous entailment, restrictions that point back to themselves
   are allowed.  Given that they are allowed, the above entailment is
   mandated, John is a member of any restriction whose c's all belong to it
   because he has no c's.

   Therefore, OWL interpretations must include self-referential
   restrictions.  In particular, is c is a property, then there must be a
   restriction that is all c's belong to itself.

   Again, restrictions of this form exist in all OWL interpretations.  In
   particular, all OWL interpretations must contain restrictions whose
   condition is that all rdf:type's belong to the restriction.


7/ Next, a more complex self-referential restriction.

   If John has no c's, then John is in some restriction that has no c's
   that are the restriction itself.

   <John, rdf:type, :_1>, <:_1, rdf:type, owl:Restriction>,
   <:_1, owl:onProperty, c>, <:_1, owl:maxCardinality, "0">
   |= <John, rdf:type, :_2>, <:_2, rdf:type, owl:Restriction>,
      <:_2, owl:onProperty, c>, <:_2, owl:maxCardinalityQ, "0">,
      <:_2, owl:hasClassQ, :_3>,
      <:_3, owl:oneOf, :_4>, <:_4, owl:first, :_2>, <:_4, owl:rest, owl:nil>

   This is just a combination of previous stuff.

   In particular, if c is a property then there must be a restriction that
   whose condition is that no c's belong to the oneOf of itself. 


From the above, a restriction like

   <:_2, rdf:type, owl:Restriction>,
   <:_2, owl:onProperty, rdf:type>, <:_2, owl:maxCardinalityQ, "0">,
   <:_2, owl:hasClassQ, :_3>,
   <:_3, owl:oneOf, :_4>, <:_4, owl:first, :_3>, <:_4, owl:rest, owl:nil>

must be in all OWL interpretations that have rdf:type as a property.  But
this is all OWL interpretations.

Now is this restriction related to itself by rdf:type?  If it is, then it
is not; but if it is not, then it is.  Thus any OWL interpretation
containing this restriction is ill-formed.  But this is all OWL
interpretations, so OWL has a semantic paradox.
Received on Tuesday, 19 February 2002 09:21:38 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:57:47 GMT