# How to show that a problem is in $\Pi_1^1$?

I am trying to show that a decision problem is in $$\Pi_1^1$$. Because of this, I am looking for:

1. Papers or books that present a complete and well-explained proof where a problem is shown to be in $$\Pi_1^1$$.
2. Well-known problems that are in $$\Pi_1^1$$.

Any suggestions?

I think that a good well-studied problem may be the "recurrent tiling problem". For more references (with many use cases) consult the paper "Recurring Dominoes: Making the Highly Undecidable Highly Understandable" by David Harel [Sec. 2.1, 1].

• A quite readable paper on tilings is also “The convenience of tilings” by Peter van Emde Boas Commented Oct 20, 2023 at 20:16
• Thanks guys for the comments! At the end we were able to use some of the problems presented by Harel to reduce to and from : ) Commented Feb 8 at 11:08

The standard example of a $$\Pi^1_1$$ complete decision problem is the following:

Is $$e$$ an index for a Turing machine which (halts on all inputs and) computes a well-ordering of $$\mathbb{N}$$?

Let's write "$$\mathcal{W}$$" for the set of such $$e$$s.

Here, a well-ordering of $$\mathbb{N}$$ is a binary relation on $$\mathbb{N}$$ which is a linear order with the additional property that every (nonempty) subset has a least element. One inessential (but technically useful) variant of this is Kleene's $$\mathcal{O}$$, which basically focuses on "nicely presented" relations. Re: my parenthetical, detecting whether a Turing machine halts on all inputs is merely $$\Pi^0_2$$, so galactically weaker than what we're interested in.

It's a standard result (and a fun exercise to show) that $$\mathcal{W}$$ is $$\Pi^1_1$$ complete; that is, a decision problem is $$\Pi^1_1$$ iff it can be (computably many-one) reduced to $$\mathcal{W}$$. So $$\mathcal{W}$$ serves as a template for testing $$\Pi^1_1$$-ness analogously to the role that the halting problem serves for $$\Sigma^0_1$$-ness or (replacing "computably" with "polynomial-time-computably") that $$\mathsf{SAT}$$ serves for $$\mathsf{NP}$$-ness.

The basic idea behind proving that $$\mathcal{W}$$ (or $$\mathcal{O}$$) is $$\Pi^1_1$$ hard (this is the nontrivial part of $$\Pi^1_1$$ completeness in these cases) is as follows: given an arbitrary $$\Sigma^1_1$$ definition $$\varphi$$ and a number $$n$$, we build a tree $$T_{n,\varphi}$$ whose nodes represent "apparent counterexamples" to $$\varphi(n)$$ holding. An infinite path through $$T_{n,\varphi}$$ corresponds to a genuine counterexample to $$\varphi(n)$$, so we've reduced checking whether $$\varphi(n)$$ holds to checking whether $$T_{n,\varphi}$$ is well-founded. This isn't quite the same as "well-ordered," but now we use the Kleene-Brouwer construction to reduce well-foundedness to well-orderedness.

A nice general treatment of $$\Pi^1_1$$ complete sets and their properties - but focusing on the more technical $$\mathcal{O}$$ rather than $$\mathcal{W}$$ - can be found in the first section of Sacks' book Higher recursion theory.

EDIT: This next bit is really more set theory than complexity theory, but I think it's still worth mentioning:

One key bit of intuition (due to Kreisel if I have my history right) is that despite appearances $$\Pi_1^1$$ is the analogue of computably enumerable (c.e.) rather than co-c.e. Even more confusingly, $$\Delta^1_1$$ is the analogue of finite rather than computable. (For an example of the latter point, the $$\Pi^1_1$$ image of a $$\Delta^1_1$$ set is $$\Delta^1_1$$ again.)

This is explained via $$\omega_1^{CK}$$-recursion theory - the special case of $$\alpha$$-recursion theory with $$\alpha=\omega_1^{CK}$$ - as follows (with "$$L_\alpha$$" denoting the $$\alpha$$th level of Godel's constructible universe):

• Classically, shifting from the natural numbers to the hereditarily finite sets we have "finite" = "element of $$L_\omega$$," and "c.e." = "$$\Sigma_1(L_\omega)$$."

• The generalization to $$\omega_1^{CK}$$ is then "$$\omega_1^{CK}$$-finite" = "element of $$L_{\omega_1^{CK}}$$" and "$$\omega_1^{CK}$$-c.e." = "$$\Sigma_1(L_{\omega_1^{CK}})$$."

Note that $$\omega$$ (or $$\mathbb{N}$$ if you prefer) is $$\omega_1^{CK}$$-finite. It's not hard to show that $$X\subseteq\omega$$ is $$\Pi^1_1$$ in the usual sense iff it is $$\Sigma_1(L_{\omega_1^{CK}})$$. Conversely, though, we lose a crucial bit of combinatorics in passing to $$\omega_1^{CK}$$: a c.e. subset of a finite set is not finite but merely "subfinite." However, a computable subset of a finite set is finite. This corresponds to the fact that the theory $$\mathsf{KP}$$ (= basically the amount of set theory that $$L_{\omega_1^{CK}}$$ satisfies) entails $$\Delta_1$$ comprehension but not $$\Sigma_1$$ comprehension.

Why on earth am I saying all this? Well, in my opinion a lot of the properties of $$\Pi^1_1$$ sets become much simpler when thought of in terms of $$\omega_1^{CK}$$-recursion theory. If set theory puts you off, you may find "metarecursion theory" - basically $$\omega_1^{CK}$$-recursion theory but over (paths through) Kleene's $$\mathcal{O}$$ instead of $$L_{\omega_1^{CK}}$$ as such - to be a useful rephrasing; again assuming my history is right, this was how things were originally phrased by Kreisel and Sacks before the simplifying power of the shift to $$\alpha$$-recursion theory was fully understood.

• Out of curiosity, why the downvote? Commented Oct 30, 2023 at 19:11
• Thank you for your detailed reply! : ) Commented Feb 8 at 11:09