Is the set $\{ (X_n)_{n \in \mathbb{N}} \text{ has a nondecreasing subsequence} \}$ measurable? Given a measurable space $(\Omega, \mathcal{A})$ and $\mathcal{A}/\mathcal{B}(\mathbb{R})$-measurable maps $X_n : \Omega \to \mathbb{R}$, $n \in \mathbb{N}$, is the set
$$
A:= \{\omega \in \Omega | (X_n(\omega))_{n \in \mathbb{N}} \text{ has a nondecreasing subsequence} \}
$$
in $\mathcal{A}$?
My intuitive answer was yes. But I have been struggling to show this. Basically, the problem is that there are uncountably many subsequences.
To clarify: A sequence of real numbers $(a_n)_{n \in \mathbb{N}}$ is nondecreasing if $a_n \leq a_{n+1}$ for all $n \in \mathbb{N}$.
Here are some ways of trying to show the measurability that don't work.


*

*Trying to write $A$ as
$$
B:= \bigcap_{n \in \mathbb{N}}\bigcup_{k \geq n}\bigcup_{l > k}\{X_k \leq X_l\}
$$
doesn't work, because $B$ doesn't have to be in $A$, see the sequence $-1,-1,-2,-2,-3,-3,\dots$

*Defining, for all $k \in \mathbb{N}$, the random variables $T_0^k := k$, and then recursively
$$
T_{j+1}^k := \inf\{n \geq T_j^k|X_n \geq X_{T_j^k}\}
$$
and then considering the set
$$
C:= \bigcup_{k \in \mathbb{N}}\bigcap_{j \in \mathbb{N}}\{T_j^k < \infty\}
$$
doesn't work, because $A$ doesn't have to be in $C$, see the sequence $0,\frac12,0,\frac13,0,\frac14,0,\dots$

*Considering the sets
$$
S_k =  \{(X_n)_{n \in \mathbb{N}} \text{ has a nondecreasing subsequence of length } k \}
$$
and arguing that $A = \bigcap S_k$. In fact the reverse inclusion does not hold as can be seen by the sequence:
$$1,1+1/2,$$
$$0,0+\frac{1}{2}, \; 0+\frac{3}{4},$$
$$-1,-1+\frac{1}{2},-1+\frac{3}{4},-1+\frac{7}{8},$$
$$-2,-2+\frac{1}{2},-2+\frac{3}{4},-2+\frac{7}{8}, -2+\frac{15}{16}, \ldots$$
Update: I still don't know the answer to this question. However, I feel like if $A$ was always measurable, it shouldn't be so difficult to find a proof.
For showing non-measurability, I have tried the following. Let $X_n$ be iid $U([0,1])$ distributed. Now if we assume that $A$ is measurable, then $A$ is also in the terminal $\sigma$-algebra $\mathcal{T}_\infty$ of the $X_n$. Now if we define
$$
B := \{\omega \in \Omega | (X_n(\omega))_{n \in \mathbb{N}} \text{ has a nonincreasing subsequence} \},
$$
then we have $P(A \cup B) = 1$ because every sequence of real numbers has a monotone subsequence, and $P(A) = P(B)$ because the $X_n$ are $U([0,1])$-distributed. This gives us $P(A) > 0$, and thus $P(A) = 1$ because $A \in \mathcal{T}_\infty$. So all you would have to do to find a contradiction is to find a set of strictly positive measure where $(X_n)$ doesn't have a nondecreasing subsequence.
Update: George Lowther has given an extensive answer. To sum up: We can use the lemma in his answer to show that our set $A$ need not be in $\mathcal{A}$, but is always analytic which means in particular that, given any probability measure $P$ on $(\Omega, \mathcal{A})$, we can always assign a meaningful measure to $A$ because $A$ is in the completion of $\mathcal{A}$ w.r.t. $P$. Here is how we use the lemma:


*

*Given any measurable space $(\Omega,\mathcal{A})$ and $A$ as above, the first implication of the lemma directly implies that $A$ is analytic.

*To show that $A$ need not be in $\mathcal{A}$, we construct a counterexample. Let $(\Omega,\mathcal{A}) = (\mathbb{R},\mathcal{B}(\mathbb{R}))$. Then there exists a set $A \subseteq \Omega$ that is analytic but is not in $\mathcal{A}$. Now the second implication of the lemma tells us that we can construct a sequence $(X_n)_{n \in \mathbb{N}}$ of random variables such that
$$
A = \{\omega \in \Omega | (X_n(\omega))_{n \in \mathbb{N}} \text{ has a nondecreasing subsequence} \}.
$$
 A: In general, the set described need not be measurable, but it will always be universally measurable. Universally measurable sets are those subsets of $\Omega$ which lie in the completion of $\mathcal{A}$ with respect to every sigma-finite measure. That is, for a sigma-finite measure $\mu$ on $(\Omega,\mathcal{A})$, let $\mathcal{A}_\mu$ be the completion. This is the sigma-algebra of sets of the form $B\cup C$ where $B\in\mathcal{A}$ and $C$ is contained in a set in $\mathcal{A}$ of zero $\mu$-measure. The universal completion of $\mathcal{A}$ is
