Are there any studies on a sorting function on real line?

216 Views Asked by At

Let assume we have an integer array $[3,4,1,0,7]$, we can sort it into $[0,1,3,4,7]$.

There is a sorting function $S: \mathbb{N}^k \to \mathbb{N}^k$ that sort the integer in the array defined as above.

If we see an integer array as a function that maps an index set $\mathcal{I} \to \mathbb{N}$, I want to generalize it to the case that $\mathbb{N}$ is replaced by $[0,1]$ of a real line.

In this continuum case, are there any studies on the analog to the sorting function $S$ but on real line in the sense that it "sorts" a real-valued function $f(x)$ defined on $[0,1]$?

i.e. a function $S': F[0,1] \to M[0,1]$, where:

$\mathcal{F}[0,1]$ are all function from $[0,1] \to [0,1]$,

$\mathcal{M}[0,1]$ are all monotonic increasing (non-decreasing) function from $[0,1] \to [0,1]$.

that somehow preserves the values of $f(x)$. I am not sure how to define what it preserves precisely now (I guess should be related to derivative), just a weird idea.

EDIT followed by David C. Ullrich's answer

What if we restrict $\mathcal{F}[0,1]$ to be some kind of "nice" function, such as differentiable almost everywhere on $[0,1]$?

1

There are 1 best solutions below

8
On BEST ANSWER

Well first we need to define what it means to "sort" a function $f:[0,1]\to\Bbb R$. Given what seems like the natural definition (below) there are functions that cannot be sorted.

Definition Suppose that $f:[0,1]\to\Bbb R$. To sort $f$ is to find a bijection $\phi:[0,1]\to[0,1]$ such that $g=f\circ\phi$ is nondecreasing.

Let $f$ be the characteristic function of the irrationals in $[0,1]$. Or if you want an injective example, to clarify that breaking ties is not the issue, define $$f(t)=\begin{cases}t,&(t\in[0,1]\cap\Bbb Q), \\2+t,&(t\in[0,1]\setminus\Bbb Q).\end{cases}$$

Then $f$ cannot be sorted. Because if you could sort $f$ then $[0,1]=A\cup B$ where $A$ is countably infinite and every element of $A$ is less than evey element of $B$; this is impossible, since every infinite initial segment of $[0,1]$ is uncountable.

Edit: Smoothness doesn't help. Simpler example than the above, also smooth: Let $f(t)=\sin(\pi t)$. If $\phi$ is a bijection and $g=f\circ \phi$ then $g^{-1}(1/2)$ contains exactly two points, but if $g$ is monotone then $g^{-1}(a)$ is either a singleton or infinite.