W3C home > Mailing lists > Public > w3c-rdfcore-wg@w3.org > June 2001

Re: log:forSome/#rdfms-identity-anon-resources

From: pat hayes <phayes@ai.uwf.edu>
Date: Thu, 28 Jun 2001 00:17:43 -0500
Message-Id: <v04210115b75d66689b6a@[205.160.76.188]>
To: Dan Connolly <connolly@w3.org>
Cc: w3c-rdfcore-wg@w3.org
>pat hayes wrote:
>[...]
> > The RDF distinction between anonymous nodes and named nodes is
> > logically invisible, as far as I can see.
>
>I have been convinced otherwise. I'm still not certain,
>but let's see if I can reproduce the argument
>and its ability to convince...
>
> > All nodes have an identity,
> > so giving one of them a URI doesnt really change anything about it or
> > what it means. All nodes could be non-anonymous and nothing would
> > change in the meanings of any RDF. Anonymity seems to be a kind of
> > syntactic sweetener which works by removing some bitterness rather
> > than by adding sugar.
>
>I think anonymous nodes have non-trivial expressive power.
>
>In sum: skolemization is *not* a two-way street:
>while a proof of a skolemized formula is generally
>accepted as a proof of the formula with existential
>quantifiers, it doesn't work the other way around.

Yes and no. Its true that you can't get from a proof of the 
existential to a proof with any particular skolem constant, ie if you 
fix on one skolem constant and then go back to the existential proof 
and ask for a proof containing *that* skolem constant, you can't get 
it from the existential proof, because to get a skolemised proof you 
have to re-skolemise, and every time you do that you will get a *new* 
skolem constant. But this new one and the old one are what one might 
call functionally equivalent, in that anything that you can prove 
about one of them you can also prove about the other (except of 
course being equal to itself).

Skolemising an existential is like saying 'OK, at least one thing 
exists ..... Choose one of them and call it FOO.' Now, once you have 
done that, you can again say 'choose one of them and call it BAZ', 
but you can't legitimately use 'FOO' again, since you have no way to 
know if you are choosing the same one.

>You lose information when you replace an
>existentially quanitified variable/term with
>a URI.

You don't gain or lose information by skolemising. What you do do, is 
provide a name for something that was previously nameless; but you 
don't gain any new information about it (unless you count that new 
name as new information; but since you generated it, that seems 
rather generous.)

>In detail: let's suppose you're buying a book.
>You transmit, to the bookseller, a description
>of the book you want to buy; roughly,
>"it's by Barnsley and it's called
>Fractals Everywhere. I want it in
>hardback, tomorrow."

