$\Sigma^1_1$-complete set of natural numbers of non-logical nature

132 Views Asked by At

I am interested in $\Sigma^1_1$-complete reals (i.e., subsets of $\omega$) of non-logical nature. I am more familiar with $\Sigma^1_1$-complete sets of reals that arise in computable structure theory, but I have recently realized that I knew of no reals of similar vein.

  1. A host of reals that are $\Sigma^1_1$-complete appear to come from so-called recurring domino problems. These are variants of the better known tiling problem by Wang: in the recurrent domino problems, you ask whether there is a tiling in which a designated color occurs infinitely many times in the top row. The linked paper studies three variants of the problem, but one could think of more. In fact, in a more recent paper, a variant in which the number of colors is finite and there is a restriction on the tiles is called "the recurrent [sic] domino problem." My question is: is there a good survey of these sets of reals? Often, these were published in old CS conference proceedings, so they are scattered and sometimes very hard to obtain. (In fact, I can't read the article cited in Vardi et al. even though it appears to contain a stronger result.)

  2. More generally, I am interested in $\Sigma^1_1$-complete reals of non-logical nature. Is there a survey of such reals? The recurring domino problems are combinatorial, but I would not be surprised if people have looked at $\Sigma^1_1$-complete reals arising from, say, finite group theory.