Let


* $(\Omega,\mathcal A,\operatorname P)$ be a probability space
* $(E,\mathcal E)$ be a measurable space
* $n\in\mathbb N$
* $X\_1,\ldots,X\_n$ be $(E,\mathcal E)$-valued random variables on $(\Omega,\mathcal A,\operatorname P)$



> 
> I'm interested in the following question: Given a total$^1$ order $\le$ on $E$, I want to construct $(E,\mathcal E)$-valued random variables $X\_{1:n},\ldots,X\_{n:n}$ on $(\Omega,\mathcal A,\operatorname P)$ such that $X\_{k:n}$ is the $k$th smallest element among $X\_1,\ldots,X\_n$ (where $X\_i$ is considered as smaller than $X\_j$ whenever $X\_i=X\_j$ and $i<j$).
> 
> 
> 


I would like to define them by something like $X\_{1:n}:=\min\left\{X\_1,\ldots,X\_n\right\}$ and $$X\_{i:n}:=\min\left\{X\_j:X\_j>X\_{i-1:n}\right\}\;\;\;\text{for }j\in\left\{2,\ldots,n\right\}\tag1,$$ but this won't be well-defined if not all $X\_i$ are distinct and it won't be measurable in general. Equivalently, we may ask if there is a random permutation $\pi:\Omega\times\left\{1,\ldots,n\right\}\to\left\{1,\ldots,n\right\}$ such that $X\_{\pi(1)}\le\cdots\le X\_{\pi(n)}$ and each $X\_{\pi(k)}$ is measurable.


The examples I've got in mind include $E=\mathbb R$ with the usual order or $E=\mathbb R^d$ and the order given by the smallest distance to a fixed element $x\in\mathbb R^d$.



> 
> Which conditions on the relation between $\mathcal E$ and $\le$ do we need to impose and how do we actually need to define $X\_{k:n}$ (or $\pi$)?
> 
> 
> 




---


$^1$ I've strengthen the assumption from "partial" order to total order, since at least the examples I've described are total orders. Actually, I think we need a total order, since otherwise we cannot use the fact that a finite set has a unique minimum. Please correct me if I'm wrong (I'm not familiar with general order theory) and feel free to weaken the assumption again, if your answer doesn't need the stronger assumption.



