Re: Patel-Schneider Paradox ...

Hi:

I put together, and distributed to the WebOnt WG, a more-detailed document
that should answer many of your questions.   I have appended it to this
message, but will also respond to your message in-line.

peter


From: "Tim Berners-Lee" <timbl@w3.org>
Subject: Re: Patel-Schneider Paradox ...
Date: Fri, 29 Mar 2002 17:17:37 -0500

> Peter,
> 
> I feel that I have, though lack of time, not to mention
> background and ability, failed to get mind loaded with the
> thinking behind your paradox.
> 
> The most concise definition I could find with Google
> was in
> http://lists.w3.org/Archives/Public/www-webont-wg/2002Jan/0099.html
> and nearby.
> 
> With respect to the set of triples
> > _:1 rdf:type owl:Restriction .
> > _:1 owl:onProperty rdf:type .
> > _:1 owl:maxCardinalityQ "0" .
> > _:1 owl:hasClassQ _:2 .
> > _:2 owl:oneOf _:3 .
> > _:3 owl:first _:1 .
> > _:3 owl:rest owl:nil .
> > _:1 rdf:type _: 1 .
> 
> you say, "The question is whether the above collection of triples is
> entailed by an empty collection of triples."
> 
> How would that be entailed?  Certainly, the owl:first and owl:rest triples
> are
> axiomatically true.  However, looking at it naively, that set of triples
> is indeed inconsistent, but I don't see why they should have the status of
> a paradox. Why should be inference engine believe them and more
> than it believes anything else inconsistent?  Is there a set
> of rules for constructing classes which exist consistently from a vacuum?
> 
> In Russell's paradox, why must one consider the class of
> classes which are not members of themselves?  What forces
> one to fall prey to it?  I thought it was the assumption that
> for every thing and every class that thing had to be either a member
> or not a member, akin to the idea that all sentences are either true
> or false.  If you drop that requirement, then the paradox just sits
> there.

What makes the Russell set a paradox is its status as a ``built-in'' object
in the theory.  Yes, it produces a contradiction, but because it is
``built-in'', and thus exists in all states of affairs, every state of
affairs is contradictory, thus the paradox.

There are several ways around this.  One is to redefine set membership,
perhaps in a three-valued (or intuitionistic) fashion.  However, you have
to be very careful in this redefinition or else you will have other, more
complex, sets that have the same characteristics as the Russell set.  The
intuitionistic redefinition may eliminate the problem, but intuitionistic
logic has a very ``strong'' undefined, resulting in many sentences being
undefined where one might like them to be either true or false.

Another way around the problem is to weaken the theory of classes.
However, this results in a number of non-inferences that one would like to
make.   The document below takes a number of small steps all of which, I
claim, are desirable, ending up with the paradox.


> I realize I'm asking you a big favor to reiterate this, and that I would
> probably know why had I studied the lists more effectively.
> 
> Tim




		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 in 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 Monday, 1 April 2002 13:18:15 UTC