- From: Graham Klyne <GK@ninebynine.org>
- Date: Fri, 30 Aug 2002 11:54:07 +0100
- To: "Roy T. Fielding" <fielding@apache.org>
- Cc: www-tag@w3.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