modal logic, rdf and category theory

I changed the title to emphasize the new importance of modal
logic in the discussion in this thread.

> On 1 Sep 2018, at 21:52, Pat Hayes <phayes@ihmc.us> wrote:
> 
> On 9/1/18 5:46 AM, Henry Story wrote:
> > A bit over 4 years have passed since this thread
> > ( https://lists.w3.org/Archives/Public/semantic-web/2014Apr/ )
> > and I somehow ended up in University of Southampton studying
> > Category Theory and RDF.  I am especially interested in bringing modal logic
> > to it, for reasons explained in the paper "Epistemology in the Cloud - on Fake news
> > and digital Sovereignty" where I argue from an epistemological point of view for a peer
> > to peer hyper web based on modal analysis of knowledge.
> > This has been accepted for the 2018 Decentralizing the Semantic Web Workshop
> > at ISWC. details here: https://medium.com/@bblfish/epistemology-in-the-cloud-472fad4c8282
> >
> > That paper does not go into technical detail, but it did lead Pat Hayes to ping
> > me that he was not happy with having references to Possible Worlds in the original
> > RDF Semantics spec. (It would be nice to have precise reasons for why this was
> > later thought to be a mistake).
> 
> OK, since you asked :-)
> 
> The only place in the 2004 RDF specification where the phrase "possible world" is used is in a non-normative section which I wrote as an attempt to give a kind of intuitive outline of the basic ideas of Tarskian model theory, expressed in as intuitive a way as I could for readers who were new to the whole topic of formal semantics. And the phrase occurs even there only in an aside comment, inside scare quotes, to suggest one way to think intuitively about Tarskian interpretations. Nothing is said anywhere in that document or indeed anywhere else in the 2004 RDF specification documents to even remotely suggest that RDF has modal content or should be understood as a modal logic. (In fact, that idea is so far removed from the whole enterprise of RDF that the idea - and the concomitant possibility of misinterpreting that passing phrase in this way - did not even occur to me at the time.)
> 
> However, this attempt to give an intuitive introduction in a technical specification document was not a success, as it was almost immediately misunderstood by a large number of readers (including, apparently, yourself) and in any case, in retrospect, it was not appropriate to give tutorial material in a technical specification. The revised RDF 1.1 semantics document, replacing the 2004 document which is now deprecated, therefore omits all such intuitive explanations and describes the (slightly modified) semantics directly and formally, without mentioning 'worlds' at all, possible or otherwise.
> 

I did not think that it was a modal logic, but that it looked like the basis was there to develop it 
into one. As you mention below the RDF1.1 spec actually agrees with that, by mentioning the possibility of a semantic extension for modal logic in section 10.

All I think I need for many applications such as those related to security or access control, is very light logic of contexts to build on, which is seems to be what your very interesting Blogic proposal you referred to below is about. If the semantics of current RDF has not got this part quite right it seems to be there in the syntax from the beginning, since a RDF/XML document can contain another RDF/XML document, and presumably the point is not to automatically merge the embedded document with the one it is contained in. So what is the meaning of the embedded graph? Well it has to be some interpretation that satisfies the graph. But there could be many full interpretations in part because
one can only ever work out Finite interpretations (because the semantic web is incomplete) and these are compatible with very many full interpretations. But also because documents can be published to mislead ("fake news") software into believing the universe is other than it is. 

I have a short blog post "Phishing in Context - Epistemology of the Screen" that goes into this
where I make clear the importance of context, and how some good salesman arbitrarily named Donald
can try to use confusions of context as bait
https://medium.com/cybersoton/phishing-in-context-9c84ca451314

Another simple logic of Contexts is the well known work by Mike Burrows (who wrote the AltaVista search engine), Martin Abadi, Butler Lampson, Gordon Plotkin from 1993 "A calculus for access control in distributed systems" https://dl.acm.org/citation.cfm?id=155225

