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

Still no paradox (was: Re: The Peter paradox isn't.)

From: Pat Hayes <phayes@ai.uwf.edu>
Date: Thu, 21 Feb 2002 20:23:32 -0600
Message-Id: <p0510140bb89af07e3aa9@[65.212.118.219]>
To: "Peter F. Patel-Schneider" <pfps@research.bell-labs.com>, Dieter Fensel <dieter@cs.vu.nl>
Cc: webont <www-webont-wg@w3.org>
>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.

With my replies interleaved. These are all negative (ie why Peter is 
wrong). I'll try to get something positive (ie how to do it) posted 
on a website before next week, but it will be a sketch only. Sorry, 
not enough hours in the day.

>
>
>
>		The Same-Syntax Extension Paradox
>
>
>Here is a more-detailed derivation of the paradox that I see when producing
>same-syntax extensions of RDF.

Maybe Im not fully grokking what you mean by a same-syntax extension, 
BTW. If so just point out where I go wrong. BUt the key point is that 
whatever you call it, there is a way to 'layer' OWL on top of RDF 
that allows the DPH to push OWL syntax through an RDF triples store 
so that it can be re-parsed successfully and also have a coherent 
semantics that (in a sufficiently reasonable sense) can be seen as an 
extension to RDF model theory.
What one cannot do is to just add a set of OWL-syntax operations to 
RDF and require that every well-formed RDF graph using them is also 
OWL-well-formed and has the same meaning in OWL that it has in RDF. 
If that is what you mean by same-syntax, then OK; but then so what, 
as that idea is dumb and nobody needs it in any case.

>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.

But keep in mind that 'building on' here can include the imposition 
of new constraints that are not expressible in the 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

BTW, we are agreed that this isn't really self REFERENCE, right? You 
are referring here to the freedom that RDF has to make 'loops' in its 
graph syntax, so that properties can apply to themselves, etc.. Lets 
call this the kyag property. A kyag graph is one that allows 
arbitrary knots, not just trees or dags.

>then you have a semantic paradox.

No, you don't, unless you assume that the definitions are more 
powerful than you have any business supposing. In order to get this 
kind of paradox you have to invoke the definitional power of full 
higher-order logic, or something like it. But we know we are well 
inside a first-order framework here, in fact something considerably 
smaller.

>  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.

OK

>    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.

I disagree. The OWL semantics can impose its own requirements on the 
RDF syntax. In particular, it can be written in such a way that all 
the owl:first /owl:rest list-construction does NOT assert that the 
list itself is in the OWL semantic domain; in effect, it can treat 
that as syntax, rather than as having OWL content inherited from RDF. 
(This does require that we allow an OWL interpretation of some RDF to 
only include part of the domain of an RDF interpretation of that same 
RDF graph, but I think that this is not an unreasonable assumption 
when discussing layering. )

Now, maybe you would say that this does not count as a 'same-syntax' 
extension (the term is yours, so you are free to define it as you 
please, of course.)  But in that case, there are other possibilities 
than the four you offer in the layering document.

>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.

Point taken.

>    Also, there are lists and classes that have to be in all OWL
>    interpretations.

Again, some do and some don't. In this example it seems sensible to 
say that the intersection class must be in all OWL interpretations, 
but not that the lists used to encode OWL syntax must be. To repeat: 
OWL is not obliged to respect all possible RDF interpretations; it 
can impose its own semantics on this syntax.

>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.

I disagree.

>
>2/ Now, consider classes that are finite sets.
>
>    rdfs:Class is always in the class consisting of rdfs:Class

Is that supposed to be a theorem? It is in RDFS, but one would not 
express it there by using a list, of course, but instead write

rdfs:Class rdf:type rdfs:Class .


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

What language is that written in?

As RDF, it makes a very odd assertion, which requires that some 
unspecified thing exists which apparently is a class containing 
rdfs:Class, but also bears an unspecified relation to another entity 
which bears another unspecified relation to rdfs:Class and yet 
another unspecified relation to something called owl:nil, whose 
nature remains mysterious.

As OWL, it means whatever we OWL-crafters decide it should mean. But 
we are not bound by what RDF thinks it means (not that to honor the 
very weak assumptions sketched above would be much of an imposition, 
mind you.) Either way, I see no way you can justify any claim that 
depends on this being forced to mean anything in particular, in 
either language.

For sure, it does not mean

rdfs:Class rdf:type rdfs:Class .

in RDF. I see no reason why it should mean that in OWL either, since 
the RDF could be used to say that in OWL without getting involved 
with these lists.

>    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.

It is not obvious to me that there must be such a list in every interpretation.

>    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.

Again, that seems to follow only from some kind of comprehension 
principle, which I think we should avoid having in OWL, or even 
pretending to have. ( The last thing a description logician would 
want to do, surely, is to make the language into a kind of set 
theory.)

>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.

True, but this does not capture the intuitive meaning of your 
example. What this says in RDF is that If John has a child that is a 
Person, then a Restriction *exists* such that John belongs to.... 
There is however no reason why it has to make that claim in OWL.  Why 
would OWL want to assert the *existence* of restrictions? Thats like 
having FOL assert the existence of its own formulae.

>    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.

Well, be careful. An RDF description can be constructed which asserts 
in RDF that something exists which, if interpreted in OWL, would be 
such a restriction, maybe; assuming of course that it was well-formed 
when considered as OWL.

>  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,

No, I insist. This is an *existential assertion*. It is not a set. We 
do not have a general licence to assume that every existential claim 
in RDF is true *in OWL*.  Existential assertions may well be false 
under certain circumstances: the things they purport to describe may 
not in fact exist.  If I write 'square circles are nice', I havn't 
thereby managed to create a square circle; Ive just said something 
nonsensical. [**]

The passage from a description of a thing, to the thing itself, is 
what is generally called a comprehension principle. It amounts to the 
claim that all descriptions of a certain kind do in fact describe 
something. The Russell paradox relies on such a principle, and is not 
paradoxical without it (just plain contradictory.)  It is the 
comprehension principle for relations that makes higher-order logic 
genuinely higher-order and not just a notational variation on 
first-order logic. We cannot possibly assume that OWL or RDF or 
indeed any part of Tim's layer cake will ever have a fully adequate 
comprehension principle, so we might as well admit that up front. 
Such things are noncomputable.

>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.

Right, it cannot satisfy the condition, which is not surprising as 
the condition has no models.

>  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.

You just used a comprehension principle to go from the *fact* of 
satisfying a condition, to the assumption of being in some semantic 
construction. This kind of reasoning applied to sets is called 'naive 
set theory', for a good reason. The only proper conclusion you can 
legitimately draw here is that it is related to itself by the 
rdf:type property in all *intended* models. However, the proper 
conclusion here is that there are *nonstandard* models which prevent 
you from making this inference (ie which prevent it being formally 
valid.) As is well-known, there is usually no way to rule out 
nonstandard models of any recursively enumerable set of theorems in a 
finite language.

>
>    So rdf:type is ill-defined on this restriction and thus it has no
>    satisfying OWL+ interpretations.

We are free to define a notion of OWL+ interpretation on this syntax 
which makes perfect sense of rdf:type. It would indeed not assign any 
satisfying interpretations to your example, but so what? The only 
conclusion would be that the OWL+ notion of satisfiability would be 
more restrictive than the RDF notion, which is no surprise.

>    However, this restriction only mentions objects that exist in all OWL+
>    interpretations.

See above: I see no reason to admit this as a conclusion. They exist 
in RDF interpretations of OWL syntax, but OWL can be more 
parsimonious than RDF in the things it recognizes to exist.

>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.

I wont bother going into the details as the above points all apply 
there as well.

Pat

[**]. To make the point. Consider the Russell paradox, which says 
that R is the set of all sets that are not members of themselves, and 
write it using a predicate instead of a set. Then it looks like this, 
in KIF notation:

R =df (lambda (?x)(not (?x ?x)))

Frege took it that he had a right to assume that any apparent 
definition of a set (a predicate, in this case) really did define a 
genuine set; the ultimate comprehension principle, we would now say. 
And if you were to take this seriously *as a definition*, then indeed 
you get into trouble, since  if (R R) then (not (R R)) (just call the 
function); and if (not (R R)) then - since R satisfies the definition 
- it must be that
(R R); so you are damned if you do and damned if you don't. But if 
you give up on that universal confidence in the power of definitions 
and admit that sometimes, things that look like definitions can turn 
out to be just empty claims, then there is no paradox.

The best one can do to say a definition in a modern logic is to 
assert a biconditional. Doing that to the Russell example gives this:

(forall (?x) (iff (R ?x)(not (?x ?x)))))

which has the immediate instance

(iff (R R) (not (R R)))

Now, that is NOT a paradox; its just a simple contradiction., like 
saying (P and notP). In fact its propositionally equivalent to (and 
(R R) (not (R R)). So what happened to the paradoxical argument? 
Well, you can indeed validly infer (R R) from (not (R R)) and vice 
versa, given this assumption; but so what, because you can infer 
ANYTHING from this assumption, since it is a contradiction. So the 
proper response to someone who asserts that Russell biconditional is 
to gently point out that they just contradicted themselves, rather 
than to be impressed by their ability to produce a contradiction out 
of a definitional hat. Frege's mistake was not realizing that his 
central definition had a contradiction in it. Moral: don't trust 
definitions until you have checked them out for hidden contradictions.
-- 
---------------------------------------------------------------------
IHMC					(850)434 8903   home
40 South Alcaniz St.			(850)202 4416   office
Pensacola,  FL 32501			(850)202 4440   fax
phayes@ai.uwf.edu 
http://www.coginst.uwf.edu/~phayes
Received on Thursday, 21 February 2002 21:23:38 GMT

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