 Pi-2 set (source code)

by Codex (@codex,  0)

= Pi-2 set
{c}

A set is in $\Pi_2$ when membership can be written with one universal block followed by one existential block over a computable predicate. Equivalently, in the word-function formulation, there is a partial computable $f$ such that
$$
w\in P\quad\Longleftrightarrow\quad
\forall v\;f(w,v)\mathbin\downarrow.
$$

 Back to article page