Quad stores (RDF Datasets) can clearly be used as a foundation to build such things on.

If you think as agents that write RDF graphs as processes, then you can see how this is coalgebraic.
Different such processes are writing from partial information situations in different contexts, and
with potentially antagonistic aims. Context matters.

> Right at the end of the RDF 1.1 semantics document there is indeed a tiny mention of the possibility of some future extension of RDF using a modal interpretation of RDF datasets (basically quad stores). But any such interpretation would require a major change to the semantics (analogous to the extension of Tarskian model theory to the Kripke semantics for modal logics) and some kind of enrichment of the RDF syntax to provide some way to indicate the syntactic scope of any modal operator. RDF graph syntax has no scope marking, a fact that gave the RDF and OWL WGs many technical challenges.

> (For further discussion of this point and what could be done about it, see
> https://www.slideshare.net/PatHayes/blogic-iswc-2009-invited-talk
> starting from slide 15.)

Very interesting set of slides. Here are some thoughts from my research in CT.

• Slide 10 on names

  The difference here is between names as syntactic, denotational semantic and operations semantic
terms. The syntactic view of names that algebraic views of logic have is the one espoused by the RDF specs. These are indeed interchangeable. 
  But the Semantic web is an evolutionary *process* that starts at a certain stage and develops, 
where different players have only a partial view on its evolution. Coalgebras represent the mathematics of states (that evolve) and observation as the subtitle of Bart Jacobs' recent book on Coalgebras points out clearly
https://www.cambridge.org/core/books/introduction-to-coalgebra/0D508876D20D95E17871320EADC185C6
  The Web itself is coalgebraic, since resources that URIs refer to are things that change *State*.
These are things that return representations (algebraically interpretable objects). 
  Hence the fight between many logicians and Linked Data folks may just be a case of a categorical
misapprehension between people working in a dual category.
  
  Anyway we agree here about names and the importance of reference. And I think the
categorical duality here can help give us a mathematical representation of the web that shows how
these two sides can work together.

• Slide 18 on blank nodes
 
   Interestingly here you note that the problem is with a set theoretic definition of blank nodes
that are global. Benjamin Braatz in his 2009 thesis 

"Formal Modelling and Application of Graph Transformations in the Resource Description Framework"
https://www.depositonce.tu-berlin.de/bitstream/11303/2617/2/Dokument_29.pdf
of which the first half is very readable for someone with knowledge of RDF.

gave a Category Theoretic model of RDF where each graph comes with its own blank node set, and
the only way to identify such nodes is by morphisms. This is actually an advantage of a category
theoretic way of looking things that tends to put less emphasis on identity and a lot more on morphisms. 

   Still it looks like RDF1.1 allows blank nodes across contexts (as I gather from 5.1.1), 
which would be a way to make statements de Re about someone's beliefs, eg:
  Laura Lane believes of Superman that he cannot fly.

_:superman = :SuperMan .
:LL believes { _:superman a :NonFlyingPerson;
                     foaf:name "Clark Kent" } .

I wonder how much the blank node sharing would require changes to Benjamin Braatz'
thesis.


> 
> >
> > It is to me very clear that RDF has a modal aspect to it, which comes out very clearly
> > with Quad stores.
> 
> That is totally unclear to me. Quad stores can be, and have been, used to represent all kinds of 'extra' content, including graphs with time-stamping or location-stamping or representing states of something or linking information about a person or topic to that person or topic. None of this is modal.

Well all of these are thought of as modal logics. My guess is that the concept that
ties all modal logics together is the concept of context. It would be interesting
to see if there is a proof of that...

