Sequences with increasing subsequence (Q6611780)

Let \(X\) be a countable set and \(R\) be a binary relation on \(X\). Define \(L_{(X,R)}=\{y\in X^\omega: (\exists k_0<k_1<\dots)(\forall i\in\omega)\) \((y_{k_i}\mathrel{R}y_{k_{i+1}})\}\). Every set \(L_{(X,R)}\) is an analytic subset of \(X^\omega\). It is a Luzin theorem that for a division relation \(\mid\) on \(\mathbb{N}\) the set \(L_{(\mathbb{N},{\mid})}\) is a \(\boldsymbol\Sigma^1_1\)-complete set. In the paper under the review the authors study complexity of these sets for various relations \((X,R)\). They provide several examples of such sets that are Borel and they prove that if \((X,{\leq_X})\) and \((Y,{\leq_Y})\) are countable posets and \(\varphi:X\to Y\) is a mapping such that for every \((x_n)_{n\in\omega}\in X^\omega\), \((x_n)_{n\in\omega}\) contains a \(\leq_X\)-increasing sequence if and only if \((\varphi(x_n))_{n\in\omega}\) contains a \(\leq_Y\)-increasing sequence, then \(L_{(Y,{\leq_Y})}\) is \(\boldsymbol\Sigma^1_1\)-complete whenever \(L_{(X,{\leq_X})}\) is \(\boldsymbol\Sigma^1_1\)-complete. This helps to show that several sets of this form are \(\boldsymbol\Sigma^1_1\)-complete as they are reductions of classical results. The authors prove that for linear orders \((X,{\leq})\), the set \(L_{(X,{\leq})}\) is \(\boldsymbol\Sigma^1_1\)-complete if and only if there is an infinite set \(Y\subseteq X\) such that \((Y,{\leq}{\restriction}Y)\) is a dense order.