On ${\Sigma }_1^1$-completeness of quasi-orders on ${\kappa }^{\kappa }$

Abstract

We prove under $V=L$ that the inclusion modulo the non-stationary ideal is a ${\Sigma }_1^1$-complete quasi-order in the generalized Borel-reducibility hierarchy ($\kappa >\omega$). This improvement to known results in $L$ has many new consequences concerning the ${\Sigma }_1^1$-completeness of quasi-orders and equivalence relations such as the embeddability of dense linear orders as well as the equivalence modulo various versions of the non-stationary ideal. This serves as a partial or complete answer to several open problems stated in literature. Additionally the theorem is applied to prove a dichotomy in $L$: If the isomorphism of a countable first-order theory (not necessarily complete) is not ${\Delta }_1^1$, then it is ${\Sigma }_1^1$-complete. We also study the case $V\ne L$ and prove ${\Sigma }_1^1$-completeness results for weakly ineffable and weakly compact $\kappa$.