Hacker News Reader

Comment by yarg | Hacker News Reader

Some of those infinities are the same, others are not.

There's a one to one mapping between the integers and the cartesian product of the integers (I^I == I), but (I believe) that's not true for the reals (someone correct me if I'm wrong about that).

However, you can take some subset of R^n and stretch it to infinity across all dimensions, giving you back R^n.

So:

There are the same number of integers as odd integers,

There are more points on a continuous plane than on a continuous line.

The number of points on a line is the same as the number of points on the edge of a circle.

The number of points in a plane is the same as the number of points in a semiplane.

There are the same number of rationals as integers.

There are more reals than integers.

View on HN

I think it was clear from there their comment that they not only understood that, but picked those examples specifically because of that understanding. Your comment would be fine if it were framed as clarifying that for those who didn't understand, but as it is it just seems to out you as them.

He may have stated the things that are not true to illustrate that they don't seem that different from those that are, but could have been clearer in delineating the two sets.

> (I believe) that's not true for the reals (someone correct me if I'm wrong about that).

It is also true for the reals. R^2 can be trivially mapped to R.

Here's one mapping from R to R^2:

Let b_{n} b_{n-1} .. b_0 . b_{-1} b_{-2} ...

Be the binary representation of the real 'x'. For example, if x = 2.5, then:

b_1 = 1

b_0 = 0

b_{-1} = 1

Have x map to the following value in R^2 (y, z) where

y = b_{n} b_{n-2} ... b_{0} . b_{-2} b_{-4} ..

z = b_{n-1} b_{n-3} .. b_{1} . b_{-1} b_{-3} ..

So 2.5 -> (0, 1.5)

1 -> (1, 0)

1.75 -> (1.5, 0.5)

etc.

> It is also true for the reals. R^2 can be trivially mapped to R.

> Here's one mapping from R to R^2:

That's the easy part. It's very easy to map R to R^2, the other direction not so much.

From my searches, based upon what other people said, the mapping is a surjection and not a bijection.

If that's the case, then either they don't have the same cardinality or I'm confused as to what cardinality actually is.

There is no need to exhibit bijections, if you have an injection X -> Y and an injection Y -> X, then X and Y have the same cardinality. This is the statement of the Cantor-Schroeder-Bernstein theorem.

If you assume the axiom of choice it's enough to have surjections both way.

I get how you can map every value in R -> R^2, but I have yet to see any proof that there's a complete mapping in reverse.

For the most reasonable attempt at flooding a plane with R, I still end up with something where I can trivially define values {r0, r1} that do not map back to R.

What are those trivially defined {r0,r1} for the "interleaving digits" map f:(0,1) -> (0,1)^2 defined by taking a real x in (0,1), writing its decimal expansion as

x=0.a1a2a3a4a5a6...

(always pick the nonrepeating decimal expansion in case x has two) and sending it to the pair (y,z) where

y=0.a1a3a5... z=0.a2a4a6...

(Using (0,1) is no issue since we can compose later with bijections (0,1) -> R)

Edit: I'm not sure why I cannot reply to your reply, but {π,π} is not even in (0,1)^2

We can also do a map f:R -> R^2 directly, it's just slightly more annoying to write. Take a real number x, written in decimal expansion as

x=bn...b2b1b0.a0a1a2a3a4...

where again we choose the representation which is not repeating in case x has two. We also choose our first index n so that bn is zero but b(n-1) is not. We now map x to the pair (y,z), where

y=...b5b3b1.a1a3a5...

z=...b4b2b0.a0a2a4...

So that, for example, (π,π) is the image of x=33.114411559922...

{π, π} will generally do.

Sorry, didn't even look at the bounds - assumed things went to infinity.

As an example, try using a Hilbert curve to map {π, π} back onto R (and I mean π exactly, not π ± an infinitesimal).

(There are, however, infinitely many mappings for {π, π ± ε} -> R and {π ± ε, π} -> R, such that ε is infinitesimal.)

Correct...except that there are the same number of points on a line as in a plane.

Aleph_0^2 = Aleph_0

Aleph_1^2 = Aleph_1

How though (genuine question)?

I can see space filling curves through I^I, but I can't see them covering R^I.

How does a space-filling curve cover a plane without being filled with infinitesimal discontinuities?

