[proofplan]
We separately prove that $\operatorname{Fin}$ fails to be $\Sigma_1$ and fails to be $\Pi_1$. Both directions come from the strong form of [Rice's Theorem](/theorems/1835): the proof there exhibits, for any non-trivial index set $I$, a reduction from either $\mathbb{W} \setminus \mathbb{K}$ (when $e \in I$) or $\mathbb{K}$ (when $e \notin I$) to $I$, where $e$ is the fixed empty-domain code. Since $W_e = \varnothing$ is finite, $e \in \operatorname{Fin}$, so Case 1 of Rice's theorem directly gives $\mathbb{W} \setminus \mathbb{K} \leq_m \operatorname{Fin}$. Combined with the facts $\mathbb{W} \setminus \mathbb{K} \notin \Sigma_1$ (from [$\Sigma_1$ Is Not Closed Under Complement](/theorems/1826)) and $\Sigma_1$-closure under $\leq_m$, this rules out $\operatorname{Fin} \in \Sigma_1$. For $\Pi_1$, we must show $\mathbb{K} \leq_m \operatorname{Fin}$ directly; the construction is a timed-halting-gate variant of the $s$-$m$-$n$ recipe in which the "good" inputs are those *before* the halting time (finitely many) and the "bad" inputs are those *from* the halting time onward (also finitely many, but here, if the machine never halts, then *all* inputs are good and $W_{h(w)} = \mathbb{W}$). This arranges $W_{h(w)}$ to be finite iff $w \in \mathbb{K}$.
[/proofplan]
[step:Fix notation, recall the strong form of Rice's theorem, and the hierarchy facts]
Fix the course alphabet $\Sigma$ with distinguished accept letter $a \in \Sigma$ and write $\mathbb{W} = \Sigma^*$. For $c \in \mathbb{W}$, write $f_{c, 1} : \mathbb{W} \rightharpoonup \mathbb{W}$ for the arity-$1$ computable partial function computed by the machine with code $c$, and $W_c := \operatorname{dom} f_{c, 1}$. Recall
\begin{align*}
\mathbb{K} &= \{w \in \mathbb{W} : w \in W_w\}, &
\operatorname{Fin} &= \{v \in \mathbb{W} : W_v \text{ is finite}\}, & \sim \text{ on } \mathbb{W} &\iff W_v = W_u.
\end{align*}
Fix a code $e \in \mathbb{W}$ with $W_e = \varnothing$, e.g. the code of an immediate-infinite-loop machine. Since $\varnothing$ is finite, $e \in \operatorname{Fin}$.
*The strong form of Rice's theorem.* The proof of [Rice's Theorem](/theorems/1835) (Steps 3–5) establishes that for every non-trivial index set $I$:
(a) if $e \in I$, then $\mathbb{W} \setminus \mathbb{K} \leq_m I$ via a total computable $h$ obtained by applying the $s$-$m$-$n$ theorem to a gated two-argument function, with $h(u) \sim w$ when $u \in \mathbb{K}$ (for a chosen $w \notin I$ with $W_w \neq \varnothing$) and $h(u) \sim e$ when $u \notin \mathbb{K}$;
(b) if $e \notin I$, then $\mathbb{K} \leq_m I$ via the same construction with $w \in I$ this time.
*Closure of $\Sigma_1$ and $\Pi_1$ under $\leq_m$.* By [Closure Properties of $\Sigma_1$](/theorems/???) and [Closure Properties of $\Pi_1$](/theorems/???): if $A \leq_m B$ and $B \in \Sigma_1$, then $A \in \Sigma_1$; similarly for $\Pi_1$. These are the contrapositive tools we need.
*Hierarchy facts for $\mathbb{K}$ and its complement.* From [Halting Sets Are Computably Enumerable](/theorems/1822) and [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824), $\mathbb{K} \in \Sigma_1$. From [$\Sigma_1$ Is Not Closed Under Complement](/theorems/1826), $\mathbb{W} \setminus \mathbb{K} \notin \Sigma_1$. Dually, $\mathbb{W} \setminus \mathbb{K} \in \Pi_1$ by definition (complement of $\Sigma_1$), and $\mathbb{K} \notin \Pi_1$ (else $\mathbb{K} \in \Sigma_1 \cap \Pi_1 = \Delta_1$, which by [Computable Sets Are $\Delta_1$](/theorems/1825) means $\mathbb{K}$ is computable, contradicting [The Halting Problem](/theorems/1823)).
[/step]
[step:$\operatorname{Fin}$ is not $\Sigma_1$]
$\operatorname{Fin}$ is an index set (membership depends only on $W_v$) and non-trivial ($e \in \operatorname{Fin}$ since $W_e = \varnothing$ is finite; the constant-halting code $t$ of Step 2 of the proof of [Corollaries of Rice's Theorem](/theorems/1836) has $W_t = \mathbb{W}$ infinite, so $t \notin \operatorname{Fin}$). Since $e \in \operatorname{Fin}$, by Case (a) of Step 1,
\begin{align*}
\mathbb{W} \setminus \mathbb{K} &\leq_m \operatorname{Fin}.
\end{align*}
Suppose for contradiction that $\operatorname{Fin} \in \Sigma_1$. By closure of $\Sigma_1$ under $\leq_m$ (Step 1), $\mathbb{W} \setminus \mathbb{K} \leq_m \operatorname{Fin} \in \Sigma_1$ forces $\mathbb{W} \setminus \mathbb{K} \in \Sigma_1$ — contradicting [$\Sigma_1$ Is Not Closed Under Complement](/theorems/1826), which says $\mathbb{W} \setminus \mathbb{K} \notin \Sigma_1$.
Hence $\operatorname{Fin} \notin \Sigma_1$.
[guided]
*Why does the $\mathbb{W} \setminus \mathbb{K}$ reduction come "for free" from Rice?* The proof of [Rice's Theorem](/theorems/1835) is not a black-box non-computability result; it constructs an explicit reduction whose source set depends on which side of $I$ the empty-domain witness $e$ lies. When $e \in I$, the reduction source is $\mathbb{W} \setminus \mathbb{K}$; when $e \notin I$, it is $\mathbb{K}$. This "which side of $e$" bookkeeping is the *strong form* referenced in Step 1.
*Why does $e \in \operatorname{Fin}$ give us $\mathbb{W} \setminus \mathbb{K}$ (and not $\mathbb{K}$)?* Because the reduction pattern from Step 3 of the proof of [Rice's Theorem](/theorems/1835) routes convergent inputs $u \in \mathbb{K}$ to $h(u) \sim w \notin I$ and divergent inputs $u \notin \mathbb{K}$ to $h(u) \sim e \in I$. Membership in $I$ is thus aligned with "$u \notin \mathbb{K}$", making the reduction witness $\mathbb{W} \setminus \mathbb{K} \leq_m I$. If instead $e \notin I$, the alignment flips and one gets $\mathbb{K} \leq_m I$. For $\operatorname{Fin}$, $e \in \operatorname{Fin}$ and the first pattern applies.
*Why does non-$\Sigma_1$-ness of $\mathbb{W} \setminus \mathbb{K}$ pin down non-$\Sigma_1$-ness of $\operatorname{Fin}$?* Closure of $\Sigma_1$ under $\leq_m$ says: if you can reduce $A$ to a $\Sigma_1$ set, then $A$ is $\Sigma_1$. Contrapositively, if $A$ is *not* $\Sigma_1$ and $A \leq_m B$, then $B$ is *not* $\Sigma_1$. Here $A = \mathbb{W} \setminus \mathbb{K}$ (not $\Sigma_1$, by [$\Sigma_1$ Is Not Closed Under Complement](/theorems/1826)), and $B = \operatorname{Fin}$. The chain seals the conclusion.
*Why does $\Sigma_1$ fail to be closed under complement?* Because $\mathbb{K} \in \Sigma_1$ but $\mathbb{W} \setminus \mathbb{K} \notin \Sigma_1$. The latter would force $\mathbb{K} \in \Sigma_1 \cap \Pi_1 = \Delta_1$ and hence computable (by [Computable Sets Are $\Delta_1$](/theorems/1825)), contradicting [The Halting Problem](/theorems/1823).
[/guided]
[/step]
[step:Set up the reduction $\mathbb{K} \leq_m \operatorname{Fin}$ via a timed halting gate]
To show $\operatorname{Fin} \notin \Pi_1$, we construct a reduction $\mathbb{K} \leq_m \operatorname{Fin}$. (Rice's theorem only gives $\mathbb{W} \setminus \mathbb{K} \leq_m \operatorname{Fin}$, which is in the wrong direction for $\Pi_1$-ness.) The construction inverts the pattern: instead of making $W_{h(w)}$ all-or-nothing, we make $W_{h(w)}$ finite-or-infinite, with finite when $w \in \mathbb{K}$ and infinite when $w \notin \mathbb{K}$.
We use the timed simulation function of [Computability of the Configuration Function](/theorems/1818): for each register machine $M$ of arity $1$ there is a total computable function
\begin{align*}
t_{M} : \mathbb{W}^2 &\to \mathbb{W}, \\
(v, u) &\mapsto \begin{cases} a & \text{if $M$ on input $v$ halts in at most $\#u$ steps}, \\ \varepsilon & \text{otherwise}, \end{cases}
\end{align*}
where $\#u$ is the shortlex index of $u$ (see [Shortlex Is Order-Isomorphic to $\mathbb{N}$](/theorems/1815)). For $w \in \mathbb{W}$, write $t_{w, 1}(v, u) := t_{M_w}(v, u)$ where $M_w$ is the register machine with code $w$. The assignment $w \mapsto t_{w, 1}$ is uniformly total computable: there is a single total computable $t : \mathbb{W}^3 \to \mathbb{W}$ with $t(w, v, u) = t_{w, 1}(v, u)$, by [Computability of the Configuration Function](/theorems/1818) combined with the uniform coding of register machines.
Define
\begin{align*}
g : \mathbb{W}^2 &\rightharpoonup \mathbb{W}, \\
(v, w) &\mapsto \begin{cases} \uparrow & \text{if } t(w, w, v) = a, \\ \varepsilon & \text{if } t(w, w, v) = \varepsilon. \end{cases}
\end{align*}
[claim:$g$ is computable]
A register machine $M_g$ witnessing $g$ runs on input $(v, w)$ as follows:
(a) Invoke the total computable $t : \mathbb{W}^3 \to \mathbb{W}$ on $(w, w, v)$: build the triple by pairing and copy primitives (total computable, L2 of Step 4 of the proof of [Recursive Implies Computable](/theorems/1817)), then run the register machine for $t$.
(b) Case-distinguish on the output (total computable primitive, L2): if the output is $\varepsilon$, halt with $\varepsilon$ in register $0$; if the output is $a$, enter an immediate infinite loop.
This matches the definition of $g$. Formally, $g = \mathrm{cd} \circ t \circ \sigma$, where $\sigma : \mathbb{W}^2 \to \mathbb{W}^3$, $(v, w) \mapsto (w, w, v)$ is total computable (pairing and copy primitives) and $\mathrm{cd} : \mathbb{W} \rightharpoonup \mathbb{W}$ sends $\varepsilon \mapsto \varepsilon$ and $a \mapsto \uparrow$ (computable by L2). Composition preserves computability of partial functions (L1).
[/claim]
[/step]
[step:Apply the $s$-$m$-$n$ theorem and compute $W_{h(w)}$]
Apply the [$s$-$m$-$n$ Theorem](/theorems/???) to $g : \mathbb{W}^2 \rightharpoonup \mathbb{W}$, with $w$ as the parameter: we obtain a total computable
\begin{align*}
h : \mathbb{W} &\to \mathbb{W}
\end{align*}
such that for every $w \in \mathbb{W}$ and $v \in \mathbb{W}$,
\begin{align*}
f_{h(w), 1}(v) &= g(v, w) = \begin{cases} \uparrow & \text{if } t(w, w, v) = a, \\ \varepsilon & \text{if } t(w, w, v) = \varepsilon. \end{cases}
\end{align*}
[claim:For every $w \in \mathbb{W}$: $W_{h(w)}$ is finite if $w \in \mathbb{K}$ and $W_{h(w)} = \mathbb{W}$ if $w \notin \mathbb{K}$]
Fix $w \in \mathbb{W}$.
*Case $w \in \mathbb{K}$.* Then $f_{w, 1}(w) \downarrow$, i.e. $M_w$ halts on input $w$ in some number of steps $n \in \mathbb{N}$. By definition of $t$, $t(w, w, v) = a$ iff $\#v \ge n$. Since $(\mathbb{W}, <)$ is order-isomorphic to $(\mathbb{N}, <)$ via shortlex (see [Shortlex Is Order-Isomorphic to $\mathbb{N}$](/theorems/1815)), the set $\{v \in \mathbb{W} : \#v < n\}$ has cardinality $n < \infty$, and the set $\{v \in \mathbb{W} : \#v \ge n\}$ is cofinite. Therefore
\begin{align*}
W_{h(w)} &= \{v \in \mathbb{W} : f_{h(w), 1}(v) \downarrow\} \\
&= \{v \in \mathbb{W} : t(w, w, v) = \varepsilon\} \\
&= \{v \in \mathbb{W} : \#v < n\},
\end{align*}
which has exactly $n$ elements. In particular, $W_{h(w)}$ is finite.
*Case $w \notin \mathbb{K}$.* Then $f_{w, 1}(w) \uparrow$, so $M_w$ never halts on input $w$. Hence $t(w, w, v) = \varepsilon$ for every $v \in \mathbb{W}$, so $f_{h(w), 1}(v) = \varepsilon$ for every $v$, giving $W_{h(w)} = \mathbb{W}$. In particular, $W_{h(w)}$ is infinite.
[/claim]
[/step]
[step:Conclude $\mathbb{K} \leq_m \operatorname{Fin}$ and deduce $\operatorname{Fin} \notin \Pi_1$]
By Step 4, for every $w \in \mathbb{W}$,
\begin{align*}
w \in \mathbb{K} &\iff W_{h(w)} \text{ is finite} \iff h(w) \in \operatorname{Fin}.
\end{align*}
Since $h$ is total computable (Step 4), $h$ is a many-one reduction from $\mathbb{K}$ to $\operatorname{Fin}$: $\mathbb{K} \leq_m \operatorname{Fin}$.
Suppose for contradiction that $\operatorname{Fin} \in \Pi_1$. By closure of $\Pi_1$ under $\leq_m$ (Step 1), $\mathbb{K} \leq_m \operatorname{Fin} \in \Pi_1$ forces $\mathbb{K} \in \Pi_1$ — contradicting the fact recorded in Step 1 that $\mathbb{K} \notin \Pi_1$ (else $\mathbb{K}$ would be computable).
Hence $\operatorname{Fin} \notin \Pi_1$.
[guided]
We unpack the timed-gate reduction.
*Why doesn't the Rice-style construction of the proof of [Rice's Theorem](/theorems/1835) work for $\Pi_1$?* Because Rice's theorem with $e \in I$ yields $\mathbb{W} \setminus \mathbb{K} \leq_m I$, and $\mathbb{W} \setminus \mathbb{K} \in \Pi_1$ — so this reduction transfers $\Pi_1$-membership *into* $I$, not out of it. For ruling out $I \in \Pi_1$, we need a reduction from a set known *not* to be $\Pi_1$, and the canonical such set is $\mathbb{K}$.
*How does the gate design differ from Step 3 of the proof of [Rice's Theorem](/theorems/1835)?* There, the gate was "halt if $f_{u, 1}(u) \downarrow$; diverge otherwise" — an all-or-nothing gate: once $f_{u, 1}(u)$ is known to halt, every subsequent computation on $v$ runs unimpeded. Here, the gate is *time-dependent*: "halt on $v$ iff $M_w$ on $w$ has *not yet* halted by step $\#v$". This makes the size of $W_{h(w)}$ a function of *how long* $M_w$ takes on $w$ — finite if it halts (at some step $n$, giving $n$ inputs $v$ before timeout) and infinite if it never halts (all $v$ admitted).
*Why do we want "finite if $w \in \mathbb{K}$" and not "infinite if $w \in \mathbb{K}$"?* Because $\operatorname{Fin}$ is defined by finiteness. We need $W_{h(w)} \in \operatorname{Fin} \iff w \in \mathbb{K}$ — and the gate "diverge on $v$ after the halting time, $\varepsilon$ before" delivers exactly this.
*Why flip the convention? (In the proof of $\mathbb{K}$ being $\Sigma_1$-complete, "convergent = in $\mathbb{K}$" was good.)* We are still keeping "convergent = in $\mathbb{K}$" for the *input* $w$ (Step 4 case analysis), but for the *inner computation* of $f_{h(w), 1}(v)$ we flip: we divergence when the gate is tripped (i.e. when $M_w$ on $w$ has halted by step $\#v$) and converge otherwise. The flip is deliberate: divergence carves out $v$ from $W_{h(w)}$, and we want to carve out $v$'s after the halting time.
*Why is $t(w, w, v)$ the right gate (as opposed to $t(w, w, u)$ for some $u$)?* Because we need the second argument of the inner computation (i.e. the "time index") to range with $v$, so that $W_{h(w)}$ as a function of $v$ is finite in exactly the $w \in \mathbb{K}$ case. Making the time index $v$ means $W_{h(w)}$ counts "$v$'s admitted before timeout", and this count is the halting time of $M_w$ on $w$.
*Sanity check.* When $w \in \mathbb{K}$ with halting time $n$: $W_{h(w)} = \{v : \#v < n\}$, which has $n < \infty$ elements. $h(w) \in \operatorname{Fin}$. When $w \notin \mathbb{K}$: $W_{h(w)} = \mathbb{W}$. $h(w) \notin \operatorname{Fin}$. The biconditional $w \in \mathbb{K} \iff h(w) \in \operatorname{Fin}$ is verified.
*On totality of $h$.* The $s$-$m$-$n$ theorem gives $h$ total computable, regardless of whether $g$ is total. So even when $w \notin \mathbb{K}$ (and $g(v, w) = \varepsilon$ for every $v$, producing $f_{h(w), 1}$ total), or when $w \in \mathbb{K}$ (and $g(v, w)$ converges on some $v$ and diverges on others), $h(w)$ exists as a concrete word — the code of the gated register machine.
*Final integration with Step 2 and the hierarchy.* Step 2 rules out $\operatorname{Fin} \in \Sigma_1$ via Rice + $\Sigma_1$ non-closure under complement. Step 5 rules out $\operatorname{Fin} \in \Pi_1$ via direct reduction from $\mathbb{K}$ + $\Pi_1$ closure under $\leq_m$ + $\mathbb{K} \notin \Pi_1$. In both halves, the cleanest proof factors through a reduction to a set whose hierarchy position is already known.
[/guided]
[/step]
[step:Conclude]
Step 2 proves $\operatorname{Fin} \notin \Sigma_1$ by combining the strong form of Rice's theorem ($\mathbb{W} \setminus \mathbb{K} \leq_m \operatorname{Fin}$, since $e \in \operatorname{Fin}$) with $\Sigma_1$-closure under $\leq_m$ and $\mathbb{W} \setminus \mathbb{K} \notin \Sigma_1$ (from [$\Sigma_1$ Is Not Closed Under Complement](/theorems/1826)). Steps 3–5 prove $\operatorname{Fin} \notin \Pi_1$ by constructing, via a timed halting gate and the $s$-$m$-$n$ theorem, a total computable reduction $h : \mathbb{W} \to \mathbb{W}$ witnessing $\mathbb{K} \leq_m \operatorname{Fin}$, then applying $\Pi_1$-closure under $\leq_m$ together with $\mathbb{K} \notin \Pi_1$. Hence $\operatorname{Fin}$ is neither $\Sigma_1$ nor $\Pi_1$.
[/step]
