Foundations of Unsolvability: Hierarchy and Priority in Recursion Theory

The study of recursion theory is an investigation into the algorithmic limits of mathematics. By mapping the hierarchy of unsolvability, we delineate the boundary between the effectively calculable and that which necessitates transfinite complexity. This paper addresses three core pillars of this field: the diagonalizing nature of the Halting Problem, the structural classification of sets within the arithmetical hierarchy, and the construction of Turing-incomplete recursively enumerable (r.e.) sets via finite injury priority arguments.

I. Diagonalization and the Halting Problem

The Halting Set $K=\{e\mid {\varphi }_e(e)\downarrow \}$ is the foundational set that is r.e. but not recursive.

Proof of Recursive Enumerability: Let $W_e$ be the domain of the $e$-th partial computable function ${\varphi }_e$. By definition, $K=\{e\mid e\in W_e\}$. Since the universal function $\psi (e,x)={\varphi }_e(x)$ is computable, $K$ is r.e..

Proof of Non-Recursiveness: Suppose $K$ were recursive. Then its characteristic function ${\chi }_K$ would be total computable. We define a partial computable function $f(x)$ as follows: $f(x)=\{\begin{array}{ll}\uparrow & \text{if }x\in K\\ 0& \text{if }x\notin K\end{array}$ Since $f$ is partial computable, by the Indexing Theorem (or Kleene’s Normal Form), there exists an index $k$ such that $f={\varphi }_k$. Consider the value $f(k)$:

• If $k\in K$, then by definition of $K$, ${\varphi }_k(k)\downarrow$. But by our definition of $f$, if $k\in K$, $f(k)\uparrow$. This is a contradiction.

• If $k\notin K$, then by definition of $K$, ${\varphi }_k(k)\uparrow$. But by our definition of $f$, if $k\notin K$, $f(k)=0$. This is a contradiction. Thus, $K$ cannot be recursive.

Significance: The Halting Problem demonstrates that there are well-defined mathematical problems for which no algorithm exists. This establishes that computational limits are intrinsic to formal systems, rather than limitations of physical hardware.

II. Reductions and the Arithmetical Hierarchy

The classification of sets into ${\Sigma }_n^0$ and ${\Pi }_n^0$ levels provides a structural scaffold for computational complexity. A set $A\in {\Sigma }_n^0$ if it is definable by a formula with $n$ alternating quantifiers starting with $\exists$ over a recursive predicate.

Post’s Theorem: A set $A$ is ${\Delta }_{n+1}^0$ (where ${\Delta }_{n+1}^0={\Sigma }_{n+1}^0\cap {\Pi }_{n+1}^0$) if and only if $A$ is computable in a set that is ${\Sigma }_n^0$. More broadly, ${\Sigma }_{n+1}^0$ sets are exactly those r.e. in ${\varnothing }^{(n)}$ (the $n$-th jump of the empty set). This connects the logical complexity of set definitions to their computational information content.

Totality and ${\Pi }_2^0$-Completeness: Let $Tot=\{e\mid {\varphi }_e\text{ is total}\}$. $Tot\in {\Pi }_2^0$ because $e\in Tot⟺\forall x\exists sT(e,x,s)$, where $T$ is Kleene’s $T$-predicate. To show ${\Pi }_2^0$-completeness, let $S$ be any ${\Pi }_2^0$ set: $x\in S⟺\forall y\exists zP(x,y,z)$. By the $s-m-n$ theorem, there exists a total computable function $f$ such that ${\varphi }_{f(x)}(y)$ searches for a $z$ satisfying $P(x,y,z)$. If the search succeeds, ${\varphi }_{f(x)}(y)\downarrow$; if not, it diverges. Thus, $x\in S⟺{\varphi }_{f(x)}$ is total. This uniform reduction places $Tot$ strictly higher than the Halting Problem, demonstrating that ${\Pi }_2^0$ represents a higher level of computational "hardness".

III. The Friedberg-Muchnik Theorem

The Friedberg-Muchnik Theorem solves Post’s Problem by constructing two r.e. sets $A$ and $B$ such that $A/{\le }_{T}B$ and $B/{\le }_{T}A$.

Construction: We define requirements $R_{2e}:{\Phi }_e^B\ne A$ and $R_{2e+1}:{\Phi }_e^A\ne B$. To satisfy $R_{2e}$, we choose a witness $x_e$, wait for a stage $s$ such that ${\Phi }_{e,s}^{B_s}(x_e)\downarrow =0$, and enumerate $x_e$ into $A$. To ensure this disagreement persists, we must prevent future changes to $B$ on the usage of the computation ${\Phi }_e^{B_s}(x_e)$. We define a restraint function $r(e,s)$, which acts as a barrier: any requirement $R_j$ with $j>2e$ is forbidden from putting numbers into $B$ below this usage.

Injury and Convergence: A requirement $R_j$ (where $j>e$) may attempt to enumerate a number into the oracle that violates the restraint, thereby injuring $R_e$. However, because each requirement $R_e$ is only injured by requirements with higher priority (lower index), and because we define our strategies to act at most finitely often, the restraints eventually stabilize. Each requirement is eventually satisfied, proving the existence of degrees strictly between $0$ and $0^{\prime }$.

Conclusion

The hierarchy of unsolvability is a unified architecture. From the self-referential failure of the Halting Problem, through the quantificational complexity of the arithmetical hierarchy, to the constructive priority arguments of Friedberg-Muchnik, recursion theory demonstrates that the landscape of computation is internally complex and resistant to reduction. These results establish the foundational limits for logic: computational power is not a singular resource, but a partitioned, structured hierarchy that defines the limits of what is knowable through effective procedure.

Works Cited

• Cooper, S. Barry. Computability Theory. Chapman & Hall/CRC, 2004.

• Odifreddi, Piergiorgio. Classical Recursion Theory. North-Holland, 1989.

• Shoenfield, Joseph R. Degrees of Unsolvability. North-Holland, 1971.

 

Compactness, Types, and the Architecture of First-Order Theories

I. Compactness and the Upward Löwenheim–Skolem Theorem

The Construction of Elementary Extensions

The Compactness Theorem serves as the primary engine for model-theoretic constructions, allowing us to build structures that satisfy arbitrary sets of consistent first-order axioms.

Theorem (Upward Löwenheim–Skolem): Let $T$ be an $L$-theory with an infinite model $\mathcal{M}$. For every cardinal $\kappa \ge \max (|L|,{\aleph }_0)$, there exists a model $\mathcal{N}$ of $T$ such that $\mathcal{M}⪯\mathcal{N}$ and $|\mathcal{N}|\ge \kappa$.

Proof: Let $\mathcal{M}$ be an infinite model of $T$ with domain $M$. We construct an elementary extension using the elementary diagram of $\mathcal{M}$. Let $L_M=L\cup \{c_m:m\in M\}$ be an expansion of the language $L$ where each element $m\in M$ is named by a unique constant symbol $c_m$. The elementary diagram of $\mathcal{M}$, denoted $Dia{g}_{el}(\mathcal{M})$, is the set of all $L_M$-sentences true in $\mathcal{M}$.

To construct a model of cardinality $\kappa$, we expand $L_M$ further to $L^{\prime }=L_M\cup \{d_{\alpha }:\alpha <\kappa \}$, where $\{d_{\alpha }{\}}_{\alpha <\kappa }$ is a set of new constant symbols. Consider the theory $\Gamma =Dia{g}_{el}(\mathcal{M})\cup \{d_{\alpha }\ne d_{\beta }:\alpha <\beta <\kappa \}$.

We claim $\Gamma$ is finitely satisfiable. Let ${\Gamma }_0\subseteq \Gamma$ be a finite subset. ${\Gamma }_0$ contains a finite number of new constants $\{d_{{\alpha }_1},\dots ,d_{{\alpha }_n}\}$. We can satisfy ${\Gamma }_0$ by expanding $\mathcal{M}$ to a model of $L^{\prime }$ where we interpret the constant symbols $c_m$ as the elements $m\in M$, and interpret the $d_{{\alpha }_i}$ as distinct elements in $M$ (possible because $M$ is infinite). By the Compactness Theorem, the full theory $\Gamma$ is satisfiable. Let $\mathcal{N}$ be a model of $\Gamma$. Since $\mathcal{N}\models Dia{g}_{el}(\mathcal{M})$, there exists an elementary embedding $h:\mathcal{M}\hookrightarrow \mathcal{N}$ (the Diagram Lemma). Thus, $\mathcal{M}⪯\mathcal{N}$. Finally, the axioms $\{d_{\alpha }\ne d_{\beta }\}$ ensure that the set $\{d_{\alpha }^{\mathcal{N}}:\alpha <\kappa \}$ has cardinality at least $\kappa$, implying $|\mathcal{N}|\ge \kappa$.

The Limits of Expression: Zooming In and Out

The Downward and Upward Löwenheim–Skolem theorems define the "cardinality bounds" of first-order logic. The Downward LS Theorem asserts that if a theory has an infinite model, it has a countable elementary substructure (provided $|L|={\aleph }_0$), allowing us to "zoom in" on a structure to find its countable essence. The Upward LS Theorem allows us to "zoom out," constructing models of arbitrary size.

A quintessential example is the theory of Peano Arithmetic ($PA$). The standard model $\mathbb{N}\models PA$ is countable. By the Upward LS theorem, there exist elementary extensions $\mathcal{N}\succ \mathbb{N}$ such that $|\mathcal{N}|>{\aleph }_0$. These "non-standard" models contain infinite elements greater than every standard natural number $n\in \mathbb{N}$. It is important to note that while $\mathbb{N}\prec \mathcal{N}$ holds for these specific extensions, it is not the case that $\mathbb{N}$ is an elementary substructure of every model of $PA$; rather, these models demonstrate that $PA$ cannot force a domain to be exactly $\mathbb{N}$ in first-order logic.

II. Stone Spaces and the Syntax-Semantics Interface

While Part I demonstrated how models grow, Part II examines how types control that growth. The structure of a theory is mirrored by its Stone space, which effectively maps the "syntax" (formulas) to the "semantics" (realizable sets of formulas).

Topology on the Stone Space $S_n(T)$

Let $S_n(T)$ be the set of complete $n$-types over $T$. For any $L$-formula $\varphi (\bar{x})$, we define the set $[\varphi ]=\{p\in S_n(T):\varphi \in p\}$. The collection $\{[\varphi ]:\varphi \in L\}$ forms a basis for the topology on $S_n(T)$.

1. Hausdorff: If $p\ne q$, there exists a formula $\varphi$ such that $\varphi \in p$ and $\varphi \notin q$. Thus $\neg \varphi \in q$. The sets $[\varphi ]$ and $[\neg \varphi ]$ are disjoint open sets containing $p$ and $q$, respectively.

2. Compactness: If $\{[{\varphi }_i]:i\in I\}$ is an open cover of $S_n(T)$, then ${\bigcap }_{i\in I}[\neg {\varphi }_i]=\varnothing$. This implies $T\cup \{\neg {\varphi }_i:i\in I\}$ is inconsistent. By the Compactness Theorem, some finite subset is inconsistent, implying ${\bigcup }_{i\in I_0}[{\varphi }_i]=S_n(T)$.

3. Totally Disconnected: Each $[\varphi ]$ is a clopen set because its complement is $[\neg \varphi ]$, which is also open. The existence of a basis of clopen sets confirms the space is zero-dimensional.

Categoricity, Saturation, and Atomic Models

The Stone space encodes the "variety" of models a theory can have. The connection between types and models is mediated by saturation and atomicity.

• Categoricity: Morley’s Categoricity Theorem states that if a countable first-order theory $T$ is $\kappa$-categorical for some uncountable cardinal $\kappa$, then it is $\lambda$-categorical for all uncountable cardinals $\lambda$. This reflects an underlying structural uniformity.

• $\omega$-Categoricity: By the Ryll-Nardzewski Theorem, a countable theory $T$ is ${\aleph }_0$-categorical if and only if $S_n(T)$ is finite for every $n<\omega$. In such theories, every type is isolated (the "predictable" points in the topology).

• Saturation: A model is $\kappa$-saturated if it realizes all types over sets of size $<\kappa$. Uncountably categorical theories are characterized by their saturated models in uncountable cardinalities.

• Atomic Models: Atomic models are models that omit all non-isolated types. They are the "simplest" possible structures in a theory. In theories with a dense set of isolated types, we can often construct an atomic model by realizing only those types that are "forced" by the theory.

The interplay between these concepts is fundamental: theories with few types in their Stone space (e.g., ${\aleph }_0$-categorical theories) are highly structured, while theories with complex, non-isolated types (e.g., those with the Independence Property or Order Property) lead to a wide spectrum of non-isomorphic models. By studying $S_n(T)$, we do not just study sets of formulas; we study the categorical limits of the theory itself.