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

Re: Maximum cardinality of an RDF model

From: pat hayes <phayes@ai.uwf.edu>
Date: Mon, 22 Jan 2001 15:36:46 -0800
Message-Id: <v04210108b69272e1e1cd@[130.107.66.237]>
To: Miles Sabin <MSabin@interx.com>
Cc: www-rdf-logic@w3.org
>Working on the assumption that there's at most a countably
>infinite set of URI(-refs) ... each is a finite sequence of
>charaters drawn from a finite alphabet ... and similarly for
>Literals, am I right to infer that,
>
>1. there is at most a countable infinity of resources: because
>   every resource has a URI(-ref) and no two distinct resources
>   share a URI(-ref).
>
>hence that,
>
>2. the set Resources from rdfms 5.1, is at most countably
>   infinite,
>
>3. the set Properties from 5.3 is at most countably infinite:
>   because a (proper) subset of Resources.
>
>and hence that,
>
>4. RDF models can contain at most countably many statements:
>   becauce they're subsets of,
>
>     Properties x Resources x (Resources U Literals)
>
>   which is at most countably infinite because Properties,
>   Resources and Literals are.

Yes, you are right to infer that. However, your question raises 
another, related, issue: according to several members of the group 
which developed RDF, the 'graph model' of a set of RDF triplets is 
intended itself to be *the* model (in the sense from model theory) of 
those triplets. It follows that all RDF models of any RDF ontology 
(that could be stored on any web page, at any rate) must be not only 
countable, but finite. Now, since the finite-model restriction is not 
expressible in first-order (or any complete semi-decideable) logic, 
this would appear to indicate that RDF must have a semantics which 
has no semidecision procedure (and hence no proof procedure.)

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 Monday, 22 January 2001 18:34:12 GMT

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