$$
\overline{\mathcal{A}}=\bigcap_\mu\mathcal{A}_\mu
$$
where the intersection is over all sigma-finite measures on $(\Omega,\mathcal{A})$. The set $A$ in the question can be shown to be in $\mathcal{A}_\mu$ for each such $\mu$ and, in particular, is in $\overline{\mathcal{A}}$. This means that it has a well-defined measure with respect to any sigma-finite measure $\mu$. However, it need not be in $\mathcal{A}$.
We can exactly classify the possible sets $A$ in terms of analytic sets. There are many equivalent definitions of analytic sets, but I will take the following for now (which makes sense for any sigma-algebra $\mathcal{A}$).

A set $A\subseteq\Omega$ is $\mathcal{A}$-analytic if and only if it is the projection of an $\mathcal{A}\otimes\mathcal{B}(\mathbb{R})$ measurable subset of $\Omega\times\mathbb{R}$ onto $\Omega$. i.e.,
  $$
A = \left\{x\in\Omega\colon(x,y)\in S{\rm\ for\ some\ }y\in\mathbb{R}\right\}
$$
  for some $S\in\mathcal{A}\otimes\mathcal{B}(\mathbb{R}).$

The definition given by Wikipedia is for the case where $\Omega$ is a Polish space and $\mathcal{A}$ its Borel sigma-algebra, but this definition can be applied to any measurable space $(\Omega,\mathcal{A})$. A nice introduction to analytic sets is given in appendix A5 of Stochastic Integration with Jumps by Klaus Bichteler, available free online on his homepage.
Useful well-known properties of analytic sets are the following.


*

*Every $\mathcal{A}$-analytic set is in the universal completion $\overline{\mathcal{A}}$.

*If $\Omega$ is an uncountable Polish space with Borel sigma-algebra $\mathcal{A}$, (for example, $\Omega=\mathbb{R}$, $\mathcal{A}=\mathcal{B}(\mathbb{R})$) then there exists $\mathcal{A}$-analytic sets which are not in $\mathcal{A}$.


The following classifies the sets $A$ in the question in terms of analytic sets.

Lemma: The following are equivalent.
  
  
*
  
*There is a sequence of real-valued random variables $X_n$ on $(\Omega,\mathcal{A})$ such that $$A=\left\{\omega\in\Omega\colon n\mapsto X_n(\omega){\rm\ has\ a\ nondecreasing\ subsequence}\right\}\qquad{\rm(1)}$$
  
*$A$ is $\mathcal{A}$-analytic.
  

Once we have proven this lemma, then the statements above about the measurability of $A$ follow.
To prove that the first statement of the lemma implies the second, consider $A$ given by (1). Define $S\subseteq\Omega\times(0,\infty]$ by
$$
S=\left\{(\omega,x)\colon X_n(\omega){\rm\ has\ a\ nondecreasing\ subsequence\ tending\ to\ }x\right\}.
$$
This can be shown to be in $\mathcal{A}\otimes\mathcal{B}((0,\infty])$ and its projection onto $\Omega$ is $A$. So, $A$ is analytic.
It just remains to prove that the second statement of the lemma implies the first. For this, I will use the alternative definition of an analytic set $A$ as given by the Suslin operation. This can be shown to be equivalent to the definition above. Let $\omega=\{0,1,2,\ldots\}$ denote the natural numbers, $\omega^{\lt\omega}=\bigcup_{n=1}^\infty\omega^n$ denote the nonempty finite sequences in $\omega$, and $\omega^\omega$ denote the infinite sequences in $\omega$. For each $x\in\omega^\omega$ and positive integer $n$, write $x\vert_n\in\omega^{\lt\omega}$ for the initial sequence of length $n$ from $x$,
$$
x\vert_n = (x_0,x_1,\ldots,x_{n-1}).
$$
A Suslin scheme $P$ is a collection of sets $P_x\in\mathcal{A}$ over $x\in\omega^{<\omega}$ and the Suslin operation maps this to
$$
A=\bigcup_{x\in\omega^\omega}\bigcap_{n=1}^\infty P_{x\vert_n}.
$$
Every $\mathcal{A}$-analytic set can be expressed in this form. We can express $A$ as a projection of a reasonably nice subset of $\Omega\times\mathbb{R}$. Start by choosing a collection of intervals $U_x=[a_x,b_x)\subseteq[0,1)$ over $x\in\omega^{\lt\omega}$ satisfying the properties