Ingenious argument. But you have done something slightly odd in your 
logic here (maybe there is no way to avoid doing this in RDF, which 
is another issue, I'll return to that) by writing this as a simple 
existential. If you (just) say that "there exists a book by Barnsley 
and its called "Fractals Everywhere" and ..." then, indeed, the 
bookseller really has no way to know what you want. He has a book 
that satisfies this description, but there's nothing in a simple 
existential to guarantee that there might not be something else that 
satisfies it as well, so he can have no logical confidence that the 
thing he has that satisfies the description is the *same* as the 
thing that you have in mind that satisfies the description. If all 
that he has to go on is a simple existential, that is.  In order to 
know that the thing that you are saying exists is the *same* as the 
thing he knows exists, he has to know something else as well, which 
is that there is only one such thing (we are talking about books here 
as editions rather than copies, I assume). That can be said 
explicitly in KIF (FOL) by using universal quantification and 
identity, ie instead of just saying

(exists (?x) (and (by ?x Barnsley)...))

you include a statement of identity:

(exists (?x) (and (and (by ?x Barnsley)...)
                           (forall (?y)(implies (and (by ?y Barnsley)...)
                                                         (= ?x ?y))))

which is what Russell gave as the logical gloss for a definite 
description, ie this is what you get when you say something about 
'THE x which is by Barnsley and ......'. The 'THE' is what pins down 
the meaning to a single entity.

Now, if you apply this to your example, there can be two URI's, but 
it would follow (either from what you would have said, ie that you 
wanted THE book...., or from general knowledge that the bookseller 
has about uniqueness of author/title information, or something) that 
the two names (URIs) were equivalent, ie had the same denotation; so 
now there would be no loss of information at all.

This analysis requires logical apparatus which goes well beyond what 
RDF1.0 can do, but another way to think about how to convey the 
uniqueness assumption in your order, is to say that the URIs in the 
following example are not simple logical constants, but something 
more like public names. So the idea would be, here, that instead of 
the existential being in your Kbase, then getting sent to the 
bookseller, then processed by him in his Kbase, that something more 
like a process of setting up a 'common ground' happens, where some of 
your assertions and some of the booksellers assertions are brought 
into a common area of mutually accepted beliefs, like what seems to 
happen in a conversation. If that were possible, then it would be 
more like the two sets of beliefs being made to intersect, rather 
than thinking of them as communicating with each other, so that this 
existential about this book could then be mutually accepted. Then if 
it were skolemised *when in the common ground*, then only a single 
skolem name would be generated, but it - the new name - would be part 
of both your beliefs, and you could both use it to refer to the book 
you have agreed to talk about. This is a bit like a conversation 
between two mathematicians going like this:
A:  'I want to talk about a finite group with ten elements.'
B: 'OK.'
A: 'Call this group G'
B: 'OK, now what else do I need to know about G?'
....
where they can agree on a mutually acceptable name even when one of 
them doesnt yet know exactly what the other is talking about. Once A 
has said enough about G to enable B to figure out that there is only 
one thing that satisfies the description, B might say: 'now I know 
what you mean'.
(Another way to think about it is that you and the bookseller set up 
a temporary existential quantifier whose scope extends across 
sentences in both your Kbase and his, a kind of spanning quantifier; 
and then when you skolemise that, you both get beliefs involving the 
same name. I like this way of thinking, since it seems to suggest a 
way to analyse public names in general as implicit linking 
quantifiers whose scope extends across an entire community. )

>Formally, in n-triples:
>
>---8<---
>_:g0 <http://purl.org/dc/elements/1.1/title> "Fractals Everywhere" .
>_:g0 <http://purl.org/dc/elements/1.1/creator> "Barnsley" .
>_:g0 <http://booksellers.example/vocab#binding>
><http://booksellers.example/vocab#hardback> .
>_:g0     <http://booksellers.example/vocab#shipping>
><http://booksellers.example/vocab#nextDay> .
>---8<---
>
>In KIF, by my understanding of anonymous nodes:
>
>---8<---
>(exists (?x0 )
> (and
>  (PropertyValue http\:\/\/purl\.org\/dc\/elements\/1\.1\/title
>     ?x0
>     "Fractals Everywhere")
>  (PropertyValue http\:\/\/purl\.org\/dc\/elements\/1\.1\/creator
>     ?x0
>     "Barnsley")
>  (PropertyValue http\:\/\/booksellers\.example\/vocab\#binding
>     ?x0
>     http\:\/\/booksellers\.example\/vocab\#hardback)
>  (PropertyValue http\:\/\/booksellers\.example\/vocab\#shipping
>     ?x0
>     http\:\/\/booksellers\.example\/vocab\#nextDay)
>) )
>---8<---
>
>Now if I use something like Sergey's algorithm[1,2]
>to compute a URI for this anonymous term, I get
>something like:
>
>---8<---
><http://skolem.example#432oj34oij2o3ijo23j>
><http://purl.org/dc/elements/1.1/title> "Fractals Everywhere" .
><http://skolem.example#432oj34oij2o3ijo23j>
><http://purl.org/dc/elements/1.1/creator> "Barnsley" .
><http://skolem.example#432oj34oij2o3ijo23j>
><http://booksellers.example/vocab#binding>
><http://booksellers.example/vocab#hardback> .
><http://skolem.example#432oj34oij2o3ijo23j>
><http://booksellers.example/vocab#shipping>
><http://booksellers.example/vocab#nextDay> .
>---8<---
>
>i.e. in KIF:
>
>---8<---
> (and
>  (PropertyValue http\:\/\/purl\.org\/dc\/elements\/1\.1\/title
>     http\:\/\/skolem\.example\#432oj34oij2o3ijo23j
>     "Fractals Everywhere")
>  (PropertyValue http\:\/\/purl\.org\/dc\/elements\/1\.1\/creator
>     http\:\/\/skolem\.example\#432oj34oij2o3ijo23j
>     "Barnsley")
>  (PropertyValue http\:\/\/booksellers\.example\/vocab\#binding
>     http\:\/\/skolem\.example\#432oj34oij2o3ijo23j
>     http\:\/\/booksellers\.example\/vocab\#hardback)
>  (PropertyValue http\:\/\/booksellers\.example\/vocab\#shipping
>     http\:\/\/skolem\.example\#432oj34oij2o3ijo23j
>     http\:\/\/booksellers\.example\/vocab\#nextDay)
>)
>---8<---
>
>Now suppose the bookseller's inventory database shows:
>
>---8<---
><http://booksRus.example/inv2001-06-25#item342323>
><http://purl.org/dc/elements/1.1/title> "Fractals Everywhere" .
><http://booksRus.example/inv2001-06-25#item342323>
><http://purl.org/dc/elements/1.1/creator> "Barnsley" .
><http://booksRus.example/inv2001-06-25#item342323>
><http://booksellers.example/vocab#binding>
><http://booksellers.example/vocab#hardback> .
><http://booksRus.example/inv2001-06-25#item342323>
><http://booksellers.example/vocab#shipping>
><http://booksellers.example/vocab#nextDay> .
>---8<---
>
>i.e.
>
>---8<---
>(and
>  (PropertyValue http\:\/\/purl\.org\/dc\/elements\/1\.1\/title
>     http\:\/\/booksRus\.example\/inv2001\-06\-25\#item342323
>     "Fractals Everywhere")
>  (PropertyValue http\:\/\/purl\.org\/dc\/elements\/1\.1\/creator
>     http\:\/\/booksRus\.example\/inv2001\-06\-25\#item342323
>     "Barnsley")
>  (PropertyValue http\:\/\/booksellers\.example\/vocab\#binding
>     http\:\/\/booksRus\.example\/inv2001\-06\-25\#item342323
>     http\:\/\/booksellers\.example\/vocab\#hardback)
>  (PropertyValue http\:\/\/booksellers\.example\/vocab\#shipping
>     http\:\/\/booksRus\.example\/inv2001\-06\-25\#item342323
>     http\:\/\/booksellers\.example\/vocab\#nextDay)
>)
>---8<---
>
>
>This information from the inventory database clearly
>provides a match (i.e. a proof, or the interesting
>bits of one, anyway) for the
>description of the book stated as a formula involving
>an existentially quantified variable, ?x0.

No, not a description; it just proves that a book exists which 
satisfies the existential. But since there might be several things 
that satisfy an existential, nothing follows about whether the 
bookseller's item#342323 actually IS the particular thing that you 
had in mind when writing your order. (Not without some uniqueness 
assumption from somewhere.) So the bookseller is in the same position 
in either case. If he knows the thing is unique, he can figure out 
what you want; if he doesn't, he can't.

Of course, if you had phrased your order not as an existential but as 
a universal , so that you say: "if it is a book and has author...and 
title ...., then I want it", then the bookseller can figure out what 
you want. However, you might now get several books, unless you give 
enough of a description to pin down one uniquely.

>But it doesn't match/prove the formula where _:g0
>is replaced by the skolem constant
><http://skolem.example#432oj34oij2o3ijo23j> .

Right. And it might not be it. On the other hand it is possible that 
those names corefer, ie
(=  http\:\/\/booksRus\.example\/inv2001\-06\-25\#item342323
      <http://skolem.example#432oj34oij2o3ijo23j>)
and if the bookseller could somehow conclude this (eg by knowing that 
only one thing satisfied the description) then he could get you the 
book you want from your order, skolemised or not.

>So an RDF document with anonymous nodes is *not*
>interchangeable with a skolemized version of that document.
>Q.E.D.

It is if everyone is using valid logical reasoning.

>
>I think this is the important part of Pat's message
>that I disagree with is:
>
> > RDF is supposed to
> > consist of assertions, not equations, and they are pretty simple
> > assertions of the logical form (V s o) . Those s's and o's are
> > logical names = logical constants, ie they denote things, one thing
> > each in a given interpretation. Now, logical names are *just* like
> > existentially quantified variables where the quantifers are at the
> > top level (the only level there is in RDF), ie not inside any
> > universal quantifiers.
>
>The s's and o's would be just logical constants if we
>left out anonymous/existentially-quantified terms.
>But RDF does have such terms, as demonstrated above.
>And the semantics of such terms is non-trivially
>different from the semantics of constants:
>an existentially quantified formula is satisfied
>by an interpretation if there's *some* thing
>you can bind the existential term to that makes
>it work out.

Yes, and that is exactly the truth conditions for a logical name, as 
well; it has to have a denotation that makes the sentences containing 
the name work out true.

>Skolemizing the formula reduces
>the number of interpretations that satisify the
>formula.

No, it doesnt. Technically, if E is an existential sentence and E' is 
a skolemisation of it, then E and E' are actually in different 
logical languages, because the signature of E' has a new symbol in 
it, so it takes a little care to compare interpretations. If I is an 
interpretation of the smaller langauge (of E, without the new skolem 
name) then I can be easily extended to an interpretation I' of the 
larger language (of E') which is identical to I on the E-language and 
makes E' true (just make the skolem name denote one of the things 
that satisfies the existential.) And in the language of E' (with the 
skolem name), any interpretation which satisfies E' will also satisfy 
E, ie E' entails E in the E'-language. So either way round, 
skolemising the formula doesnt *reduce* the number of interpretations.
Theres quite a lot of depth to that notion of a 'new' name. In 
natural deduction systems where introducing new names is a legal 
inference step, the rules for scoping new names can get very 
complicated.

>It's one of those things that usually
>works "without loss of generality,"

No, it always works. You can see why if you transcribe it into 
second-order logic, since then the skolemisation process is basically 
just a quantifier exchange, and its actually valid in both 
directions. The first-order case seems clunkier only because in 
first-order order, any change to the nonlogical vocabulary goes 
outside the usual inference process and so isn't technically valid; 
but thats only a technicality.

>but doesn't,
>in the case of RDF; i.e. in the case when constant
>symbols that are shared between documents.

Ah, but wait: that 'shared' begs the question. A skolem constant 
generated inside one document cannot possibly be shared with another 
document; it has to be a new name, not one used anywhere else. 
(Possible thanks to the Power of the URI, right?). Now, once 
generated, it might later get transferred to another document, but 
that transfer process doesnt add any new information to it. If a name 
is shared between documents in such a way that each of them says 
something nontrivial about it (ie each one constrains the possible 
interpretations), then it can't be a skolem constant. (Unless maybe 
it was somehow introduced to them both simultaneously by some kind of 
'common ground' maneuver, as sketched above.)

BTW, an overall comment: all this discussion has been in the context 
of classical logic. If we are using a nonmonotonic logic of some 
kind, eg by assuming a unique-name condition, then skolemisation may 
well not be correct at all, and we would need to re-think the entire 
game. It may (MAY) be that Euler is using some such assumptions to do 
its LCU 'unification'; I honestly cannot follow what Euler is up to.

>p.s. This message is really about an existing issue
>http://www.w3.org/2000/03/rdf-tracking/#rdfms-identity-anon-resources
>
>The fact that there are graphs involving anonymous nodes
>that are not expressible in RDF/XML is, I agree, another
>issue; one that, I'm afraid, belongs in the
>postpone-to-next-version pile.
>
>[1] Re: RDF API 1.0 Draft / algorithm for anonymous URIs
>Sergey Melnik (Wed, 08 Dec 1999)
>http://lists.w3.org/Archives/Public/www-rdf-interest/1999Dec/0046.html
>
>[2] what I actually used was random scratching at the keyboard ;-)
>
>--
>Dan Connolly, W3C http://www.w3.org/People/Connolly/


Pat Hayes

---------------------------------------------------------------------
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, 28 June 2001 09:49:01 EDT

This archive was generated by hypermail pre-2.1.9 : Wednesday, 3 September 2003 09:37:18 EDT