Fourth-level quantifier-pattern degrees — Problem 3.1

3. Takayuki Kihara

The following problems concern a realizability-theoretic refinement of many-one and Wadge reducibility.

For sets $A,B\subseteq\omega^{\omega}$, define

if there is a computable function

such that

for every $x\in\omega^{\omega}$. Replacing “computable” by “continuous” gives Wadge reducibility, denoted by

For formulas, the truth-preserving map on instances is not sufficient. The witnesses for the two formulas must also be uniformly convertible.

Let $\alpha\Vdash\varphi(x)$ mean that $\alpha$ is a witness, or realizer, for the truth of $\varphi(x)$. The witness relation is defined inductively from the logical structure of $\varphi$; see [2, Definition 2.10].

A formula $\varphi$ is realizability-theoretically many-one reducible to a formula $\psi$, written

if there are computable functions $\eta,r^{-},r^{+}$ such that

If $\alpha\Vdash\varphi(x)$, then

If $\beta\Vdash\psi(\eta(x))$, then

This is also called Levin reducibility; see [2, Definition 2.13]. Its continuous analogue gives the corresponding realizability-theoretic version of Wadge reducibility.

Existentially quantified variables may depend on all preceding universally quantified variables. For example, a witness for

consists of three functions

such that

Thus, $F_{0}(a)$ witnesses $b$, $F_{1}(a,c)$ witnesses $d$, and $F_{2}(a,c,e)$ witnesses $f$.

In addition to the ordinary quantifiers $\exists$ and $\forall$, define

and

A finite sequence

is called a quantifier pattern. If

then a formula of the form

where $\theta$ is bounded, is called an $\overline{Q}$-formula.

For each quantifier pattern $\overline{Q}$, let

denote a fixed $\overline{Q}$-complete formula.

Consider

and

Although both are classically $\Sigma^{0}_{2}$ properties, their witness structures are different. The first has the quantifier pattern $\exists\forall$, whereas the second has the pattern $\forall^{\infty}$.

The realizability-theoretic classification of $\Sigma^{0}_{2}$ quantifier patterns consists of exactly three degrees:

The abstract treatment of this classification is given in [1].

The more concrete analysis of the $\Sigma^{0}_{3}$ and $\Pi^{0}_{3}$ levels is given in [2]. The known numbers of equivalence classes are as follows:

There is exactly one many-one equivalence class of $\Pi^{0}_{2}$ quantifier patterns, represented by

There are exactly three many-one equivalence classes of $\Sigma^{0}_{2}$ quantifier patterns, represented by

There are exactly three many-one equivalence classes of $\Sigma^{0}_{3}$ quantifier patterns, represented by

There are exactly five many-one equivalence classes of $\Pi^{0}_{3}$ quantifier patterns, represented by

The corresponding classifications at the fourth level are still in progress.

Current research status is unassessed. The dated source poses this question; inclusion does not certify that it remains open today.