Re: infinity

Ross A. Finlayson wrote:
>> So: well-order the reals.
>

Jonathan Hoyle wrote:
> Sigh. Didn't I do this one already? Here it is again <grin>:
>
> Take any arbitrary 1-1 mapping F from the reals R to the power set of
> natural numbers P(N). By the Axiom of Choice, we know we can
> well-order P(N), so take any such well-ordering, <=. Define a <=
> operation (obviously different from the standard one) on R such that
> for a,b in R, a <= b whenever F(a) <= F(b). You have now well-ordered
> R. Creating F and well ordering P(N) are left as exercises. :-)

The mapping F:R->P(N) can be defined as follows.

For simplicity, we first map the reals in (-oo,+oo) into the more
manageable interval [0,1):
g(x) = 1 - 1/(x^2+1) for all x in R.

Now for real r in [0,1), define the function:
M(r,i) = floor(r x 2^i) mod 2, for all i=1,2,3,...

In other words, M(r,i) is the i-th binary fractional digit of r for
all 0 <= r < 1. For example, given r = 0.6875 = 11/16 = .1011(2),
M(.1011, 0) = 1,
M(.1011, 1) = 0,
M(.1011, 2) = 1,
M(.1011, 3) = 1.

Now for all real r in [0,1), define the set
f(r) = { M(r,i+1) for all i=0,1,2,3,... }

In other words, f(r) is the set of naturals that correspond to the
powers of non-zero binary digits of fractional real r. For example,
r = 0.6875 = 11/16 = .1011(2)
r = 1/2^(0+1) + 1/2^(2+1) + 1/2^(3+1)
therefore:
f(0.6875) = f(11/16) = f(.1011) = {0,2,3}.

Combining f and g gives us our mapping function, which is the union
of all f(r) sets:
F(x) = f(g(x)) for all x in R.
So we have a mapping that maps reals to subsets of naturals, which
are member subsets in P(N).

There remains the small problem of duplicate binary fractions,
such as:
0.010111...
0.011000...
which are the same real point in [0,1) but which correspond to
different member sets of P(N):
f(.010111...) = {1,3,4,5,...}
f(.011000...) = {1,2}.

But this is not a problem since we're only concerned about ordering
the reals that we can map from R into P(N), not the other way
around. (Even if it was a concern, we could safely ignore the
duplicates because there are only a countably infinite number of
them, and P(N) is an uncountably infinite set.)

.

Relevant Pages

  • Re: Uncountable sets in CZF?
    ... naturals bijectively to the reals. ... relatively modern response to the vagaries of infinitesimals of Newton ... from the naturals to the reals was the definition of the Natural/Unit ... properties similar to EF in monotonically mapping. ...
    (sci.math)
  • Re: induction vs Cantor
    ... > that creates a new mapping for each natural number. ... > between the naturals and the reals. ... It's a pity that you don't understand what a Proof By Contradiction means. ...
    (sci.math)
  • Re: induction vs Cantor
    ... > that creates a new mapping for each natural number. ... > between the naturals and the reals. ... It's a pity that you don't understand what a Proof By Contradiction means. ...
    (sci.logic)
  • Re: Zenkins paper on Cantor
    ... > as least as many reals not in that list as are in the list to start with. ... A bijection between the naturals and reals is not accepted by ... My perception _was_ that you could toss out antidiagonals all day and after ... the mapping must be that way. ...
    (comp.theory)
  • Re: Zenkins paper on Cantor
    ... > as least as many reals not in that list as are in the list to start with. ... A bijection between the naturals and reals is not accepted by ... My perception _was_ that you could toss out antidiagonals all day and after ... the mapping must be that way. ...
    (sci.math)