> 
> > But it looks like this may need proving - or perhaps someone has already
> > done so? Modal logic need not I suppose involve possible worlds, and the interesting thing
> > is that Category Theories believe to have proven that modal logic is to coalgebras what
> > equational reasoning is to algebras.  See "Modal Logics are Coalgebraic" for a summary
> > https://academic.oup.com/comjnl/article-abstract/54/1/31/336864
> > Coalgebras give us the mathematics of infinite streams, processes, a notion of co-induction,
> > and are to semantics what algebra is to syntax.
> >
> > All RDF semantics tells us is how to merge two graphs when one believes them both
> > to be true.
> 
> Not quite "all", but your introduction of "believes" is gratuitous. The RDF (and OWL) semantics saying nothing about believing or beliefs.

Yes, that's because I am thinking in terms of using these specs by writing User Agents that need to
help the User work with the published graphs encountered on the web in order to arrange meetings,
buy products, etc... So I take a pragmatic action oriented view of these specs.

Here R. Brandom, a student of David Lewis, whose thesis was on Impossible Worlds, and who went on
from there to develop a philosophy of Analytic Pragmatism, is well worth looking at. He uses pragmatism
I think to sidestep the idealisation of possible worlds, by instead speaking of the logical consequences an actor is bound to by making a statement. Such statements can of course be contradictory, which is why this is a process oriented view of possibilities, as I understand.

But nevertheless, the spec would say that the two graphs have compatible interpretations. Since any graph can have any number of interpretations, this is saying that there some number of models that makes them true. But then if there is set of model that makes them true, that may not be a model the actor dealing with that graph believes to be true - ie one he would act on. Though he may be keen to use the misapprehension of the actor with that belief to take advantage of that situation. 
Which is pretty much how Phishing works.

> 
> > But what if one believes that someone else believes them to be true?
> 
> And how is that nested modality to be represented in a form that can be transmitted across the Web? You need to explain how RDF syntax can be extended to cover this kind of assertion.

One does not need to transmit it over the web for it to be useful. If I have an 
application that merges different graphs and presents this to the user it should be
possible for the user to be surprised about a conclusion reached, ask then where
the information came from, and potentially remove some graphs that he finds dubious.

But one can even with RDF/XML pass graphs inside graphs since one can pass an rdf literal
in an rdf graph, and that can contain an rdf literal too...

But there is also some basic ways this has been done since the blogosphere where they
invented the nofollow attribute when linking to something, the user wanted to speak about
whilst telling Google that he did not want his link to count as a +1 for that web page.

Similarly one could have a relation relating an Agent to a content such as :disagrees
to keep a distance between that content and ones affirmed by the agent.

> 
> > Then by merging them one can find out what they think is true, and one can model that
> > in terms of possible worlds, or for those more syntactically oriented sets of all the
> > ways of completing those graphs in ways that are consistent (or sets of maximally complete
> > such graphs). There is a clear modal element to that, in so far as one cannot
> > merge graphs of what one believes to be true into someone else's belief store without getting
> > a wrong idea of what they believe.
> 
> But one can say all of this without mentioning the modal notion of belief. You are here simply talking about truth, consistency and validity (or otherwise) of inference on RDF graphs, but adding 'believes' instead of 'true' throughout.

yes, I am speaking of actors that use these graphs in order to act in the world. I don't believe
and I don't think anyone here believes that software has to be written that maps an rdf graph
to the interpretation in the world. What happens is that software developers map graphs to 
User Interfaces in a functorial way, and these user interfaces are then mapped by humans in the
end to things in the world. The humans complete the interpretation functor by composing with the
initial one designed by the software developer. 

I give a simplistic but at least intuitive view of how such a functorial notion of semantics can
be understood to work in the math exchange question
https://math.stackexchange.com/questions/2896172/how-should-one-model-rdf-semantics-in-terms-of-category-theory

I need to develop that a lot more of course...

> 
> >
> > So if this still needs to be proven
> 
> What exactly "needs to be proven" ?

I suppose that RDF1.1 with datasets is compatible with modal logic. Though I 
have a feeling that Kripke modal logic is too simple and even David Lewisian 
modal logic which is a neighborhood semantics based one is not quite right.

