3
$\begingroup$

This is just a completely random question of the top of my head.

Let $\Omega$ be the set of bijections $\phi:\mathbb{N} \cup \{0\} \rightarrow \mathbb{Q}$.

We can imagine any $\phi \in \Omega$ to be equivalent to a wacky "staircase", where for $x \in \mathbb{R}^+$ we have $x \mapsto \phi(\lfloor x \rfloor)$.

If we walk along this staircase, the biggest step we need to take is of size $\sup_{n \geq 0} |\phi(n+1)-\phi(n)|$. Suppose we want to make the steps as small as possible. How small can we make them? That is, what is \[\inf_{\phi \in \Omega} \sup_{n \geq 0} |\phi(n+1)-\phi(n)|\ \ ?\]

2 Answers 2

4

I would claim the limit is zero. First, here is a version with the step under 2. Partition $\mathbb{R}^+$ into sets $(m,m+1]$ for $m\in\mathbb{N}$. There are countably many rationals in each interval, so order them in type $\omega$. Now let $\phi(0)$ be the first item in (0,1], $\phi(1)$ the first item in (1,2], $\phi(2)$ the second item in (0,1], $\phi(3)$ the second item in (1,2], $\phi(4)$ the first item in (2,3], etc.. We step up through the intervals, going one higher each run, then back down to (0,1], and start up again. No step is longer than twice an interval. Now we can shrink the intervals as small as we wish.

  • 0
    Nice solution, but the use of countable choice is unnecessary.2010-11-30
  • 0
    Can't I avoid it by constructing explicitly my ordering of the rationals in (m,m+1]? Say by the Farey sequence?2010-11-30
  • 0
    Absolutely. So avoidable!2010-11-30
5

If $\phi$ is a bijection, so is $r \phi$ for any $r \in \mathbb{Q}$, so if the supremum is ever finite then the infimum you ask for is zero. And it's not hard to describe a bijection with bounded step size: number the rationals in $[-1, 1]$ with denominator at most $2$ from left to right, then weave back and number the rationals in $[-2, 1]$ with denominator at most $4$ that you haven't already, then weave back and number the rationals in $[-2, 2]$ with denominator at most $8$ that you haven't already... and so forth. The step size here, I think, is always bounded by $\frac{1}{2}$.