RE: are there uncountably infinite types?

Oops- hit send too soon.  Try again.

Every value space has associated with it the concept of cardinality.  Some
value spaces are finite, such as boolean, some are countably infinite, such
as integers and strings, and some are uncountably infinite, such as real
numbers.  A datatype is said to have the cardinality of its value space.
This specification does not currently support any datatypes of uncountably
infinite cardinality.

Matthew

> -----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:15:35 UTC