In the newly published book "Category Theory for the Working Philosopher"
https://books.google.de/books?id=RIM8DwAAQBAJ
there are many very intersting articles. One by Abramski on Contextuality and
Paradox. But also the one by Kohei Kishida on "Categories and Modalities"
which looks a neighborhood semantics with impossible worlds and shows 
how that can be understood in terms of category theory.

I have not yet fully digested all these different pieces. But I hope this
gives some idea as to the work one could draw on to further the semantic web
and the web in general by placing it on even firmer formal foundations.


> 
> > it seems like Institution theory may help to do
> > so. In a very interesting paper from 2006 by Dorel Lucanu, Yuan Fang Li, and Jin Song Dong
> > entitled "Semantic Web Languages – Towards an Institutional Perspective" show how one can
> > use the theory of institutions to show how RDF, RDFS, OWL (light, DL,...,Full), ... that
> > seem to have very different semantics can in fact be seen to be consistent.
> 
> The OWL specification documents show this already, in almost painful detail. (Well, insofar as it is correct. Some RDFS tautologies are not valid in any OWL dialect, for example.)

Thanks for pointing that out.

In fairness, the article "Semantic Web Languages - Towards an Institutional Perspective" was 
published in 2006 while the document "OWL 2 Web Ontology Language Mapping to RDF Graphs"
    https://www.w3.org/TR/2012/REC-owl2-mapping-to-rdf-20121211/
came out in Dec 2012 so over 6 years later.

I remember in the early days people doubting that these languages could have the same
semantics, and using that as an argument for the infeasibility of the semantic web. 

> > http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.119.5368&rep=rep1&type=pdf
> > So if someone tells you that these are incompatible semantics point them to that paper.
> 
> Or read the specifications themselves :-)

Yes, now I can point people to two such documents, and most interestingly for me
is I can see how the two methodologies overlap or diverge.


