- From: Peter F. Patel-Schneider <pfps@research.bell-labs.com>
- Date: Mon, 01 Apr 2002 13:17:39 -0500
- To: timbl@w3.org
- Cc: www-archive@w3.org

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