Hilbert curves

Yes, I've got that part - but that only gets me as far as R * I ^ (d - 1), not R ^ d.

(d being the dimensionality of the curve.)

As I think about this there's an unfilled infinitesimal R ^ (d - 1) space orthogonal to every point on the curve.

I don't see how it is that that does not manifest as discontinuities in the filled space.

You can get from R^d to I^d (with I the open unit interval) easily by applying x -> (arctan(x) + pi/2)/pi and y -> tan(pi * y - pi/2) to each coordinate. There are also ways to go from R to the closed unit interval. You can then combine this with space-filling curves for I^d.

You can even go from R to I^d.

The problem that I'm having is in getting from R to R^d, which I still don't think is possible - look at the comment where I mention "surjections" and "bijections".

By applying the map from I^d to R^d (using the tan-arctan-construction above in each coordinate) after the map from R to R^d, you get a map from R to R^d.

I^n is just a countably infinite subset of R^n.

No, I^n is also uncountable. In fact, the usual proof for the uncountability of R is really proof of the uncountability of I, and then the natural injection into R is used to extend it to R.

Whether |R|=aleph_1 is independent of ZFC (but of course there are bijections both between R and R^2 and between aleph_1 and aleph_1^2, or between X and X^2 for any infinite set)

https://mathoverflow.net/questions/126069/bijection-from-mat...

https://mathoverflow.net/questions/240249/continuous-map-fro...

https://mathoverflow.net/questions/34232/injective-maps-math...

The second link says that there's a continuous surjection from R -> R^2, but no such bijection.

(Which, after some googling looks in line with what I was imagining.)

If there's no bijection, how can the cardinalities be the same?

Because continuity is not required here. There are non-continuous bijections between R and R^2.

How is continuity not required?

If there are holes in the map does it really cover the whole space?

I think you have misconceptions about what continuity means and I’m not even sure what you mean with holes.

As a simpler example: The map that multiplies each rational number by -1 and keeps irrational numbers as they are is bijective (it’s its own inverse), however it is nowhere continuous.

First of all the first link explicitely constructs (in a very strong sense) an explicit bijection R->R^2 so I don't know how why you seem to think otherwise.

It is true that there is no continuous bijection R -> R^2. It is also true that this has nothing to with cardinality, which is only about the existence of bijections (and indeed is defined for arbitrary sets with no topological structure for which continuity makes no sense)

I don't think that it's actually formulating a bijection across the reals - the generator function looks to me to be generating the complete set of rationals.

> Represent each real number x∈[0,1) as a sequence of DIGITS, where each DIGIT is either in {0,…,8} or is of the form 10∗(10k−1)+i with k≥1 and i∈{0,…,8} (i.e., in {90,…,98;990,…,998;9990,…,9998;…}.

He's iterating to infinity, that sure as shit sounds countable to me.

Anyway, the conclusion that I've come to is that you can map R onto a subset of R^n such that for all values {r[1] ... r[n]} in R^n there is a value in the R -> R^n mapping within all finite bounds.

So as long as you stay away from infinitesimals (not all of them), the domains are equivalent.

https://en.wikipedia.org/wiki/Infinitesimal

> In mathematics, an infinitesimal number is a quantity that is closer to zero than any standard real number, but that is not zero.

But as far as I can tell, the reverse mapping has an R^(n - 1) orthogonal that is completely unaccounted for, within those finite bounds.

(And breaking infinitesimals might cause some trouble for calculus.)

He's associating to each x in [0,1) an infinite sequence of natural numbers (just like decimal representations do), and there's uncountably many such sequences

But he's defining the numbers with a property that makes them countably infinite?

    prefix = '0.';
    queue = new Queue(prefix);
    for(;;){
        s = queue.poll();
        for(c:['0'...'9']){
            queue.add(s + c);
        }
    }

When the constraint is "run forever" I don't think that the generator he defined produces results any different from the snippet above.

The part that seems problematic is "each real number" the reals exist across bounds, I'm not sure there can be an "each".

I think his iterator is generating infinitesimals of rational and not continuous nature.

I may have misread that one, but I still think the reverse mapping only gets as far as within arbitrary bounds.

Reply on news.ycombinator.com