[Top] [All Lists]

Re: [ontolog-forum] puzzles

To: "[ontolog-forum] " <ontolog-forum@xxxxxxxxxxxxxxxx>
From: Chris Menzel <cmenzel@xxxxxxxx>
Date: Sun, 30 Apr 2006 13:43:08 -0500
Message-id: <20060430184308.GS96390@xxxxxxxx>
On Sun, Apr 30, 2006 at 06:15:30PM +0200, Barry Smith wrote:
> Patrick,
> I am trying, in my usual fumbling fashion, to understand your 13250-5
> CD ( [1]http://www.isotopicmaps.org/TMRM/TMRM-latest.html) document.
> We have the following (all from pp. 1-2):
> > Subjects are represented by subject proxies (proxies ).
> >
> > Proxies consist of properties ... which in turn may contain
> > references to other proxies. This recursive relationship is defined
> > via two postulated sets. One is the set of labels, L . Each label
> > from this set corresponds to exactly one proxy and vice-versa; ...
> > The second set postulated here is V , a set of values. It contains
> > values (such as numbers, strings, etc.), and all the labels in L .
> >
> > A property is the pair <h,k> in L x V. The set of all such
> > properties is denoted as P .
> >
> > EXAMPLE 1 Given the label shoesize and the integer 43, then
> > <shoesize, 43> is a property.
> >
> > A proxy is a finite set of properties, { p_1 , . . . , p_n } , with
> > p_i in P.
> >
> > The set of all proxies is the set of all subsets of P : X = 2^P
> >
> > NOTE 2: Subject proxies are composed of properties, each being a
> > statement about the proxy's subject.    (01)

> This raises, e.g., the following questions:
> If each label from the set L corresponds to exactly one proxy and
> vice-versa, and if the set V contains L and all the numbers, then how
> is it possible that the set of proxies is of cardinality 2P? Given
> that P itself is L x V, wouldn't this mean something like:
> card(L) = card(2L x Aleph_0)?    (02)


A problem with HTML formatted mail is that math formatting doesn't
always render properly.  (I've used "2^P" to indicate exponentiation
notation above, and I think Barry is intending to indicate
exponentiation as well but it doesn't appear to be rendering properly
for me.)  So let me suggest that, to ensure proper interpretation,
rather than relying on HTML, we use standard ASCII conventions for
writing math, e.g., * for multiplication, ^ for exponentiation, etc.    (04)


Barry points out a couple of problem in Section 3 of the Topic Maps spec.
Here are the key propositions:    (06)

(1) Each label h in L corresponds to exactly one proxy and vice versa.    (07)

(2) Let P = L x V.  P is the set of *properties*.    (08)

(3) A *proxy* is a finite set of properties.    (09)

(4) The set X of all proxies is the set of all subsets of P, i.e., X is
    the power set of P.    (010)

Problem 1    (011)

(3) and (4) are inconsistent if the set V of values can be infinite
(which is not ruled out in the spec).  For suppose V includes, say, the
set of natural numbers.  Obviously, then, there are infinite subsets of
X, i.e., of the set L x V.  By (4), such subsets of X are legitimate
proxies.  Hence, there are infinite proxies.  But this contradicts (3).    (012)

Problem 2    (013)

By (1), there is a one-to-one correspondence between the set L of all
labels and the set X of all proxies.  But this is impossible.  For by
(2) and elementary set theory, L is no larger than P.  But X is the
power set of P, and so, by Cantor's theorem, there is no one-to-one
correspondence between P and X.  Hence, there is no one-to-one
correspondence between L and X.      (014)


Problem 1 can be avoided by (i) requiring the set L of labels and the
set V of values to be finite, or (ii) allowing infinite proxies, or
(iii) restricting the definition of the set X to the set of all *finite*
subsets of P.  Given that finitude is explicit in (4), its omission from
(5) simply appears to be an oversight, so solution (iii) might be
preferred here.    (016)

Problem 2 remains on solutions (i) and (ii) of Problem 1, as Cantor's
Theorem holds for finite and infinite sets alike.  AFAICS, Problem 2 can
be avoided only by either abandoning (1) and allowing for proxies for
which there are no corresponding labels, or by requiring that L be
infinite and that proxies be cardinally smaller than the size of L.  In
particular, it can be avoided if L and V are both required to be
countably infinite (in which case P = L x V is also countably infinite)
and, following solution (iii) to Problem 1, X is defined to be the set
of all finite subsets of P, which would then be countable as well.  It
would then follow that L and X, both being countably infinite, could be
put in one-to-one correspondence (though I think we'd be rather hard
pressed actually to *exhibit* such a correspondence).  I am no expert on
the applications of Topic Maps, but simply clobbering (1) seems to me to
be the easiest solution here.  Why should there be a label corresponding
to every arbitrary finite collection of label/value pairs?    (017)

Chris Menzel    (018)

Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/ 
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx    (019)

<Prev in Thread] Current Thread [Next in Thread>