<p>I think that a good well-studied problem may be the &quot;recurrent tiling problem&quot;. For more references (with many use cases) consult the paper &quot;Recurring Dominoes: Making the Highly Undecidable Highly Understandable&quot; by David Harel [Sec. 2.1, 1].</p>
<p>[1] <a href="https://www.wisdom.weizmann.ac.il/%7Edharel/SCANNED.PAPERS/RucurringDominoes.pdf" rel="noreferrer">https://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/RucurringDominoes.pdf</a></p>

CC BY-SA 4.0
2023-10-20T20:16:16.337Z
A quite readable paper on tilings is also “The convenience of tilings” by Peter van Emde Boas
Nicola Gigante
CC BY-SA 4.0
2024-02-08T11:08:50.293Z
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 : )
David Carral
CC BY-SA 4.0
2023-10-20T16:25:18.627Z
2023-10-20T16:25:18.627Z
Bartosz Bednarczyk
<p>The standard example of a <span class="math-container">$\Pi^1_1$</span> complete decision problem is the following:</p>
<blockquote>
<p>Is <span class="math-container">$e$</span> an index for a Turing machine which (halts on all inputs and) computes a <strong>well-ordering</strong> of <span class="math-container">$\mathbb{N}$</span>?</p>
</blockquote>
<p>Let's write &quot;<span class="math-container">$\mathcal{W}$</span>&quot; for the set of such <span class="math-container">$e$</span>s.</p>
<p>Here, a well-ordering of <span class="math-container">$\mathbb{N}$</span> is a binary relation on <span class="math-container">$\mathbb{N}$</span> 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 <a href="https://en.wikipedia.org/wiki/Kleene%27s_O" rel="noreferrer">Kleene's <span class="math-container">$\mathcal{O}$</span></a>, which basically focuses on &quot;nicely presented&quot; relations. Re: my parenthetical, detecting whether a Turing machine halts on all inputs is merely <span class="math-container">$\Pi^0_2$</span>, so galactically weaker than what we're interested in.</p>
<p>It's a standard result (and a fun exercise to show) that <span class="math-container">$\mathcal{W}$</span> is <span class="math-container">$\Pi^1_1$</span> complete; that is, a decision problem is <span class="math-container">$\Pi^1_1$</span> iff it can be (computably many-one) reduced to <span class="math-container">$\mathcal{W}$</span>. So <span class="math-container">$\mathcal{W}$</span> serves as a template for testing <span class="math-container">$\Pi^1_1$</span>-ness analogously to the role that the halting problem serves for <span class="math-container">$\Sigma^0_1$</span>-ness or (replacing &quot;computably&quot; with &quot;polynomial-time-computably&quot;) that <span class="math-container">$\mathsf{SAT}$</span> serves for <span class="math-container">$\mathsf{NP}$</span>-ness.</p>
<p>The basic idea behind proving that <span class="math-container">$\mathcal{W}$</span> (or <span class="math-container">$\mathcal{O}$</span>) is <span class="math-container">$\Pi^1_1$</span> hard (this is the nontrivial part of <span class="math-container">$\Pi^1_1$</span> completeness in these cases) is as follows: given an arbitrary <span class="math-container">$\Sigma^1_1$</span> definition <span class="math-container">$\varphi$</span> and a number <span class="math-container">$n$</span>, we build a tree <span class="math-container">$T_{n,\varphi}$</span> whose nodes represent &quot;apparent counterexamples&quot; to <span class="math-container">$\varphi(n)$</span> holding. An infinite path through <span class="math-container">$T_{n,\varphi}$</span> corresponds to a genuine counterexample to <span class="math-container">$\varphi(n)$</span>, so we've reduced checking whether <span class="math-container">$\varphi(n)$</span> holds to checking whether <span class="math-container">$T_{n,\varphi}$</span> is well-founded. This isn't quite the same as &quot;well-<em>ordered</em>,&quot; but now we use <a href="https://en.wikipedia.org/wiki/Kleene%E2%80%93Brouwer_order" rel="noreferrer">the Kleene-Brouwer construction</a> to reduce well-foundedness to well-orderedness.</p>
<p>A nice general treatment of <span class="math-container">$\Pi^1_1$</span> complete sets and their properties - but focusing on the more technical <span class="math-container">$\mathcal{O}$</span> rather than <span class="math-container">$\mathcal{W}$</span> - can be found in the first section of Sacks' book <a href="https://projecteuclid.org/ebooks/perspectives-in-logic/Higher-Recursion-Theory/toc/pl/1235422631" rel="noreferrer"><em>Higher recursion theory</em></a>.</p>
<hr />
<p>EDIT: This next bit is really more set theory than complexity theory, but I think it's still worth mentioning:</p>
<p>One key bit of intuition (due to Kreisel if I have my history right) is that despite appearances <span class="math-container">$\Pi_1^1$</span> is the analogue of <strong>computably enumerable</strong> (c.e.) rather than co-c.e. Even more confusingly, <span class="math-container">$\Delta^1_1$</span> is the analogue of <strong>finite</strong> rather than computable. (For an example of the latter point, the <span class="math-container">$\Pi^1_1$</span> image of a <span class="math-container">$\Delta^1_1$</span> set is <span class="math-container">$\Delta^1_1$</span> again.)</p>
<p>This is explained via <span class="math-container">$\omega_1^{CK}$</span>-recursion theory - the special case of <span class="math-container">$\alpha$</span>-recursion theory with <span class="math-container">$\alpha=\omega_1^{CK}$</span> - as follows (with &quot;<span class="math-container">$L_\alpha$</span>&quot; denoting the <span class="math-container">$\alpha$</span>th level of <a href="https://en.wikipedia.org/wiki/Constructible_universe" rel="noreferrer">Godel's constructible universe</a>):</p>
<ul>
<li><p>Classically, shifting from the natural numbers to the hereditarily finite sets we have &quot;finite&quot; = &quot;element of <span class="math-container">$L_\omega$</span>,&quot; and &quot;c.e.&quot; = &quot;<span class="math-container">$\Sigma_1(L_\omega)$</span>.&quot;</p>
</li>
<li><p>The generalization to <span class="math-container">$\omega_1^{CK}$</span> is then &quot;<span class="math-container">$\omega_1^{CK}$</span>-finite&quot; = &quot;element of <span class="math-container">$L_{\omega_1^{CK}}$</span>&quot; and &quot;<span class="math-container">$\omega_1^{CK}$</span>-c.e.&quot; = &quot;<span class="math-container">$\Sigma_1(L_{\omega_1^{CK}})$</span>.&quot;</p>
</li>
</ul>
<p>Note that <span class="math-container">$\omega$</span> (or <span class="math-container">$\mathbb{N}$</span> if you prefer) is <span class="math-container">$\omega_1^{CK}$</span>-finite. It's not hard to show that <span class="math-container">$X\subseteq\omega$</span> is <span class="math-container">$\Pi^1_1$</span> in the usual sense iff it is <span class="math-container">$\Sigma_1(L_{\omega_1^{CK}})$</span>. Conversely, though, we lose a crucial bit of combinatorics in passing to <span class="math-container">$\omega_1^{CK}$</span>: a c.e. subset of a finite set is <strong>not</strong> finite but merely &quot;subfinite.&quot; However, a computable subset of a finite set <strong>is</strong> finite. This corresponds to the fact that the theory <span class="math-container">$\mathsf{KP}$</span> (= basically the amount of set theory that <span class="math-container">$L_{\omega_1^{CK}}$</span> satisfies) entails <span class="math-container">$\Delta_1$</span> comprehension but not <span class="math-container">$\Sigma_1$</span> comprehension.</p>
<p>Why on earth am I saying all this? Well, <strong>in my opinion a lot of the properties of <span class="math-container">$\Pi^1_1$</span> sets become much simpler when thought of in terms of <span class="math-container">$\omega_1^{CK}$</span>-recursion theory</strong>. If set theory puts you off, you may find &quot;metarecursion theory&quot; - basically <span class="math-container">$\omega_1^{CK}$</span>-recursion theory but over (paths through) Kleene's <span class="math-container">$\mathcal{O}$</span> instead of <span class="math-container">$L_{\omega_1^{CK}}$</span> 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 <span class="math-container">$\alpha$</span>-recursion theory was fully understood.</p>

CC BY-SA 4.0
2023-10-30T19:11:44.063Z
Out of curiosity, why the downvote?
Noah Schweber
CC BY-SA 4.0
2024-02-08T11:09:32.847Z
Thank you for your detailed reply! : )
David Carral
CC BY-SA 4.0
2023-10-20T16:59:02.437Z
2023-10-21T20:45:42.070Z
2023-10-21T20:45:42.070Z
Noah Schweber
<p>I am trying to show that a decision problem is in <span class="math-container">$\Pi_1^1$</span>.
Because of this, I am looking for:</p>
<ol>
<li>Papers or books that present a complete and well-explained proof where a problem is shown to be in <span class="math-container">$\Pi_1^1$</span>.</li>
<li>Well-known problems that are in <span class="math-container">$\Pi_1^1$</span>.</li>
</ol>
<p>Any suggestions?</p>

<undecidability>
How to show that a problem is in $\Pi_1^1$?
David Carral
# How to show that a problem is in $\Pi_1^1$?

(Asked by: username_0 on 2023-10-20)

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?

**Tags:** undecidability


---

## 2 answers

### Answer by username_1 on 2023-10-20. Score: 6

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].

[1] [https://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/RucurringDominoes.pdf](https://www.wisdom.weizmann.ac.il/%7Edharel/SCANNED.PAPERS/RucurringDominoes.pdf)

> **Comments:**
> **username_2**: A quite readable paper on tilings is also “The convenience of tilings” by Peter van Emde Boas  
> **username_0**: 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 : )  

---

### Answer by username_3 on 2023-10-20. Score: 6

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}$](https://en.wikipedia.org/wiki/Kleene%27s_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](https://en.wikipedia.org/wiki/Kleene%E2%80%93Brouwer_order) 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*](https://projecteuclid.org/ebooks/perspectives-in-logic/Higher-Recursion-Theory/toc/pl/1235422631).

---

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](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_3**: Out of curiosity, why the downvote?  
> **username_0**: Thank you for your detailed reply! : )  

---

