[proofplan] It is enough to prove closure under binary unions and binary intersections, since closure under arbitrary finite unions and intersections then follows by induction. For two sets in the same arithmetical class, put their definitions into the same alternating quantifier pattern and synchronize the quantified variables using a computable pairing function. The paired formula has the same quantifier complexity, and its computable matrix expresses either the union or the intersection. Finally, complement closure of $\Delta^0_n$ follows from the duality between $\Sigma^0_n$ and $\Pi^0_n$ under complementation. [/proofplan] [step:Reduce finite closure to the binary case] Fix $n \in \mathbb{N}$ with $n \ge 1$. Suppose a class $\Gamma$ of subsets of $\mathbb{N}$ contains $\varnothing$ and $\mathbb{N}$ and is closed under binary unions. Then $\Gamma$ is closed under finite unions by induction on the number of sets: the empty union is $\varnothing \in \Gamma$, the union of one set is already in $\Gamma$, and if $A_1,\dots,A_k,A_{k+1} \in \Gamma$, then \begin{align*} A_1 \cup \cdots \cup A_k \cup A_{k+1} = (A_1 \cup \cdots \cup A_k) \cup A_{k+1}. \end{align*} The induction hypothesis places $A_1 \cup \cdots \cup A_k$ in $\Gamma$, and binary closure then places the displayed union in $\Gamma$. The same induction, with $\cap$ in place of $\cup$, proves that binary intersection closure implies finite intersection closure, using the empty intersection $\mathbb{N} \in \Gamma$ as the empty-family case. The sets $\varnothing$ and $\mathbb{N}$ belong to every $\Sigma^0_n$ and every $\Pi^0_n$ class, since they are defined by the computable predicates that are identically false and identically true, respectively, with dummy quantified variables added to match the required prefix. Thus it remains to prove binary union and binary intersection closure. [/step] [step:Synchronize two formulas with the same arithmetical prefix] Let $\Gamma$ denote either the [arithmetical hierarchy](/page/Arithmetical%20Hierarchy) class $\Sigma^0_n$ or the [arithmetical hierarchy](/page/Arithmetical%20Hierarchy) class $\Pi^0_n$. Let $Q_1,\dots,Q_n$ be the alternating quantifier prefix defining $\Gamma$: for $\Sigma^0_n$, $Q_1=\exists$ and the quantifiers alternate; for $\Pi^0_n$, $Q_1=\forall$ and the quantifiers alternate. Let $A,B \subseteq \mathbb{N}$ lie in $\Gamma$. By the page's normal-form definition of $\Gamma$, finite quantifier blocks at a given alternation level have already been coded into single natural-number variables by computable tuple codings. Hence there are [computable predicates](/page/Computable%20Predicate) \begin{align*} R,S \subseteq \mathbb{N}^{n+1} \end{align*} such that, for every $x \in \mathbb{N}$, \begin{align*} x \in A &\iff Q_1 u_1\, Q_2 u_2 \cdots Q_n u_n\, R(x,u_1,\dots,u_n),\\ x \in B &\iff Q_1 v_1\, Q_2 v_2 \cdots Q_n v_n\, S(x,v_1,\dots,v_n). \end{align*} Fix a [computable pairing function](/page/Computable%20Pairing%20Function) \begin{align*} \langle \cdot,\cdot\rangle: \mathbb{N}\times \mathbb{N}\to \mathbb{N} \end{align*} with computable coordinate projections \begin{align*} (\cdot)_0,\;(\cdot)_1:\mathbb{N}\to\mathbb{N} \end{align*} satisfying $(\langle a,b\rangle)_0=a$ and $(\langle a,b\rangle)_1=b$ for all $a,b\in\mathbb{N}$. For each $j \in \{1,\dots,n\}$, the single variable $w_j$ will code the pair $(u_j,v_j)$. Define computable predicates \begin{align*} T_\cup,T_\cap \subseteq \mathbb{N}^{n+1} \end{align*} by \begin{align*} T_\cup(x,w_1,\dots,w_n) &\iff R(x,(w_1)_0,\dots,(w_n)_0) \lor S(x,(w_1)_1,\dots,(w_n)_1),\\ T_\cap(x,w_1,\dots,w_n) &\iff R(x,(w_1)_0,\dots,(w_n)_0) \land S(x,(w_1)_1,\dots,(w_n)_1). \end{align*} These predicates are computable because the coordinate projections are computable and computable predicates are closed under finite Boolean combinations. [guided] The point of this step is to make the two definitions use one shared block of quantified variables. We begin with two formulas of the same arithmetical type: \begin{align*} x \in A &\iff Q_1 u_1\, Q_2 u_2 \cdots Q_n u_n\, R(x,u_1,\dots,u_n),\\ x \in B &\iff Q_1 v_1\, Q_2 v_2 \cdots Q_n v_n\, S(x,v_1,\dots,v_n). \end{align*} The quantifier symbols $Q_1,\dots,Q_n$ are identical in the two formulas because both sets belong to the same pointclass $\Gamma$, either $\Sigma^0_n$ or $\Pi^0_n$. The normal form used here has one natural-number variable at each alternation level; any finite block of variables at one level is first coded by a computable tuple coding, so no quantifier complexity is lost. We now combine the two variables at each quantifier level into one coded variable. Fix a computable pairing map \begin{align*} \langle \cdot,\cdot\rangle: \mathbb{N}\times \mathbb{N}\to \mathbb{N} \end{align*} with computable projections $(\cdot)_0$ and $(\cdot)_1$, so that $(\langle a,b\rangle)_0=a$ and $(\langle a,b\rangle)_1=b$. Thus a single number $w_j$ can store the pair $(u_j,v_j)$, with $(w_j)_0$ recovering the $u_j$ coordinate and $(w_j)_1$ recovering the $v_j$ coordinate. Using these projections, define \begin{align*} T_\cup(x,w_1,\dots,w_n) &\iff R(x,(w_1)_0,\dots,(w_n)_0) \lor S(x,(w_1)_1,\dots,(w_n)_1),\\ T_\cap(x,w_1,\dots,w_n) &\iff R(x,(w_1)_0,\dots,(w_n)_0) \land S(x,(w_1)_1,\dots,(w_n)_1). \end{align*} These are still computable predicates. The reason is that computing $T_\cup$ or $T_\cap$ requires only finitely many computable operations: decode each $w_j$, evaluate the computable predicates $R$ and $S$, and then take either a finite disjunction or a finite conjunction of truth values. Why does this coding preserve the intended truth conditions? At a single quantifier level, the pairing projections give the equivalences \begin{align*} (\exists u\, \varphi(u)) \lor (\exists v\, \psi(v)) &\iff \exists w\,\bigl(\varphi((w)_0)\lor \psi((w)_1)\bigr),\\ (\forall u\, \varphi(u)) \lor (\forall v\, \psi(v)) &\iff \forall w\,\bigl(\varphi((w)_0)\lor \psi((w)_1)\bigr),\\ (\exists u\, \varphi(u)) \land (\exists v\, \psi(v)) &\iff \exists w\,\bigl(\varphi((w)_0)\land \psi((w)_1)\bigr),\\ (\forall u\, \varphi(u)) \land (\forall v\, \psi(v)) &\iff \forall w\,\bigl(\varphi((w)_0)\land \psi((w)_1)\bigr), \end{align*} whenever the free variables of $\varphi$ and $\psi$ are disjoint. The existential cases use surjectivity of the pairing projections onto pairs: witnesses $u$ and $v$ are coded by $w=\langle u,v\rangle$. The universal cases use the contrapositive: if the paired universal statement failed, a coded pair $w=\langle u,v\rangle$ would recover witnesses to failure in the original variables. Applying these one-level equivalences successively from the outermost quantifier inward proves that the synchronized $T_\cup$ and $T_\cap$ formulas define exactly $A\cup B$ and $A\cap B$. [/guided] [/step] [step:Prove binary union and intersection closure for each arithmetical class] We claim that, for every $x \in \mathbb{N}$, \begin{align*} x \in A \cup B &\iff Q_1 w_1\, Q_2 w_2 \cdots Q_n w_n\, T_\cup(x,w_1,\dots,w_n),\\ x \in A \cap B &\iff Q_1 w_1\, Q_2 w_2 \cdots Q_n w_n\, T_\cap(x,w_1,\dots,w_n). \end{align*} This follows by repeatedly using the following elementary equivalences for formulas whose free variables are disjoint: \begin{align*} (\exists u\, \varphi(u)) \lor (\exists v\, \psi(v)) &\iff \exists w\,\bigl(\varphi((w)_0)\lor \psi((w)_1)\bigr),\\ (\forall u\, \varphi(u)) \lor (\forall v\, \psi(v)) &\iff \forall w\,\bigl(\varphi((w)_0)\lor \psi((w)_1)\bigr),\\ (\exists u\, \varphi(u)) \land (\exists v\, \psi(v)) &\iff \exists w\,\bigl(\varphi((w)_0)\land \psi((w)_1)\bigr),\\ (\forall u\, \varphi(u)) \land (\forall v\, \psi(v)) &\iff \forall w\,\bigl(\varphi((w)_0)\land \psi((w)_1)\bigr). \end{align*} For example, in the universal-disjunction case, if the right-hand side holds and neither $\forall u\,\varphi(u)$ nor $\forall v\,\psi(v)$ holds, then there are $u_0,v_0\in\mathbb{N}$ such that $\neg\varphi(u_0)$ and $\neg\psi(v_0)$. Taking $w=\langle u_0,v_0\rangle$ contradicts $\varphi((w)_0)\lor\psi((w)_1)$. The other three equivalences follow directly from the definitions of $\exists$, $\forall$, and the pairing projections. Applying these equivalences successively from the outside quantifier inward gives the two displayed normal forms. Since $T_\cup$ and $T_\cap$ are computable and the quantifier prefix is still $Q_1,\dots,Q_n$, both $A\cup B$ and $A\cap B$ belong to $\Gamma$. Therefore both $\Sigma^0_n$ and $\Pi^0_n$ are closed under binary unions and binary intersections. [/step] [step:Deduce the finite closure properties of $\Sigma^0_n$ and $\Pi^0_n$] Applying the binary-to-finite reduction to $\Gamma=\Sigma^0_n$ and to $\Gamma=\Pi^0_n$, the binary closure just proved implies that both $\Sigma^0_n$ and $\Pi^0_n$ are closed under finite unions and finite intersections. [/step] [step:Use complement duality to prove the Boolean closure of $\Delta^0_n$] Let $A \in \Delta^0_n$, where $\Delta^0_n$ denotes the [arithmetical hierarchy](/page/Arithmetical%20Hierarchy) class $\Sigma^0_n \cap \Pi^0_n$. By definition, \begin{align*} A \in \Sigma^0_n \cap \Pi^0_n. \end{align*} We prove the needed complement duality directly in this case. If $A\in\Sigma^0_n$, then there is a computable predicate $R \subseteq \mathbb{N}^{n+1}$ such that \begin{align*} x\in A &\iff Q_1 u_1\, Q_2 u_2 \cdots Q_n u_n\, R(x,u_1,\dots,u_n), \end{align*} where $Q_1=\exists$ and the quantifiers alternate. Negating the displayed formula and moving the negation through the finite alternating prefix changes each $Q_j$ to its dual quantifier $Q_j^\perp$ and replaces $R$ by the computable predicate $R^c$, defined by $R^c(x,u_1,\dots,u_n) \iff \neg R(x,u_1,\dots,u_n)$. Thus $A^c\in\Pi^0_n$. The same argument starting from a $\Pi^0_n$ definition of $A$ gives $A^c\in\Sigma^0_n$. Hence $A^c \in \Sigma^0_n\cap\Pi^0_n=\Delta^0_n$, so $\Delta^0_n$ is closed under complements. Now let $A,B\in\Delta^0_n$. Since $A,B\in\Sigma^0_n$ and $\Sigma^0_n$ is closed under binary unions and intersections, both $A\cup B$ and $A\cap B$ lie in $\Sigma^0_n$. Since $A,B\in\Pi^0_n$ and $\Pi^0_n$ is closed under binary unions and intersections, both $A\cup B$ and $A\cap B$ also lie in $\Pi^0_n$. Therefore \begin{align*} A\cup B,\; A\cap B \in \Sigma^0_n\cap\Pi^0_n=\Delta^0_n. \end{align*} The finite closure of $\Delta^0_n$ under unions and intersections follows by the same induction used at the beginning. Thus $\Delta^0_n$ is closed under finite unions, finite intersections, and complements. [/step]