2
$\begingroup$

I'm not sure of the best vocabulary here, but is the infinite Cartesian product $$\mathbb{Z} \times \mathbb{Z} \times \cdots$$ in any important sense "equivalent" to $\mathbb{R}$? I believe they have the same cardinality, but is that enough to call them equivalent?

$\endgroup$
  • 4
    $\begingroup$ Equality of cardinality is one of many equivalence relations. The word "equivalent" means different things in different contexts. $\endgroup$ – Michael Hardy Sep 20 '17 at 19:27
  • $\begingroup$ Do you want an explicit bijection? $\endgroup$ – Dattier Sep 20 '17 at 19:36
  • $\begingroup$ @Typhon : it is a possible interpretation of the word "equivalent", especially since I do not know such a bijection (explicit). $\endgroup$ – Dattier Sep 20 '17 at 19:47
  • $\begingroup$ So I think what you're trying to ask is: Is there any "natural" nontrivial structure we can put on $\mathbb R$ and $\mathbb Z^{\mathbb N}$ such that they're isomorphic? $\endgroup$ – hmakholm left over Monica Sep 20 '17 at 20:50
  • $\begingroup$ @Typhon, in my reading, "which kind of equivalence could there be here" is part of the question, and equipotency is just the trivial baseline answer. $\endgroup$ – hmakholm left over Monica Sep 22 '17 at 2:05
2
$\begingroup$

They indeed have the same cardinality. And yes that is not very interesting since cardinality merely measures the size of collections in terms of injections, and ignores any other overlying structure (which in this case includes the arithmetic and analytic properties of the reals). $ \def\nn{\mathbb{N}} \def\zz{\mathbb{Z}} \def\qq{\mathbb{Q}} \def\rr{\mathbb{R}} \def\ceil#1{\left\lceil#1\right\rceil} \def\lfrac#1#2{{\large\frac{#1}{#2}}} $

But there is a curious elegant bijection between $\rr$ and $\zz \times \nn^\nn$. Cardinality wise, it is just obvious, since $\#(2^\nn) \le \#(\nn^\nn) \le \#((2^\nn)^\nn) = \#(2^\nn)$. But explicitly, not so obvious. One could invoke the Schroder-Bernstein theorem, but that is not very constructive, and of course does not preserve any structural properties of $2^\nn$. Also, there is the annoying issue that $2^\nn$ can encode binary strings that represent reals, but there will be countably many pairs that represent the same real, so you would have to amend the bijection, thus spoiling any structural relation.

So I shall now show the direct bijection from $\rr$ to $\zz \times \nn^\nn$, which is based on continued fractions.


Define $f : \rr \times \nn \to \nn$ and $g : \rr \times \nn \to \rr$ recursively as follows for each $r \in \rr$:

  $g(r,0) = r$.

  $f(r,n) = \ceil{g(r,n)}-1$ for each $n \in \nn$.

  $g(r,n+1) = \lfrac1{g(r,n)-f(r,n)}$ for each $n \in \nn$.

Then define $j : \rr \to \zz \times \nn^\nn$ by $j(r) = \langle f(r,n) \rangle_{n=0}^\infty$ (namely $\langle f(r,0),f(r,1),f(r,2),\cdots \rangle$).

Then it is not hard to prove that $j$ is a desired bijection. Roughly: If $j(r) = j(s)$, then for each $n \in \nn$ such that $g(r,n)+\lfrac1k \le g(s,n)$ for some $k \in \nn_{>0}$ we have $f(r,n) = f(s,n)$ and hence $g(r,n)-f(r,n) \le g(s,n)-f(s,n)-\lfrac1k \le 1-\lfrac1k$, but $g(r,n)-f(r,n) > 0$ and so $k > 1$ and hence $g(r,n+1)-g(s,n+1) = \lfrac{g(s,n)-g(r,n)}{(g(r,n)-f(r,n))(g(s,n)-f(s,n))} \ge \lfrac1{k-1}$, which by induction will yield a contradiction. (Note that this proof can be easily rephrased constructively to show that if $r+\lfrac1k \le s$ then $j(r),j(s)$ differ within the first $k$ terms.) The proof that $j$ is surjective is left as an exercise.


Furthermore, $j$ has nice properties:

  • $j(r)$ ends with zeros iff $r \in \qq$.

  • $j^{-1}$ is continuous in the sense that, for every $r \in \rr$ and $ε \in \rr_{>0}$, there is some $k \in \nn$ such that $|r-j^{-1}(v)| < ε$ for every sequence $v \in \zz \times \nn^\nn$ that agrees with $j(r)$ on the first $k$ terms.

  • $j$ on computable reals is computable.

  • $j^{-1}$ on computable sequences in $\zz \times \nn^\nn$ is computable.

$\endgroup$
  • $\begingroup$ Of course, there is an explicit computable bijection from $\nn$ to $\zz$, so there is no essential difference between $\zz \times \nn^\nn$ in my post and $\zz^\nn$ in the original question. $\endgroup$ – user21820 Sep 22 '17 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.