Recursive Representations And Diagonalization: Keys To Infinite Hierarchies

Representing Infinite Sets with Recursion

Recursion is a powerful technique in mathematics and computer science that involves defining objects in terms of themselves. This self-referential capability allows recursive definitions to characterize objects that have potentially infinite size or unbounded extent. Two major applications of recursive representations are: (1) specifying infinite sets, and (2) defining computable functions over infinite domains.

Defining recursive representations

A set S is defined recursively if it contains a base element x, and for each element y in S, another element f(y) obtained by applying a recursion function f to y is also contained in S. For example, the set of natural numbers N = {0, 1, 2, 3,…} can be defined recursively as follows:

• 0 is in N (base case)
• If y is in N, then y+1 is in N (recursion step)

This captures the intuitive notion that each natural number begets the next through an act of recursive succession. Starting with 0, applying the successor function f(y) = y+1 generates the sequence of natural numbers without end.

Diagonalization for proving infinitude

How can we be sure that a recursively defined set is actually infinite? Diagonalization is a key technique for proving that certain recursive constructions necessarily produce infinite sets. The idea is to assume a putative listing of all elements in the set, and then construct another element not contained in that listing, thereby establishing its infinitude. Cantor’s elegant diagonal argument, described next, follows this approach.

Cantor’s diagonal argument

In 1891, Georg Cantor published a dramatic new proof that the set of real numbers R is larger than the set of natural numbers N, even though both are infinite. His famous diagonal argument relies on reductio ad absurdum. Assume that there exists a one-to-one mapping f from N to R. Use f to construct a list of real numbers such that the n-th row lists the decimal digits of f(n). Now create a new real number x whose n-th digit differs from the n-th digit of f(n). By construction, x differs from every number in the listing. This contradicts the initial assumption, thereby proving R is uncountably infinite.

Applying diagonalization to computational models

Cantor’s diagonal technique demonstrated that not all infinities are equal in size. This paved the way for many profound discoveries about the extent, dimensionality, and hierarchy of infinite sets. Today, diagonalization remains a versatile tool for analyzing the capabilities and limitations of computational models for infinite domains.

Turing machines and the halting problem

Alonzo Church and Alan Turing later adapted Cantor’s diagonal argument to prove key properties of abstract computing machines. Specifically, they showed the unsolvability of the halting problem. Given a description of a Turing machine M and input x, it is impossible to decide algorithmically whether M running on x will halt or run forever.

The recursion theorem

The proof relies on a self-referential construction known as Kleene’s recursion theorem. It states that for any computable function f, there exists an input x such that f(x) = Phi(x), where Phi is the interpreter for converting between numeric codes and Turing machine descriptions. Diagonalization is used to generate x by encoding an asymmetric halted/non-halted behavior toward f itself.

Infinite hierarchies from self-reference

The recursion theorem gives rise to infinitary hierarchies of formal systems based on self-referential capabilities. By iteratively augmenting a system to reason about itself, new tiers of expanded functionality are created without bound. Two important examples are the arithmetic and polynomial hierarchies central to computational complexity theory.

The arithmetic hierarchy

The arithmetic hierarchy classifies decision problems about integers based on quantifier alternation depth. Level 0 asserts existence of solutions. Level 1 alternates existential and universal quantifiers once. Level 2 does twice, and so on transfinitely. Each level contains problems not provably solvable at lower levels, yielding an infinite hierarchy of distinct classes.

The polynomial hierarchy

The polynomial hierarchy similarly classifies problems involving integer polynomials and quantifier alternation. It forms the backbone for studying efficient computation and complextity classes like P and NP. Over decades of research, only gradual progress has been made toward collapsing or separating this rich hierarchy of classes capturing higher and higher levels of nonlocal computation.

Towards the infinite frontier

In summary, diagonalization provides a versatile method for analyzing infinite computational models, while recursive representations give a means to formally characterize productive infinities through self-reference. Together, they point the way toward endlessly rising hierarchies of languages and problems whose complexities track into the transfinite.