[proofplan]
We exhibit an explicit witness: the halting set $\mathbb{K} \subseteq \mathbb{W}$. By the [Halting Sets Are Computably Enumerable](/theorems/1822), $\mathbb{K}$ is computably enumerable; by [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824), $\mathbb{K}$ is $\Sigma_1$. The argument proceeds by contradiction. If $\Sigma_1$ were closed under complement, the complement $\mathbb{W} \setminus \mathbb{K}$ would also be $\Sigma_1$. Together with $\mathbb{K} \in \Sigma_1$, this would mean $\mathbb{K}^c \in \Sigma_1$ and $\mathbb{K} \in \Sigma_1$, so $\mathbb{K} \in \Sigma_1 \cap \Pi_1 = \Delta_1$. By [Computable Sets Are $\Delta_1$](/theorems/1825), $\mathbb{K}$ would then be computable, contradicting [The Halting Problem](/theorems/1823). Hence no such closure can hold.
[/proofplan]
[step:Fix the classes $\Sigma_1$, $\Pi_1$, $\Delta_1$ and the halting sets]
Fix $\mathbb{W} = \Sigma^*$ with the distinguished accept letter $a \in \Sigma$. A set $X \subseteq \mathbb{W}^k$ belongs to the classes at level $1$ of the arithmetical hierarchy according to:
\begin{align*}
X \in \Sigma_1 &\iff X = p(Y) \text{ for some computable } Y \subseteq \mathbb{W}^{k+1}, \\
X \in \Pi_1 &\iff X^c = \mathbb{W}^k \setminus X \in \Sigma_1, \\
X \in \Delta_1 &\iff X \in \Sigma_1 \cap \Pi_1.
\end{align*}
Here $p(Y) = \{w : \exists v, (w, v) \in Y\}$ is the projection onto the first $k$ coordinates.
The halting set in one variable is
\begin{align*}
\mathbb{K} &= \{w \in \mathbb{W} : f_{w, 1}(w) \downarrow\} \subseteq \mathbb{W},
\end{align*}
where $f_{w, 1} : \mathbb{W} \rightharpoonup \mathbb{W}$ is the arity-$1$ partial function computed by the register machine coded by $w$ (with $f_{w, 1}$ the everywhere-undefined partial function when $w$ is not a valid code), as in the proof of [Halting Sets Are Computably Enumerable](/theorems/1822).
[/step]
[step:Record that $\mathbb{K}$ is $\Sigma_1$ and that $\mathbb{K}$ is not computable]
By the [Halting Sets Are Computably Enumerable](/theorems/1822), the set $\mathbb{K}$ is computably enumerable: there is a computable partial function $F : \mathbb{W} \rightharpoonup \mathbb{W}$ with $\operatorname{dom} F = \mathbb{K}$. By [Computably Enumerable Sets Are $\Sigma_1$](/theorems/1824), every computably enumerable subset of $\mathbb{W}^k$ is $\Sigma_1$; applied to $k = 1$, this gives $\mathbb{K} \in \Sigma_1$.
By [The Halting Problem](/theorems/1823), $\mathbb{K}$ is not computable.
[/step]
[step:Argue by contradiction assuming $\Sigma_1$ is closed under complement]
Suppose, for contradiction, that $\Sigma_1$ is closed under complement: for every $k \ge 1$ and every $X \subseteq \mathbb{W}^k$, if $X \in \Sigma_1$ then $\mathbb{W}^k \setminus X \in \Sigma_1$.
Apply the hypothesis with $k = 1$ and $X = \mathbb{K}$. Since $\mathbb{K} \in \Sigma_1$ (Step 2), the hypothesis gives $\mathbb{K}^c = \mathbb{W} \setminus \mathbb{K} \in \Sigma_1$. By the definition of $\Pi_1$ restated in Step 1, this is equivalent to
\begin{align*}
\mathbb{K} &\in \Pi_1.
\end{align*}
Combined with $\mathbb{K} \in \Sigma_1$ from Step 2:
\begin{align*}
\mathbb{K} &\in \Sigma_1 \cap \Pi_1 = \Delta_1.
\end{align*}
[/step]
[step:Derive a contradiction via $\Delta_1 =$ computable]
By [Computable Sets Are $\Delta_1$](/theorems/1825), a set $X \subseteq \mathbb{W}^k$ is computable if and only if $X$ is $\Delta_1$. Applied to the subset $\mathbb{K} \subseteq \mathbb{W}$, which Step 3 showed lies in $\Delta_1$, we obtain that $\mathbb{K}$ is computable.
This directly contradicts Step 2, which recorded that $\mathbb{K}$ is not computable. The assumption that $\Sigma_1$ is closed under complement is therefore false.
[/step]
[step:Conclude]
The existence of $\mathbb{K} \in \Sigma_1$ whose complement $\mathbb{W} \setminus \mathbb{K}$ is not $\Sigma_1$ (otherwise, as shown in Steps 3–4, $\mathbb{K}$ would be computable, contradicting [The Halting Problem](/theorems/1823)) shows that $\Sigma_1$ is not closed under complement.
[/step]
