Re: Cardinality of N and P(N)
- From: "David R Tribble" <david@xxxxxxxxxxx>
- Date: 2 Aug 2005 13:08:03 -0700
Timothy Little <tim-usenet@xxxxxxxxxxxxxxxxxx> wrote:
>> Order has nothing to do with countability.
Alec McKenzie writes:
>> Really? I was under the impression that the rationals had been
>> proved to be countable by doing just that -- showing they could
>> be ordered in such a way as to be countable. Am I wrong?
Michael Stemper wrote:
> No ordering is necessary. I can show an injection from the rationals to
> the integers without any ordering needed:
>
> 1. Given a rational number, r, eliminate all common factors from the
> numerator and denominator.
> 2. Call the resulting denominator "q".
> 3. If r is nonnegative, call the resulting numerator "p". Calculate
> (2^p)*(3^q)
> 4. If r is negative, call the resulting numerator "-p". Calculate
> (2^p)*(5^q)
>
> A few examples:
>
> 1.4 = 14/10 = 7/5 yields (2^7)*(3^5) = (128)*(243) = 31104
>
> -3/6 = -1/2 yields (2^1)*(5^2) = 50
>
> Any rational that you give me will turn into a positive integer. But, no
> matter what rationals you give me, many positive integers will never get
> hit, such as { 7, 11, 13, 14, 17, 19, 21, 22, 23, 26, 28, ...}
>
> So, without any ordering, I can show that the set of rationals is no
> larger than the set of positive integers. (The mapping will define an
> ordering on the rationals, but the ordering wasn't used to define the
> mapping.)
But your mapping of rationals to naturals, call it M, can then be
used to impose an ordering on the rationals. For example, n=50
maps to q=-1/2, so -1/2 is the 50th rational in the sequence;
similarly, 7/5 is the 31,104th rational in the sequence, and
so on.
Listing M(1), M(2), M(3), ..., M(50) = -1/2, ... etc. denumerates
all of the rationals in a particular order. (Except for a few
values of M(n) that don't map to any rationals, such as M(1).)
It would seem to me that any defined counting of a set (or,
equivalently, any defined mapping of natural numbers to the set)
in turn defines an ordering of the members of that set.
Or have I missed something subtle here?
-drt
.
- Follow-Ups:
- Re: Cardinality of N and P(N)
- From: Michael Stemper
- Re: Cardinality of N and P(N)
- Prev by Date: Product of series question
- Next by Date: Re: Random Probability
- Previous by thread: Product of series question
- Next by thread: Re: Cardinality of N and P(N)
- Index(es):
Relevant Pages
|
