14
$\begingroup$

Let $S$ be the set of injective sequences in $\mathbb{R}$: $$S = \{s: \mathbb{N} \rightarrow \mathbb{R}: s(m) \neq s(n) \text{ if }m \neq n\}.$$ Consider $S$ with the topology of pointwise convergence, and $C(S,S)$ the associated continuous functions on $S$. For any sequence $s$ in $S$, let $\text{ran}(s)$ be the corresponding set of reals.

Is there $f \in C(S,S)$ such that $\text{ran}(f(s))$ is always dense in $\mathbb{R}$ and disjoint from $\text{ran}(s)$?

Without continuity, this would be as simple as listing the intervals with rational endpoints, and choosing one point in each interval minus $\text{ran}(s)$. With continuity, I don't know.

Background: I'd like to show that for any sequence of reals, we can find a dense sequence avoiding it, constructively and without using countable choice. I'd be happy to see an answer on that too. I think the question above, phrased without constructvity, gets at much the same issue.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Simpler: do you know a way to map $s$ to an element $u(s)$ not in the range of $s$, in a "constructive" way (e.g., $u$ continuous, or even $u$ Borel)? it eventually seems to be equivalent to the problem, at least in its Borel/"constructive" version. $\endgroup$
    – YCor
    Commented Dec 14, 2016 at 21:47
  • $\begingroup$ Why are you looking only at the injective sequences? $\endgroup$
    – Andrej Bauer
    Commented Dec 14, 2016 at 21:55
  • $\begingroup$ You may also be interested in this related question: mathoverflow.net/a/47191/1946, concerning the impossibility of diagonalizing against countable sets of reals in a Borel way. $\endgroup$
    – Joel David Hamkins
    Commented Dec 14, 2016 at 22:11
  • 1
    $\begingroup$ @AndrejBauer, if you look at S', the set of all sequences, then it's clearly impossible. Define L_i = {s: f(s)(1) < s(i)} and R_i = {s: f(s)(1) > s(i)}, which are open sets with S' as the union of L_i and R_i. So either L_i = S' or R_i = S'. It is impossible to have L_i = S' and R_j = S', since sometimes s(i) < s(j). So either for all i, L_i = S', making f(s)(1) impossibly small; or for all i, R_i = S', making f(s)(1) impossibly large. (Credit here to an answer now deleted, and maybe there's a better way of writing this down that conveys the imagery of squeezing better.) $\endgroup$
    – user44143
    Commented Dec 14, 2016 at 23:06
  • $\begingroup$ By "topology of point-wise convergence", do you mean the topology induced on $S$ by the product topology of $\mathbb{R}^\mathbb{N}$? $\endgroup$
    – Pietro Majer
    Commented Dec 15, 2016 at 7:31

2 Answers 2

Reset to default
6
$\begingroup$

I think there is not such an $f:S\to S$. Consider the sequence $x^t\in S$ continuously depending on $t\in[0,1]$, such that $x_0^t=-t$ and $x_n^t=1/n $ for all $n\ge1$. Since $f(x^1)$ is dense, for some index, say $17$, we have $-1 <f_{17}(x^1)<0$. Therefore, for $t=1$, we have $$-t=x^t_0<f_{17}(x^t)<x^t_n=1/n$$ for all $n\ge1$. By continuity this must hold for all $0\le t\le1$, but it is impossible for $t=0$.

Improve this answer
$\endgroup$
4
$\begingroup$

If you replace the reals $\mathbb{R}$ with Cantor space $2^{\mathbb{N}}$ or with Baire space $\mathbb{N}^{\mathbb{N}}$ (homeomorphic to the space of irrationals), then the answer is yes. Indeed, one can have the function defined on the whole space of sequences, not just the injective ones.

To see this, define $f(x_0,x_1,...)=(y_0,y_1,...)$, where $y_k$ extends the $k^{th}$ finite sequence $u_k$, and diagonalizes the $x_n's$ in a canonical way beyond the length of $u_k$, so that the $|u_k|+j^{th}$ digit of $y_k$ is different from the $|u_k|+j^{th}$ digit of $x_j$. This is a continuous function, since any finitely many digits for the output are determined by finitely many digits of the input. The $y_k$'s are not among the $x_n$, since they diagonalize against this list, and the $y_k$'s are dense, because $y_k$ extends $u_k$. (By changing the diagonalization procedure slightly, it is easy to arrange that the $y_k$ are all distinct.)

Improve this answer
$\endgroup$
6
  • $\begingroup$ But for reals and the whole space of sequences the answer is known (see my deleted comment, in which I forgot that we consider only injective sequences). $\endgroup$
    – Fedor Petrov
    Commented Dec 15, 2016 at 6:17
  • $\begingroup$ @FedorPetrov, he means that we can do it for the whole space of irrational sequences. It's a notably tweaked setup but an elegant solution to it. $\endgroup$
    – user44143
    Commented Dec 15, 2016 at 6:21
  • $\begingroup$ But $ran(f(s))$ are supposed to be dense. It seems that there is still some work to do. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Dec 15, 2016 at 6:47
  • 2
    $\begingroup$ @WłodzimierzHolsztyński The range of $f(s)$ is dense, since $y_k$ was chosen specifically to extend $u_k$, and so we've gotten into every basic open set. Fedor, my point is that if we use Cantor space or Baire space, then the answer is positive, even for the whole space of sequences; there is no need to restrict to the injective sequences. The main point is that Cantor diagonalization is a continuous process on these spaces. $\endgroup$
    – Joel David Hamkins
    Commented Dec 15, 2016 at 12:12
  • $\begingroup$ So for the reals, it follows that there is a Borel way of proceeding. $\endgroup$
    – YCor
    Commented Dec 16, 2016 at 0:57

You must log in to answer this question.