For each A ∈ { Z, Q,  } find the cardinality of the set of all increasing bijective functions f : A → A.

For each A ? { Z, Q, R }, find the cardinality of the set of all increasing bijective functions f : A ? A. 

  • Mistake in Title, need Z Q and R

Answer

1. There are $\aleph_0$ (countably many) increasing bijective functions $f \colon \mathbb{Z} \rightarrow \mathbb{Z}$. In fact, the map $f \mapsto f(0)$ is an explicit bijection between the set of these functions and $\mathbb{Z}$ itself.

It is enough to show that, for any such $f$ and for every $x \in \mathbb{Z}$, $f(x) = x+ f(0)$. We do that by induction on $\lvert x \rvert$. If $x=0$, the statement is trivial. Suppose that the thesis is true for $\lvert x \rvert < n$, and let's show it for $n$ and $-n$. Let's look at $f^{-1}(n+f(0))$. We have that $f^{-1}(n+f(0)) > f^{-1}(n+f(0)-1) = n-1$ by inductive hypothesis, but if $f(n) > n+f(0)$, then $n-1 < f^{-1}(n+f(0)) < n$, absurd. The same argument applies for $-n$, so this is a bijection and so there are countably many such functions.


2. There are $2^{\aleph_0}$ (the cardinality of the continuum) increasing bijective functions $f \colon \mathbb{Q} \rightarrow \mathbb{Q}$. Of course there are at most $2^{\aleph_0}$ as the set of all functions $f \colon \mathbb{Q} \rightarrow \mathbb{Q}$ has cardinality $\aleph_0^{\aleph_0} = 2^{\aleph_0}$, and this is a subset.

Let $a_0, a_1, \dots$ be an infinite sequence of positive integer numbers. There are $2^{\aleph_0}$ of them. We want to construct a strictly increasing bijective function $f \colon \mathbb{Q} \rightarrow \mathbb{Q}$ for each of them, injectively. Let $f(x) = x$ for $x \leq 0$, $f(n+1) = f(n) + a_n$ for $n$ positive integer, and let $f(x) = f(\lfloor x \rfloor) + a_{\lfloor x \rfloor} (x - \lfloor x \rfloor)$ for any other $x > 0$. I want to show that these functions are all distinct, strictly increasing, and bijective.

It is easy to see that these functions are all distinct: if two sequences $(a_n)_{n \in \mathbb{N}}$ and $(b_n)_{n \in \mathbb{N}}$ first differ at some $n$, then the corresponding values of $f(n+\frac{1}{2})$ are going to be different, namely $f_a(n + \frac{1}{2}) = f_a(n) + \frac{1}{2} a_n$ and $f_b(n + \frac{1}{2}) = f_b(n) + \frac{1}{2} b_n$, which are distinct as $f_a(n) = f_b(n)$ but $a_n \neq b_n$.

It is also obvious that they are strictly increasing and bijective, as they are obtained by gluing strictly increasing and bijective functions on the intervals $(-\infty, 0]$ and $[n, n+1]$ for $n \in \mathbb{N}$ so that they coincide at the endpoints.

So there are at least $2^{\aleph_0}$ such functions, but also at most $2^{\aleph_0}$ such functions, hence there are exactly $2^{\aleph_0}$ such functions.

 

3. There are $2^{\aleph_0}$ increasing bijective functions $f \colon \mathbb{R} \rightarrow \mathbb{R}$. It is easy to see that any strictly increasing bijection must be continuous, as the preimage of an interval must be an interval, and so the preimage of an open set must be an open set, which implies continuity.

(here a reference if you want a rigorous proof: https://math.stackexchange.com/questions/1918145/prove-that-a-bijective-strictly-increasing-function-is-continuous)

Any continuous function $f \colon \mathbb{R} \rightarrow \mathbb{R}$ is completely determined by the values it assumes on $\mathbb{Q}$, but there are only $2^{\aleph_0}$ functions $f \colon \mathbb{Q} \rightarrow \mathbb{R}$, as $\# \mathbb{R}^\mathbb{Q} = (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0}$. So there are at most $2^{\aleph_0}$ such functions. To see that there are at least $2^{\aleph_0}$ strictly increasing bijections, we can either consider the ones from point 2. or notice that, for any $y \in \mathbb{R}$, the function $f_y(x) = x+y$ is strictly increasing and bijective.

  • for 1. f(x) = 2x+1 is a counter example?

  • It's not bijective, the image only has odd numbers.

  • If you want a heuristic argument, bijectivity between discrete sets means there cannot be any "holes", so once you fix the image of a number (say, 0), then the image of the neighbours must be the neighbours of the image, and so everything is fixed. The rigorous argument is the one I gave in the proof.

The answer is accepted.