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

Re: Revised Axioms for Cardinality Restrictions

From: Richard Fikes <fikes@KSL.Stanford.EDU>
Date: Fri, 14 Sep 2001 10:54:06 -0700
Message-ID: <3BA2443E.988EFDFB@ksl.stanford.edu>
To: Richard Waldinger <waldinger@AI.SRI.COM>
CC: "www-rdf-logic@w3.org" <www-rdf-logic@w3.org>, Pat Hayes <phayes@ai.uwf.edu>
> > As discussed earlier, the cardinality axioms that use NoRepeatsList do
> > not require or assume that lists can be infinite in length.  So, that is
> > not an issue.
> > 
> 
> Right, the axioms straddle the fence on the finite-ness issue.  But to
> prove the desired properties of carinality restrictions, we need to add
> an axiom that will, under ordinary models, force some lists, or sets, to
> be infinite.

Oh, I now see your point that the axioms for cardinality and
maxCardinality do not work if all lists are considered to be finite. 
(The axiom for minCardinality doesn't appear to have the problem.) 
However, that problem can apparently easily be fixed by requiring that a
NoRepeatsList of appropriate length exist rather than stating the
conditions in terms of all such NoRepeatsLists, as follows:

MAXCARDINALITY AXIOM

I had proposed the following axiom for maxCardinality:

%% If a property P is a value of "onProperty" for a restriction R and a
non-negative integer N is a value of "maxCardinality" for R, then an
object I is type R if and only if for all V1, if V1 is a
"NoRepeatsLists" of length M such that the list's items are exactly the
values of P, then M is less than or equal to N.  (I.e., a
"maxCardinality" restriction of N on a property P is the class of all
objects I which have at most N values of P.)

(=> (and (PropertyValue onProperty ?r ?p)
         (PropertyValue maxCardinality ?r ?n))
    (forall (?i) 
            (<=> (Type ?i ?r)
                 (forall (?vl ?m) 
                         (=> (and (NoRepeatsList ?vl ?m) 
                                  (forall (?v) 
                                          (<=> (PropertyValue 
                                                 item ?vl ?v) 
                                               (PropertyValue 
                                                 ?p ?i ?v))))
                             (=< ?m ?n))))))

{Note that in the above axiom I have made the correction regarding the
scoping of ?m that you pointed out in your message.}

That axiom says that object ?i is type ?r if and only if all
NoRepeatsLists containing exactly the values of property ?p at ?i have
length less than or equal to the maxCardinality ?n.  We can change the
axiom to say that ?i is type ?r if and only if there exists such a
NoRepeatslist.  I think that sidesteps the finiteness issue.  The
revised axiom would be as follows:

%% If a property P is a value of "onProperty" for a restriction R and a
non-negative integer N is a value of "maxCardinality" for R, then an
object I is type R if and only if there exists a
"NoRepeatsLists" of length M such that the list's items are exactly the
values of P and M is less than or equal to N.  (I.e., a
"maxCardinality" restriction of N on a property P is the class of all
objects I which have at most N values of P.)

(=> (and (PropertyValue onProperty ?r ?p)
         (PropertyValue maxCardinality ?r ?n))
    (forall (?i) 
            (<=> (Type ?i ?r)
                 (exists (?vl ?m) 
                         (and (NoRepeatsList ?vl ?m) 
                              (forall (?v) 
                                      (<=> (PropertyValue 
                                             item ?vl ?v) 
                                           (PropertyValue 
                                             ?p ?i ?v)))
                              (=< ?m ?n))))))

CARDINALITY AXIOM

I had proposed the following axiom for cardinality:

%% If a property P is a value of "onProperty" for a restriction R and a
non-negative integer N is a value of "cardinality" for R, then an object
I is type R if and only if there exists a "NoRepeatsLists" of
length M whose items are exactly the values of P, then M is equal to N. 
(I.e., a "cardinality" restriction of N on a property P is the class of
all objects I which have exactly N values of P.)

(=> (and (PropertyValue onProperty ?r ?p)
         (PropertyValue cardinality ?r ?n))
    (forall (?i) (<=> (Type ?i ?r)
                      (forall (?vl ?m) 
                              (=> (and (NoRepeatsList ?vl ?m) 
                                       (forall 
                                         (?v) 
                                         (<=> (PropertyValue 
                                                item ?vl ?v) 
                                              (PropertyValue 
                                                ?p ?i ?v))))
                                  (= ?m ?n))))))

We can make an analogous change in this axiom as in the maxCardinality
axiom.  Namely, require that there exist a NoRepeatsList of length ?n
containing exactly the values of ?p at ?i, as follows:

%% If a property P is a value of "onProperty" for a restriction R and a
non-negative integer N is a value of "cardinality" for R, then an object
I is type R if and only if there exists a "NoRepeatsLists" of
length N whose items are exactly the values of P. 
(I.e., a "cardinality" restriction of N on a property P is the class of
all objects I which have exactly N values of P.)

(=> (and (PropertyValue onProperty ?r ?p)
         (PropertyValue cardinality ?r ?n))
    (forall (?i) (<=> (Type ?i ?r)
                      (exists (?vl) 
                              (and (NoRepeatsList ?vl ?n) 
                                   (forall 
                                     (?v) 
                                     (<=> (PropertyValue 
                                            item ?vl ?v) 
                                          (PropertyValue 
                                            ?p ?i ?v))))))))


---------------

> > That is, I think we can modify the
> > axioms so that the existence of a NoRepeatsList containing any given
> > finite number of objects is assured.  Attached below is a
> > straightforward way of doing that.
> > Add a second argument to relation NoRepeatsList that is the length of
> > the list.  Then, the axiom defining NoRepeatsList becomes the following:
> > 
> > (<=> (NoRepeatsList ?l ?n)
> >      (or (and (= ?n 0) (= ?l nil)) 
> >          (and (= ?n 1) (exists (?x) 
> >                         (= ?l (listof ?x)))) 
> >          (and (not (item (rest ?l) (first ?l))) 
> >               (NoRepeatsList (rest ?l) (- ?n 1)))))     [NoRepeatsList
> > axiom 1]
> 
> This says that ?l is a NoRepeatsList of length ?n.
> Fine, but you could just as well have left the definition the same and
> said
>  (and (NoRepeatsList ?l)(length ?l) = ?n)
> 
> > 
> > Add an axiom stating that NoRepeatsLists exist for any finite collection
> > of objects as follows:
> 
> > 
> > (=> (and (Integer ?n)
> >          (>= ?n 0)
> >          (NoRepeatsList ?l1 ?n) 
> >          (not (item ?l1 ?x)))
> >     (exists (?l2) (and (NoRepeatsList ?l2 (+ ?n 1)) (item ?l2 ?x))))
> 
> You shouldn't need an axiom for this.  Just take
> ?l2 to be Cons(?x, ?l1).

Hmm.  That is probably correct, and if so is simpler than what I
proposed.  What we are both saying is needed (in the formulation that
uses lists) are axioms assuring that the needed NoRepeatsLists exist. 
What we are both demonstrating is that adding such axioms can be done
without difficulty.

Richard
Received on Friday, 14 September 2001 13:54:14 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 2 March 2016 11:10:36 UTC