*

*$\bigcap_{n=1}^\infty U_{x\vert_n}\not=\emptyset$ for all $x\in\omega^\omega$.

*$U_x\cap U_y=\emptyset$ unless $x=z\vert_m$ and $y=z\vert_n$ for some $z\in\omega^\omega$ and positive integers $m,n$.


For example, we can take
$$
a_{x_0,\ldots,x_n}=\sum_{k=0}^n2^{-k-x_0-\ldots-x_{k-1}}(1-2^{-x_k})
$$
and $b_{x_0,\ldots,x_n}=a_{x_0,\ldots,x_n+1}$.
Define $S\subseteq\Omega\times\mathbb{R}$ by
$$
S=\bigcap_{n=1}^\infty\bigcup_{x\in\omega^n}P_x\times U_x.
$$
Then, $A$ is the projection of $S$ onto $\Omega$. Set
$$
S_n=\bigcap_{k=1}^n\bigcup_{x\in\omega^k}P_x\times U_x.
$$
Then, $S_n$ decreases to $S$ and the paths $X_n(\omega,t)=1_{\{(\omega,t)\in S_n\}}$ are right-continuous. The set $A$ is precisely the set of $\omega\in\Omega$ such that the process $\sum_{n=1}^\infty 2^{-n}X_n(\omega,t)$ hits $1$. This relates the question to measurability of hitting times of right-continuous processes as mentioned in my comment to the original question.
For each positive integer $n$, define a sequence $Y_{n,m}$ of random variables over $m=0,1,2,\ldots$ by
\begin{align}
Y_{n,0}(\omega)&=1.\\
Y_{n,m+1}(\omega)&=\sup\{x\in[0,Y_{n,m}(\omega)-1/n]\colon (\{\omega\}\times[x,Y_{n,m}(\omega)])\cap S_n\not=\emptyset\}
\end{align}
Then $m\mapsto Y_{n,m}$ are decreasing sequences of random variables and, using the convention $\sup\emptyset=-\infty$, each sequence is constant at $-\infty$ after a finite number of steps.
It can be seen that a point $(\omega,t)\in S$ if and only if there is a subsequence $Y_{n_k,m_k}(\omega)$ strictly decreasing to $t$.
Finally, let $X_k(\omega)$ be the sequence of random variables $Y_{n,m}(\omega)$ in order of increasing $m$ and then increasing $n$, after each value of $-\infty$
and each repeated value is removed. In case this terminates, we can set $X_k(\omega)=k$ once there are no remaining values left in the sequence. Then, a point $(\omega,t)$ is in $S$ if and only if $X_k(\omega)$ has a subsequence decreasing to $t$, and $A$ is precisely the set of $\omega\in\Omega$ for which $-X_k(\omega)$ has a nondecreasing subsequence.

