Re: are there uncountably infinite types?

Aki, I'm in agreement with what you said for both questions.

I mentioned the uriReference thing in case it impacts on the rewording of
#1, and because someone clearly worked hard on making this spec exactly
right in these respects --- for example, "The value space of string is the
set of finite-length sequences of characters" is for all practical purposes
the same as eliminating the words "finite-length" [1].  The only difference
is that it makes this value space countable.  I noticed that this was not
done for uriReference, probably because there was an assumption that
RFC2396 made the restriction.  You said "The stated goal of URI is to
identify a resource", and couldn't we also argue that strings aren't useful
unless they're finite?  (You'll tell me that the string being useful is not
a stated goal.)  BTW - I went back and it even says that a URI "is a
compact string". [2]

I wanted to mention it in case whoever was so careful about the language
elsewhere cared that this requirement might not be explicitly stated, and
wanted to add the words "finite-length" to the uriReference definition as
well.  I have no objection to leaving it as it is, and assuming that this
restriction is in or implied by RFC2396.

[1] http://www.w3.org/TR/xmlschema-2/#string
[2] http://www.ietf.org/rfc/rfc2396.txt


Aki Yoshida <akitoshi.yoshida@sap.com> on 12/21/2000 04:39:55 AM

To:   Morris Matsa/Somers/IBM@IBMUS
cc:   <www-xml-schema-comments@w3.org>, Ashok Malhotra/Watson/IBM@IBMUS,
      Paul.V.Biron@kp.org
Subject:  Re: are there uncountably infinite types?



At 4:50 AM +0100 12/21/00, Morris Matsa wrote:
>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.

I agree that some kind of change or note (e.g. this uncountable stuff
doens't exist in the current spec but is kept in for the future version,
etc) is required.

>> 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.)

What I said above was misleading. I should have said:
An instance of uriReference can be arbitrarily long just as an integer can
be but they are both finite. So, it's still countable.

Our disagreement is the interpretation of RFC2396 for the definition of
URI.  RFC2396 doesn't limit the length of a URI but doensn't say the length
can be infinite. The stated goal of URI is to identify a resource so that
people can use this URI to universally refer to this resource.  Therefore,
all URIs are tightly bound to their lexical representation as their
exchange format to achieve this goal.  Thus, each instance has a finite
representation just as integers do. Otherwise, the goal of URI is not fully
achieved.

If we suppose instead there is a URI instance that can not be represented
by its lexical representation in a finite length, then your following
argument is true and the value space of uriReference becomes uncountable.

Some URI-spec authority people should decide on this.

Best regards,
Aki Yoshida

>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 17:34:57 UTC