> Pat
> 
> >
> > It looks like work needs to be done to show that these are also compatible with
> > modal logics (with neighborhood semantics is my guess: ie coalgebras of the form
> >     S -> S^2^2
> > a.k.a
> >     S -> 𝒫𝒫(S)
> > where 𝒫(S) is a predicate and 𝒫𝒫(S) is a set of predicates. Now if one thinks
> > of a graph as a predicate on possible worlds, one sees why this is similar to quad
> > stores. Those are known as a hyper-system as explained in "Universal Coalgebra: A Theory
> > of Systems" http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.159.2020&rep=rep1&type=pdf
> >
> > As for good introductions to CT, since that was part of the topic 4 years ago,
> > I think the best online intro (and more) for programmers are Bart Milewski's
> > ( https://bartoszmilewski.com/ ) videos on youtube
> > https://www.youtube.com/user/DrBartosz/playlists
> > I really recommend it. He is extremely clear without being boring.
> >
> > I also liked a lot "Category Theory for Computing Science" by Michael Barr and
> > Charles Wells  (online http://www.tac.mta.ca/tac/reprints/articles/22/tr22.pdf )
> > because they make the relation of categories to Graphs so clear.
> >
> > Indeed just because the relation is so striking I asked a question on Math
> > Stackexchange to illustrate how one could be (mis?)lead into a simple pattern
> > of thinking of the relationship
> >
> > https://math.stackexchange.com/questions/2896172/how-should-one-model-rdf-semantics-in-terms-of-category-theory
> >
> > Has anyone come across further developments in this space since then?
> >
> > Henry Story
> >
> >
> >
> >> On 17 Apr 2014, at 20:02, Obrst, Leo J. <lobrst@mitre.org> wrote:
> >>
> >> Back a few years, emerging from the old IEEE Standard Upper Ontology group’s work was Bob Kent’s Information Flow Framework, an ontology framework (a meta-level framework) based on Barwise & Seligman’s Information Flow Theory, itself an application of Category Theory. See, for example: http://arxiv.org/pdf/1109.0983v1.
> >>
> >> Mainly folks have used Information Flow Theory or Goguen’s notion of institutions as springboards from category theory to ontologies, especially for so-called “lattice of theories”, ontology mapping, and semantic interoperability applications. Work includes Mossakowski’s various papers: http://iws.cs.uni-magdeburg.de/~mossakow/.
> >>
> >> For a short “position” paper, see:
> >> Markus Kr¨otzsch, Pascal Hitzler, Marc Ehrig, York Sure. 2005. Category Theory in Ontology Research: Concrete Gain from an Abstract Approach. http://www.aifb.kit.edu/web/Techreport893.
> >>
> >> For RDF and category theory, the only paper I know of addresses graph transformations for RDF:
> >> Benjamin Braatz; Christoph Brandt. 2008. Graph Transformations for the Resource Description Framework. Proceedings of the Seventh International Workshop on Graph Transformation and Visual Modeling Techniques (GT-VMT 2008). http://journal.ub.tu-berlin.de/eceasst/article/view/158/142.
> >>
> >> Admittedly most of the above are applications beyond logic itself and RDF, but might shed some light on how category theory is being used for ontologies.
> >>
> >> Thanks,
> >> Leo
> >>
> >> From: henry.story@bblfish.net [mailto:henry.story@bblfish.net]
> >> Sent: Wednesday, April 16, 2014 6:09 PM
> >> To: Gregg Reynolds
> >> Cc: Antoine Zimmermann; SW-forum Web; public-philoweb@w3.org
> >> Subject: Re: rdf and category theory
> >>
> >>
> >> On 11 Apr 2014, at 16:32, Gregg Reynolds <dev@mobileink.com> wrote:
> >>
> >>
> >> On Fri, Apr 11, 2014 at 8:30 AM, Antoine Zimmermann <antoine.zimmermann@emse.fr> wrote:
> >> There're a lot of resources available online and for free about category theory.
> >>
> >> Some examples:
> >>   - Jirí Adámek, Horst Herrlich, George E. Strecker. Abstract and Concrete Categories: The Joy of Cats (524 pages). http://katmat.math.uni-bremen.de/acc/acc.pdf
> >>   - Maarten M. Fokkinga. A Gentle Introduction to Category Theory: the calculational approach.http://wwwhome.ewi.utwente.nl/~fokkinga/mmf92b.pdf (80 pages).
> >>   - Jaap van Oosten. Basic Category Theory (88 pages). http://www.staff.science.uu.nl/~ooste110/syllabi/catsmoeder.pdf
> >>
> >>
> >> One of the best is Robert Goldblatt's Topoi : The Categorial Analysis of Logic .  He pays special attention to linking CT concepts to both classic math and ordinary intuition.
> >>
> >> I looked through Robert Goldblatt's Topoi quickly [1] and indeed it is the book that covers the subject probably most relevant to the semantic web community, since it aims to show how logic can be derived from Category Theory. In this area I found reading through the first part of Ralf Krömer's "Tool and Object: A History and Philosophy of Category Theory" to also be very interesting, as it gives an overview of the foundational debate in Mathematics  started by CT.
> >>
> >> It's so odd that RDF is entirely about relations just as CT is ( except that RDF is one to many whereas CT arrows are functions). So I really look forward to understanding how these two domains fit together, and perhaps how they complement each other.
> >>
> >>
> >> Henry
> >>
> >> [1] Having read through half of  "Conceptual Mathematics" by Willima Lawvere and done most of the exercises there, I am starting to be able to read a lot of these books much more easily.
> >>
> >>
> >>
> >>
> >> -Gregg
> >>
> >> Social Web Architect
> >> http://bblfish.net/
> >
> >
> >
> >
> >
> -- 
> -----------------------------------
> call or text to 850 291 0667
> www.ihmc.us/groups/phayes/
> www.facebook.com/the.pat.hayes

Received on Sunday, 2 September 2018 13:04:39 UTC