W3C home > Mailing lists > Public > www-rdf-logic@w3.org > February 2001

Re: universal languages

From: Daniel Mahler <mahler@cyc.com>
Date: Mon, 5 Feb 2001 11:19:01 -0600
Message-ID: <14974.57477.177224.710439@mcallister.cyc.com>
To: pat hayes <phayes@ai.uwf.edu>
Cc: "Tim Berners-Lee" <timbl@w3.org>, "Drew McDermott" <drew.mcdermott@yale.edu>, <connolly@w3.org>, <www-rdf-logic@w3.org>, <pfps@research.bell-labs.com>, <danbri@w3.org>, <horrocks@cs.man.ac.uk>

pat hayes writes:
 > Yes, but that is not the central problem. That is Turing 
 > undecideability, but the original Goedel problem cuts deeper: if you 
 > have 'reasonable' expressive powers in a descriptive logic (hard to 
 > define exactly in full generality, but basically if you combine 
 > recursion with quantification) then if you also give it a truth 
 > predicate (make it able to describe truth a wide enough range of 
 > languages to include itself), then it will be *incoherent*. It will 
 > generate paradoxes all by itself.  So there are no 'universal' 
 > languages. This is now a very basic and well-investigated idea, about 
 > as well-established and thorougly understood as, say, the second law 
 > of thermodynamics.

I believe that in a previous post I demonstrated
that such an inconsistency would arise in DAML,
if negation is introduced using reification as has been proposed.
Below is the RDF representation of a Goedel sentece.

<rdf:RDF xmlns:rdf="http://www.w3.org/TR/REC-rdf-syntax#"
          xmlns:rdfs="http://www.w3.org/TR/rdf-schema#"
          xmlns:daml="http://www.daml.org/2000/12/daml+oil#"
	  xmlns:toolbox="http://www.w3.org/DesignIssues/Toolbox#"
          >

<rdf:Description rdf:ID="goedel">
		 <rdf:type resource="rdf:Statement"/>
                 <rdf:subject resource="goedel"/>
                 <rdf:predicate resource="toolbox:truth"/>
                 <rdf:object rdf:value="0"/>
</rdf:Description>

</rdf:RDF>

RDF reification seems to make it particularly easy to
construct self referential sentences.
Relying on it to actually define logical mechanisms like
quantification and negation
seems like a walk on the wild side.

Daniel Mahler
Cycorp Inc

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
From: Daniel Mahler <mahler@cyc.com>
To: www-rdf-logic@w3.org
Subject: reification, negation & paradox in daml
Date: Tue, 16 Jan 2001 17:00:39 -0600


I believe the reification approach to negation leads
directly to Tarski's paradox.
In hindsight this is not be a surprise since
<http://www.w3.org/DesignIssues/Toolbox#truth>
is a truth predicate.
Normally, one would require more logical machinery
then graond atoms and conjuction to do real dammage.
However, the peculiarities of the graph model
seem to make it very easy to construct a Goedel sentence,
since we can explicitly construct cycles in the representations of
reified statements, thus creating representations
of fixed points of parametrized statements.
(ie self referential sentences)

<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-schema-ns#"
          xmlns:rdfs="http://www.w3.org/2000/01/rdf-schema#"
          xmlns:daml="http://www.daml.org/2000/12/daml+oil#"
	  xmlns:toolbox="http://www.w3.org/DesignIssues/Toolbox#"
          >

<rdf:Description rdf:ID="goedel">
		 <rdf:type resource="rdf:Statement"/>
                 <rdf:subject resource="goedel"/>
                 <rdf:predicate resource="toolbox:truth"/>
                 <rdf:object rdf:value="0"/>
</rdf:Description>

</rdf:RDF>

If we then wanted to query the model
about the toolbox:truth of "goedel",
it can be neither 1 nor 0.
We could just say it is 0,
since there is no toolbox:truth statement
actually asserted about "goedel".
However, that would be a very strong form
of the closed world assumption
and it would render reification and toolbox:truth
devoid of any logical content.

Since we are using the truth predicate to define
negation, rather then attempting to describe
an existing operator like Tarski,
it seems we are forced to abandon classical
logic to avoid the paradox.

This problem is not limited to negation,
but will also apply to using reification to simulate
second order predicates and modalities.
The general scope of this problem
was discussed by Montague.
There is also a very detailed discusion of the issues in
Raymond Turner's "Truth and Modality for Knowledge Representation"
book. The upshot is that only fairly weak operators
can be handled consistently using predicates over reified sentences.

Daniel Mahler
Cycorp Inc
Received on Monday, 5 February 2001 12:19:24 GMT

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