ontolog-forum
[Top] [All Lists]

## Re: [ontolog-forum] puzzles

 To: "[ontolog-forum] " Chris Menzel Sun, 30 Apr 2006 13:43:08 -0500 <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 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 > > 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) QUICK SUGGESTION    (03) 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) TWO PROBLEMS    (05) 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) DISCUSSION    (015) 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/ Subscribe/Unsubscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/ Shared Files: http://ontolog.cim3.net/file/ Community Wiki: http://ontolog.cim3.net/wiki/ To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx    (019) ```
 Current Thread [ontolog-forum] puzzles, Smith, Barry Re: [ontolog-forum] puzzles, Chris Menzel <= Re: [ontolog-forum] puzzles, Chris Menzel