부산대학교 도서관

This paper deals with generalized descriptive set theory [S.-D. Friedman, T. Hyttinen and V. Kulikov, Mem. Amer. Math. Soc. {\bf 230} (2014), no.~1081, vi+80 pp.; MR3235820]. The spaces $\kappa^\kappa$ and $2^\kappa$ are equipped with the bounded topology where the basic open sets are of the form $\{\eta\in\kappa^\kappa:\eta\supset p\}$ for $p\in\kappa^{<\kappa}$. The Borel sets are generated from the basic open sets by complements and intersections of size $\kappa$. The $\Sigma^1_1$ sets are projections of Borel subsets of $(\kappa^\kappa)^2$. For every regular $\mu<\kappa$ and for $\lambda=2$ and ${\lambda=\kappa}$ denote ${E^\lambda_\mu=\{(\eta,\xi)\in(\lambda^\kappa)^2: \{\alpha<\kappa:\eta(\alpha)=\xi(\alpha)\}}$ contains $\mu$-{\rm club}$\}$. If $V=L$, then the equivalence relation $E^\kappa_\mu$ is $\Sigma^1_1$-complete, i.e., every $\Sigma^1_1$-equivalence relation is Borel reducible to $E^\kappa_\mu$. The question whether the relation $E^2_\mu$ is $\Sigma^1_1$-complete was open. In the paper under review, the authors answer this question in the positive. Actually the answer is a quite simple consequence of the following result: If $V=L$, then the inclusion modulo the non@-stationary ideal ($\sqsubseteq^{\rm NS}$) is a $\Sigma^1_1$-complete quasi-order, i.e., every $\Sigma^1_1$@-partial quasi@-order is Borel reducible to $\sqsubseteq^{\rm NS}$. This $\Sigma^1_1$-completeness result for partial quasi@-orders has a number of consequences including the main result of the paper: Under ${V=L}$, if the isomorphism relation of a countable first-order theory (not necessarily complete) is not $\Delta^1_1$, then it is $\Sigma^1_1$-complete. A number of results are partial or complete answers to several open problems stated in the literature. For example, the embeddability of dense linear orders $\sqsubseteq_{\rm DLO}$ and the embeddability of graphs $\sqsubseteq_{\rm G}$ are $\Sigma^1_1$-complete in $L$. The authors also study the case $V\ne L$ and prove $\Sigma^1_1$-completeness results for weakly ineffable and weakly compact cardinals.