Can we order random variables in a measurable way in a general setup?
$\newcommand{\om}{\omega}
\newcommand{\Om}{\Omega}
\newcommand{\eq}{\,\overset\om\sim\,}
\newcommand{\eqq}{\overset{\,\colon\om}\sim\,}
\renewcommand{\eq}{\,\sim\_\om\,}
\newcommand{\K}{\mathcal K}
$
If $E$ is a [distributive lattice](https://en.wikipedia.org/wiki/Distributive_lattice)  with measurable binary operations $E\times E\ni(x,y)\mapsto x\wedge y\in E$ and $E\times E\ni(x,y)\mapsto x\vee y\in E$, then the "order statistics'' $X\_{n:j}$ can be defined by the formula 
\begin{equation}\label{eq:wedge-vee}
 X\_{n:j}(\om):=\bigwedge\Big\{\bigvee\_{i\in J}X\_i(\om)\colon J\in\binom{[n]}j\Big\} 
=\bigvee\Big\{\bigwedge\_{i\in J}X\_i(\om)\colon J\in\binom{[n]}{n+1-j}\Big\}
\end{equation}
for $j\in[n]:=\{1,\dots,n\}$ and $\om\in\Om$, with $\binom{[n]}j$ denoting the set of all subsets $J$ of the set $[n]$ such that the cardinality of $J$ is $j$; cf. [formulas (1.2)--(1.4)](https://arxiv.org/abs/1902.05520v1). 


As explained in that paper in the paragraph right after (1.4), if $E$ is not a distributive lattice, then the two dual to each other natural expressions for $X\_{n:j}$ in the above display may differ from each other, and thus no reasonable definition of $X\_{n:j}$ will seem possible. 




---


I did not define a permulation $\pi$ in the above answer, which was given for your initial post with only a partial order, and in that general case such a permutation will not exist in general. However, after you added the total order assumption, a measurable random permutation $\pi$ that you want does exist and can be formally described as follows. 


For each $\om\in\Om$, define the equivalence relations $\eq$ over the set $[n]$ by the formula
\begin{equation}
 k\eq l\iff X\_{n:k}(\om)=X\_{n:l}(\om) 
\end{equation}
for $k,l$ in $[n]$. 
Let then $\K(\om)$ be the set of all $\eq$-equivalence classes. For each $\om\in\Om$ and each $K\in\K(\om)$, let 
\begin{equation}
 I\_K(\om):=\{i\in[n]\colon X\_i(\om)=X\_{n:k}(\om)\ \forall k\in K\}
 =\{i\in[n]\colon\exists k\in K\ X\_i(\om)=X\_{n:k}(\om)\}, 
\end{equation}
so that the cardinality of the set $I\_K(\om)$ equals that of $K$, 
and then define the bijection $\rho\_K(\om)\colon K\to I\_K(\om)$ by the formula  

\begin{equation}
 K\ni k\mapsto\rho\_K(\om)(k)
 :=\bigwedge\Big\{\bigvee\_{i\in J}i\colon J\in\binom{I\_K(\om)}{k-m\_K+1}\Big\}\in I\_K(\om), 
\end{equation}
where $m\_K:=\min K$. 
Finally, let 
\begin{equation}
 \pi(\om)(k):=\rho\_K(\om)(k)\quad\text{if}\quad k\in K\in\K(\om). 
\end{equation}
Then $\pi\colon\Om\to S\_n$ (where $S\_n$ is the set of all permutations of the set $[n]$) is a random permutation, which is measurable, because it is defined by composing the measurable random maps $X\_{n:k}$ and $X\_i$ with other measurable maps. We also have 
\begin{equation}
 X\_{n:k}(\om)=X\_{\pi(\om)(k)}(\om) 
\end{equation}
for all $k\in[n]$ and all $\om\in\Om$. 
Finally, for all $j,k$ in $[n]$ and all $\om\in\Om$ we have the implication 
\begin{equation}
 (X\_{n:j}(\om)=X\_{n:k}(\om)\ \&\ j<k)\implies\pi(\om)(j)<\pi(\om)(k), 
\end{equation}
as desired. 




---


To illustrate the above description/construction of $\pi$, suppose that $n=6$ and $\om\in\Om$ is such that 
\begin{equation}
 (X\_i(\om))\_1^6=baacba:=(b,a,a,c,b,a) 
\end{equation}
for some $a,b,c$ in $E$ such that $a<b<c$. Then 
\begin{equation}
 (X\_{n:k}(\om))\_1^6=aaabbc, 
\end{equation}
\begin{equation}
 \K(\om)=\{\{1,2,3\},\{4,5\},\{6\}\}, 
\end{equation}
\begin{equation}
 I\_{\{1,2,3\}}(\om)=\{2,3,6\},\ I\_{\{4,5\}}(\om)=\{1,5\},\ I\_{\{6\}}(\om)=\{4\},\ 
\end{equation}
$\rho\_{\{1,2,3\}}(\om)=(236)$ (meaning 
\begin{equation}
 \rho\_{\{1,2,3\}}(\om)(1)=2, \rho\_{\{1,2,3\}}(\om)(2)=3, \rho\_{\{1,2,3\}}(\om)(3)=6), 
\end{equation}
\begin{equation}
 \rho\_{\{4,5\}}(\om)=(15),\quad \rho\_{\{6\}}(\om)=(4), 
\end{equation}
and 
\begin{equation}
 \pi(\om)=(236154), 
\end{equation}
meaning
\begin{equation}
 (\pi(\om)(1),\dots,\pi(\om)(6))=(2,3,6,1,5,4). 
\end{equation}


