- From: pat hayes <phayes@ai.uwf.edu>
- Date: Thu, 28 Jun 2001 00:17:43 -0500
- 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 UTC