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

RE: are there uncountably infinite types?

From: Fuchs, Matthew <matthew.fuchs@commerceone.com>
Date: Thu, 21 Dec 2000 15:05:10 -0800
Message-ID: <4C4A7BE77CE1D311A1D200508BA38C1202F3533D@venus.commerceone.com>
To: "'Biron,Paul V'" <Paul.V.Biron@kp.org>, "'Morris Matsa'" <mmatsa@us.ibm.com>, Aki Yoshida <akitoshi.yoshida@sap.com>
Cc: www-xml-schema-comments@w3.org


> -----Original Message-----
> From: Biron,Paul V [mailto:Paul.V.Biron@kp.org]
> Sent: Thursday, December 21, 2000 2:37 PM
> To: Fuchs, Matthew; 'Morris Matsa'; Aki Yoshida
> Cc: www-xml-schema-comments@w3.org
> Subject: RE: are there uncountably infinite types?
> 
> 
> Conceptually, it is easy to imagine type systems that contain 
> types with
> uncountable infinite value spaces (anything that had a true 
> real number type
> is the prototyplical example).  The wording that the original 
> commentor
> quoted was trying to be as general as possible and state the 
> posibilities.
> As Mathew notes, it is highly unlikely that the schema 
> language will ever
> include support for such types.  So, to more directly address 
> the original
> commentors point, yes, I think we should amend the definition 
> in question to
> be as follows:
> 
> 	[Definition:] Every value space has associated with it the
> 	concept of cardinality. Some value spaces are finite, some
> 	are countably infinite (conceptually, some value spaces may
> 	also be uncountably infinite, although this 
> specification does not
> 	currently support those value spaces). A datatype is said to
> 	have the cardinality of its value space.
> 
> Does anyone have any objects to this change? or a suggestion 
> for a better
> alternate wording?
> 
> pvb
> > -----Original Message-----
> > From:	Fuchs, Matthew [SMTP:matthew.fuchs@commerceone.com]
> > Sent:	Thursday, December 21, 2000 1:44 PM
> > To:	'Morris Matsa'; Aki Yoshida
> > Cc:	www-xml-schema-comments@w3.org
> > Subject:	RE: are there uncountably infinite types?
> > 
> > I think Aki means that a uriReference is of arbitrary length, not
> > infinitely
> > long.  A URI of infinite length would not be very useful on 
> current or
> > projected hardware/software, but there is a countably 
> infinite number of
> > URIs (which seems reasonable - do we really need more 
> resources than there
> > are particles in the universe?)
> > 
> > There may eventually be applications that use datatypes to 
> express either
> > infinite values or uncountably infinite value spaces, but they will
> > undoubtedly use some form of symbolic expression, such as 
> sqrt(2) or pi
> > for
> > infinite values, just as mathematicians always have.  
> However, I seriously
> > doubt that XML Schema will ever include native support for 
> these (although
> > some of them may end up in our type library).
> > 
> > Matthew
> > 
> > > -----Original Message-----
> > > From: Morris Matsa [mailto:mmatsa@us.ibm.com]
> > > Sent: Wednesday, December 20, 2000 7:50 PM
> > > To: Aki Yoshida
> > > Cc: www-xml-schema-comments@w3.org
> > > Subject: Re: are there uncountably infinite types?
> > > 
> > > 
> > > 
> > > 
> > > 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 Thursday, 21 December 2000 18:05:44 GMT

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