Finally, I'll point out that although I showed above that there are cases where $A$ is not in $\mathcal{A}$, the construction above would give rather contrived examples. However, the existence of any single counterexample implies that any sufficiently `generic' construction of the space $(\Omega,\mathcal{A})$ will also give $A\not\in\mathcal{A}$.
For example, consider the following standard construction of a space with an infinite sequence of random variables. Let $\Omega=\mathbb{R}^{\mathbb{N}}$ be the space of infinite sequences $\omega=(\omega_1,\omega_2,\ldots)$ of real numbers. Then, for each positive integer $n\in\mathbb{N}$, define $X_n\colon\Omega\to\mathbb{R}$ by $X_n(\omega)=\omega_n$. Finally, let $\mathcal{A}$ be the sigma-algebra generated by the $X_n$. i.e., $\mathcal{A}$ is generated by the sets $X_n^{-1}(S)$ for $n\in\mathbb{N}$ and $S\in\mathcal{B}(\mathbb{R})$. Then,
$$
A = \left\{\omega\in\Omega\colon X_n(\omega){\rm\ has\ a\ nondecreasing\ subsequence}\right\}
$$
is not in $\mathcal{A}$.
To see this, consider any counterexample $(\tilde\Omega,\mathcal{\tilde A})$ with random variables $\tilde X_n\colon\tilde\Omega\to\mathbb{R}$ such that the set $\tilde A$ on which $\tilde X_n$ has a nondecreasing subsequence is not measurable. Define the map $f\colon\tilde\Omega\to\Omega$ by $f(\tilde\omega)=\omega$ where $\omega_n=\tilde X_n(\tilde\omega)$. Then, $f$ is measurable and $\tilde A=f^{-1}(A)$. If $A$ was in $\mathcal{A}$ then this implies that $\tilde A\in\mathcal{\tilde A}$, a contradiction.
A: Some minor observations:  Let $\{a_n\}_{n=1}^{\infty}$ be a real-valued sequence.
Claim 1:
$\{a_n\}_{n=1}^{\infty}$ has no nondecreasing subsequence if and only if the following two properties hold:
(i) $\sup_{n \in \{1, 2, 3,...\}} a_n < \infty$
(ii) For each $x \in \mathbb{R}$ there is an $\epsilon_x>0$ such that $a_n \in [x-\epsilon_x,x]$ for at most finitely many positive integers $n$.
Proof:
($\impliedby$) Suppose $\{a_n\}$ has a nondecreasing subsequence $\{a_{n[k]}\}_{k=1}^{\infty}$ (where $n[k]$ are positive integers that increase with $k$). We show at least one of the two properties are violated.  If $\sup_{n \in \{1, 2, 3, ....\}} a_n = \infty$ we are done.  Assume $\sup_{n \in \{1, 2, 3, ....\}} a_n <\infty$.  Then $\{a_{n[k]}\}_{k=1}^{\infty}$ is upper bounded and nondecreasing, it approaches a finite limit $x \in \mathbb{R}$ from below, which violates property (ii).
($\implies$) Suppose $\{a_n\}$ violates one of the two properties. We show it must have a nondecreasing subsequence. If it violates the first property then $\sup_{n \in \{1, 2, 3, ...\}} a_n = \infty$ and clearly there is a subsequence that increases to $\infty$, so $\{a_n\}$ has a nondecreasing subsequence.
Now suppose the second property is violated. So there must exist an $x \in \mathbb{R}$ such that for every $\epsilon>0$ we have $a_n \in [x-\epsilon, x]$ for an infinite number of positive integers $n$. If there are an infinite number of positive integers $n$ for which $a_n=x$ then this forms a constant subsequence, which is nondecreasing and we are done. Else, for each $\epsilon>0$, we have $a_n \in [x-\epsilon, x)$ for an infinite number of positive integers $n$, and we can easily construct a nondecreasing subsequence (pick $a_{n[1]} \in [x-1, x)$, pick $n[2]>n[1]$ such that $a_{n[2]} \in [a_{n[1]}, x)$, and so on).  $\Box$

Now let $\mathcal{L}$ be the set of all limiting values that can be achieved over infinite subsequences of $\{a_n\}_{n=1}^{\infty}$ (considering all subsequences that have well defined limits, allowing $\infty$ and $-\infty$).  So $\mathcal{L} \subseteq \mathbb{R} \cup \{\infty \} \cup \{-\infty\}$.
Claim 2:
If $\{a_n\}_{n=1}^{\infty}$ has no nondecreasing subsequence, then $\mathcal{L}$ has an at-most countably infinite number of values and $\sup \mathcal{L} < \infty$.  In particular, $\infty \notin \mathcal{L}$.
Proof: Claim 1 implies that $\sup_{n \in \{1, 2, 3, ...\}} a_n < \infty$ and so $\sup \mathcal{L} < \infty$.
Claim 1 implies that for each real-valued $x \in \mathcal{L}$ there is a gap of size $\epsilon_x>0$, so that there are no elements of $\mathcal{L}$ in the interval $(x-\epsilon_x,x)$. It follows that there are an at-most countably infinite number of elements of $\mathcal{L}$ in any finite interval of $\mathbb{R}$ (*see details about summing positive numbers below). Since $\mathbb{R}$ can be represented as a countable union of finite intervals, the result holds. $\Box$

