Re: URI denumerability (one response to Roy, then I'll shut up ;-)

At 01:57 PM 8/28/02 -0700, Roy T. Fielding wrote:
>Just out of curiosity, could someone please explain why that same
>proof cannot be used to prove that URI are not denumerable?  Just
>replace the real numbers in the proof with their equivalent
>representation as a URI.

To do so presumes that *all* real numbers have an equivalent representation 
as a URI, which they don't.

By way of partial explanation (not proof), all the normal representations 
for numbers as character strings represent rational numbers;  e.g. a 
sequence of the form (digit*).(digit*) can easily be seen to always 
represent a rational number under normal fixed point decimal representation 
(think: n/10^m).  Similarly for formal floating point number 
representations (not counting odd values like "not-a-number").  Admitting 
(say) the square root operator into one's representation of numbers allows 
a denumerable subset of irrationals to be represented.  But ultimately, 
theres no scheme to represent every real number using a denumerable set of 
character strings (which URIs are).

Norm later says:
>I don't think the proof hinges on irrational numbers. The
>diagonalization proof that real numbers are not denumerable relies on
>the fact that you can always manufacture a new real number that is
>demonstrably not in your list. Whether or not that number is
>irrational is incidental. I think. :-)

I don't know how to argue the diagonalization case you raise, but there is 
a proof that the rational numbers are denumerable.  As I recall, it goes 
roughly like this:  a pair of positive integers n and m can represent any 
positive rational number >0 as n/m, so arrange the pairs thus:

     n  :| :
        3|3/1 3/2 3/3
        2|2/1 2/2 3/2
        1|1/1 1/2 1/3 ...
     ----+-----------------------
         | 1   2   3  ...

then arrange these as a sequence, following successive finite diagnonals in 
the matrix, thus:

    1/1, 1/2, 2/1, 1/3, 2/2, 3/1, ...

With some extra rules to exclude members not expressed in lowest terms, 
this establishes a 1:1 correspondence between rationals and positive integers.

#g


-------------------
Graham Klyne
<GK@NineByNine.org>

Received on Friday, 30 August 2002 08:11:52 UTC