W3C home > Mailing lists > Public > www-xml-schema-comments@w3.org > October to December 2000

Re: are there uncountably infinite types?

From: Morris Matsa <mmatsa@us.ibm.com>
Date: Wed, 20 Dec 2000 22:50:08 -0500
To: "Aki Yoshida" <akitoshi.yoshida@sap.com>
Cc: <www-xml-schema-comments@w3.org>
Message-ID: <OFAAE430C5.43DAA10B-ON852569BC.000854C0@somers.hqregion.ibm.com>


For question 1:  Thank you for the history, I wasn't involved when there
were real numbers, and it seems to explain the sentence.  You seem to be
confirming that now there is no longer a way to make a type with an
uncountably infinite value space.  If this is so, should the spec be
amended slightly?  It now says (see below) "others are uncountably
infinite" which is at least misleading.

> For Question 2:
> A uriReference can be infinitely long just as an integer can. So, it's
still
> countable.

For question 2: I disagree.  I'll tell you why I feel the way that I do,
and please tell me where I'm going wrong.  (I'm still not sure anybody
would care even if I'm right.)

The way I see it, the difference between integers and uriReferences is that
while there are infinitely many integers, the lexical representation of any
given integer is finite, although arbitrarily long  (the same is true for
rational numbers and all other finite and countably infinite sets, given
the correct lexical representation).  This is not true for uriReferences
--- a given uriReference can be infinitely long (the same is true for
irrational numbers, real numbers, and all other uncountably infinite sets,
regardless of lexical representation).

Consider a trivial one-to-one mapping between real numbers between 0 and 1
and a subset of uriReferences:  Take the decimal representation of the real
number and add a slash between every two digits, eliminating the leading
"0."  [Admittedly, this is a mapping between decimal representations of
real numbers and uriReferences, and there are more representations of real
numbers than there are real numbers (e.g. 0.09999... = 0.10000...), so
eliminate the redundant representations and reduce the subset of the
uriReferences involved, and the point is the same.]

If you prefer, use a diagonalization argument on a similar subset.

Do you still think that the value space of uriReferences is countable?  I'm
rusty on this stuff so I'll believe you - please explain.
(I also wonder if it matters given that the lexical space of all
uriReferences encodable in the universe is finite.)

Morris


"Aki Yoshida" <akitoshi.yoshida@sap.com> on 12/20/2000 07:41:32 AM

To:   Morris Matsa/Somers/IBM@IBMUS
cc:   <www-xml-schema-comments@w3.org>
Subject:  Re: are there uncountably infinite types?



For Question 1:
An earlier draft had a datatype called "real" whose value space included
irrational numbers.
Although thatdraft provided no way to lexically represent these values,
from
the value-space
point of view,  these values were there and therefor, this datatype was
classified as
uncountably infinite.

In contrast, the value space for the current decimal datatype is
constrained
by  i * 10^-n, where
both i and n are integers (which is countably infinite). Therefore, the
decimal type is classified as
countably infinite.  If instead we didn't make the above value constraint,
we would have
an uncountably infinite decimal.


For Question 2:
A uriReference can be infinitely long just as an integer can. So, it's
still
countable.

Best regards,
Aki Yoshida

---------------------------------------------------------------
From: "Morris Matsa" <mmatsa@us.ibm.com>
Date: Tue, 19 Dec 2000 18:27:43 -0500
Subject: are there uncountably infinite types?


Part 2 of the spec (http://www.w3.org/TR/xmlschema-2/#dt-cardinality) says
that:
"Every value space has associated with it the concept of cardinality. Some
value spaces are finite, some are countably infinite while still others are
uncountably infinite."  Table C.1 "Fundamental Facets", also in part 2 of
the spec, (http://www.w3.org/TR/xmlschema-2/#app-fundamental-facets) lists
all of the built-in datatypes and their cardinalities, and none of them are
uncountably infinite.  Elsewhere, the spec tells us how to figure out the
cardinality of the value spaces of user-defined data types
(http://www.w3.org/TR/xmlschema-2/#dc-defn), none of which end up
uncountably infinite.

1. My first question is how any type can ever end up uncountably infinite,
as the spec claims?

2. My second question is a minor one - I was wondering whether all of the
primitive types should be defined as not being uncountably infinite.  For
example, I looked at uriReference, and it seems uncountably infinite.  It
is defined (http://www.w3.org/TR/xmlschema-2/#uriReference) as "a Uniform
Resource Identifier (URI) Reference as defined in Section 4 of [RFC 2396],
as amended by [RFC 2732]."  From skimming RFC2396 it seems that a URI
mostly reduces to a sequence of path segments.  In section 3.3. of RFC 2396
(http://www.ietf.org/rfc/rfc2396.txt) it says "The path may consist of a
sequence of path segments separated by a single slash "/" character."  This
does not say, as the Schema spec would, "a finite sequence of path
segments", so it seems that URIs may be infinitely long, in which case the
value space of uriReference would be uncountably infinite.  Am I right?
Received on Wednesday, 20 December 2000 22:48:25 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Sunday, 6 December 2009 18:12:49 GMT