*Details on summing positive numbers: Let $I$ be the finite interval of $\mathbb{R}$ in question, with size $|I|$.  Suppose $\mathcal{L} \cap I$ is uncountably infinite (we reach a contradiction).  Note that $\epsilon_x>0$ for all $x \in \mathcal{L} \cap I$. Let $\mathcal{M}$ be the set $\mathcal{L} \cap I$ with the smallest element removed (if there is no smallest element then let $\mathcal{M} = \mathcal{L} \cap I$). Then $\mathcal{M}$ is uncountably infinite and every point $x \in \mathcal{M}$ has another point in $\mathcal{L} \cap I$ beneath it (so $x-\epsilon_x$ does not fall below the bottom of interval $I$). For any countably infinite subset $\mathcal{A}\subseteq \mathcal{M}$ we know $\sum_{x \in \mathcal{A}} \epsilon_x \leq |I|$, meaning that the sum of the gaps is less than or equal to the interval size. The next lemma shows that, because $\mathcal{M}$ is uncountably infinite, there must exist a countably infinite subset $\mathcal{A}\subseteq\mathcal{M}$ for which $\sum_{x \in \mathcal{A}} \epsilon_x=\infty$, a contradiction.
Lemma:
If $\mathcal{X}$ is an uncountably infinite set and $f:\mathcal{X}\rightarrow\mathbb{R}$ is a function such that $f(x)>0$ for all $x \in \mathcal{X}$, then there exists a countably infinite subset $\mathcal{A}\subseteq \mathcal{X}$ such that $\sum_{x \in \mathcal{A}} f(x) = \infty$.
Proof:
Let $M$ be the supremum of $\sum_{x \in \mathcal{B}} f(x)$ over all finite subsets $\mathcal{B} \subseteq \mathcal{X}$. Then there is a sequence of finite subsets $\{\mathcal{B}_k\}_{k=1}^{\infty}$ with $\mathcal{B}_k \subseteq \mathcal{X}$ for all $k\in \{1, 2, 3, ...\}$ such that
$$ \lim_{k\rightarrow\infty} \sum_{x \in \mathcal{B}_k} f(x) = M $$
Since $f(x)>0$ for all $x \in \mathcal{X}$, for all positive integers $k$ we have
$$\sum_{x \in \cup_{i=1}^{\infty}\mathcal{B}_i} f(x) \geq \sum_{x \in \mathcal{B}_k} f(x) $$
Taking a limit as $k\rightarrow \infty$ gives
$$ \sum_{x \in \cup_{i=1}^{\infty}\mathcal{B}_i}f(x) \geq M$$
If $M=\infty$ it follows that $\cup_{i=1}^{\infty} \mathcal{B}_i$ is a countably infinite set over
which $f(x)$ sums to infinity and we are done.
Now suppose $M<\infty$ (we reach a contradiction). The set $\cup_{k=1}^{\infty} \mathcal{B}_k$ is either finite or countably infinite, so (since $\mathcal{X}$ is uncountably infinite) there is a point $x^* \in \mathcal{X}$ that is not in $\cup_{k=1}^{\infty} \mathcal{B}_k$.  Choose $k$ such that $|\sum_{x \in \mathcal{B}_k} f(x) - M| < f(x^*)/2$. Then $\mathcal{B}_k \cup \{x^*\}$ is a finite set but
$$ \sum_{x \in \mathcal{B}_k \cup \{x^*\}} f(x) > M$$
contradicting the definition of $M$. $\Box$
A: Here is a proof of a (lesser) result that shows the set of all $\omega \in \Omega$ for which $\{X_n(\omega)\}_{n=1}^{\infty}$ contains arbitrarily long finite nondecreasing subsequences is measurable. 
For each $k\in \mathbb{N}$, define $B_k(\omega)\subseteq\mathbb{N}$ as the set of all indices $i \in \mathbb{N}$ 
for which  $\{X_n(\omega)\}_{n=1}^{\infty}$ has a length-$k$ nondecreasing subsequence that starts at index $i$. So $B_k$ is a random set. For example $\{5 \in B_{12}\}$ is the subset of all $\omega \in \Omega$ for which $\{X_n(\omega)\}$ has a length-12 non-decreasing subsequence that starts at index 5.  
Notice that $B_1 = \mathbb{N}$ and so for all positive integers $i$ we have $\{i \in B_1\}= \Omega$, which is measurable. 
Induction: 
Fix $n \in \mathbb{N}$. 
Suppose that for all $i \in \mathbb{N}$ we have $\{i \in B_n\}$ is measurable (it holds for $n=1$).  We show it holds for $n+1$: For each $i \in \mathbb{N}$ we have: 
$$ \{i \in B_{n+1}\} = \cup_{j=i+1}^{\infty}\{ \{X_i\leq X_j\} \cap\{j \in B_n\}\} = \mbox{measurable}$$
$\Box$
Thus the following sets are measurable: 
\begin{align}
&\cup_{i=1}^{\infty} \cap_{n=1}^{\infty} \{i \in B_n\} \\
& \cap_{n=1}^{\infty} \cup_{i=1}^{\infty} \{i \in B_n\} 
\end{align} 
In particular the event that $\{X_n(\omega)\}$ contains arbitrarily long finite-length nondecreasing subsequences  is measurable.
