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

From: Graham Klyne <GK@ninebynine.org>
Date: Fri, 30 Aug 2002 11:54:07 +0100
Message-Id: <5.1.0.14.2.20020830114448.03e6d640@127.0.0.1>
To: "Roy T. Fielding" <fielding@apache.org>

```
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

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 22:55:53 UTC