Primitive recursive categoricity spectra of functional structures

This paper investigates the relationship between degrees of categoricity and their punctual (primitive recursive) analogues for functional structures, demonstrating that these notions coincide for non-$\Delta_{1}^{0}$-categorical injection structures but diverge for certain $\Delta_{1}^{0}$-categorical ones, while also establishing the existence of specific PR-degrees with distinct properties in every non-zero c.e. Turing degree.

The Gist

Imagine you have a giant, infinite library of books. Each book describes a specific pattern or structure (like a maze, a family tree, or a chain of dominoes). In the world of mathematics, these are called structures.

Now, imagine two librarians, Alice and Bob. They both have copies of the same book (the same structure), but they organized the shelves differently. Alice's books are on the left, Bob's on the right. The question is: How hard is it to figure out which book on Alice's shelf corresponds to which book on Bob's shelf?

This paper explores that question, but with two very specific rules about "how smart" the librarians are allowed to be.

The Two Types of Librarians

1. The Turing Librarian (The Standard): This librarian is very powerful. They can use a computer that can search forever if needed. They can solve almost any puzzle, even if it takes a long time. In math, we call this Computable.
2. The Primitive Recursive Librarian (The "Feasible" One): This librarian is much stricter. They are like a robot that can only do simple, repetitive tasks. They cannot search forever or look back at the infinite past to find a pattern. They must follow a strict, pre-defined recipe that finishes quickly. In math, this is called Primitive Recursive.

The paper asks: If we restrict our librarians to be the "Primitive Recursive" type, does the difficulty of matching the books change?

The Main Discovery: When Rules Change, Difficulty Changes

The authors studied a specific type of structure called an Injection Structure. Think of this as a set of chains.

• Some chains are finite (a short line of dominoes that stops).
• Some chains are infinite (a line of dominoes that goes on forever in one direction, like a snake).
• Some chains loop back on themselves (like a circle).

The Good News (The "Normal" Cases):
For most of these structures, the "Primitive Recursive" librarian and the "Turing" librarian agree on the difficulty.

• If the Turing librarian needs a super-computer to match the books, the Primitive Recursive librarian also needs a super-computer (of their own kind).
• If the Turing librarian can do it easily, the Primitive Recursive librarian can too.
• Analogy: Imagine matching two identical sets of Lego castles. If you can do it with a simple instruction manual, you can do it with a super-computer too. The "complexity" is the same for both.

The Bad News (The "Pathological" Case):
The authors found a weird, tricky structure where the two librarians disagree.

• There is a structure where the "Turing" librarian can easily match the books (it's "computably categorical").
• However, the "Primitive Recursive" librarian gets stuck! They cannot match the books using their strict, fast rules.
• Analogy: Imagine two identical mazes. A human (Turing) can walk through, look back, and find the path easily. But a robot (Primitive Recursive) that can only move forward and cannot remember where it turned left 10 steps ago gets lost. The robot needs a "degree of categoricity" (a measure of difficulty) that is higher than what the human needs.

The "Low" and "High" Degrees

The paper also looks at the "power levels" of these librarians.

1. Low for Punctual Isomorphism: These are librarians who are so "weak" or "simple" that even if you give them a super-powerful structure, they can't do any better than a basic librarian. They don't add any extra value.

   • Metaphor: Giving a calculator to someone who is already doing simple addition. The calculator doesn't help them solve the problem any faster than they could with their fingers.

2. Degrees of Punctual Categoricity: These are librarians who are exactly strong enough to solve a specific hard puzzle, but no stronger. They are the "Goldilocks" librarians—just right for a specific job.

   • Metaphor: A specific key that opens exactly one specific lock. It's not a master key (too powerful), and it's not a useless stick (too weak).

The Big Conclusion

The authors proved that within the world of "non-zero" complexity (meaning, puzzles that aren't already solved), you can always find:

• A librarian who is too weak to help (Low).
• A librarian who is perfectly tuned to solve a specific hard puzzle (Degree of Categoricity).

Why Does This Matter?

In the real world, we often care about efficiency. We don't just want to know if a problem can be solved; we want to know if it can be solved quickly and with limited resources.

This paper tells us that when we strip away the "infinite search" power of computers and look only at "feasible" (fast, simple) methods, the landscape of mathematical difficulty changes. Sometimes, a problem that looks easy to a powerful computer becomes impossible for a fast, simple robot. This helps us understand the gap between "theoretically possible" and "practically doable."

In short: The paper maps out the "difficulty levels" of matching mathematical patterns, showing that when you limit the tools to simple, fast ones, some puzzles become much harder than they appear to powerful computers.

Technical Summary

Here is a detailed technical summary of the paper "Primitive Recursive Categoricity Spectra of Functional Structures" by Nikolay Bazhenov, Heer Tern Koh, and Keng Meng Ng.

1. Problem Statement and Context

The paper investigates the algorithmic content of isomorphisms between structures, specifically within the framework of punctual structures.

• Background: In classical computable structure theory, the degree of categoricity of a structure $\mathcal{A}$ is the least Turing degree $\mathbf{d}$ capable of computing an isomorphism between any two computable presentations of $\mathcal{A}$.
• The Shift to Punctuality: The authors move from Turing degrees (computability) to PR-degrees (primitive recursive reducibility). A structure is punctual if its domain is $\omega$ and its operations/relations are uniformly primitive recursive. This models "feasible" computation by eliminating unbounded search (minimization).
• Core Question: What is the analogue of the degree of categoricity for punctual structures? Specifically, for a punctual structure $\mathcal{A}$, what is the set of PR-degrees ($PRCatSpec(\mathcal{A})$) that can compute isomorphisms (and their inverses) between any two punctual copies of $\mathcal{A}$?
• Key Definitions:
  • PR-Degree: $f \leq_{PR} g$ if $f$ is obtained from $g$ via a primitive recursive scheme.
  • PR-Categoricity Spectrum ($PRCatSpec(\mathcal{A})$): The set of PR-degrees $\mathbf{d}$ such that for any punctual $\mathcal{B} \cong \mathcal{A}$, there exists an isomorphism $f$ where $\mathbf{d} \geq_{PR} f \oplus f^{-1}$.
  • Cone($\Delta^0_\alpha$): The set of PR-degrees capable of computing all total $\Delta^0_\alpha$ functions.
  • Low for Punctual Isomorphism: A PR-degree $\mathbf{d}$ is "low" if any structure computable by $\mathbf{d}$ that is isomorphic to a punctual structure is actually punctually isomorphic to it (i.e., $\mathbf{d}$ adds no power to finding isomorphisms).

2. Methodology

The authors employ a combination of structural analysis and priority arguments (injury constructions) tailored to the constraints of primitive recursive functions.

• Structural Analysis (Injection Structures): The paper focuses on injection structures (structures with a single unary injective function). These are characterized by their orbits: finite cycles, $\omega$-chains (infinite forward), and $\zeta$-chains (bi-infinite).

  • The authors analyze how the number and type of orbits (finite, $\omega$, $\zeta$) dictate the complexity of isomorphisms.
  • They construct pairs of punctual structures $(\mathcal{A}, \mathcal{B})$ where the isomorphism must encode specific computational information (like the convergence of a function approximation) to force the isomorphism to be "hard" (high PR-degree).

• Priority Constructions:

  • Theorem 3.1 (Pathological Example): Uses a "pressing" strategy with a $\Delta^0_2$ oracle to construct a computably categorical injection structure that is not punctually categorical in the expected way. The construction involves enumerating finite orbits of specific sizes and using an oracle to delay enumeration in the "opponent's" structure, forcing the isomorphism to compute the oracle.
  • Theorem 4.1 & 4.2 (Degrees in c.e. Degrees): Uses a permitting technique combined with a "pressing" strategy on a structure with four unary functions ($S, P, R, C$).
    • Permitting: Ensures the constructed function $f$ is Turing equivalent to a given non-zero c.e. degree $\mathbf{d}$.
    • Pressing: Forces any isomorphism between the constructed structure and its copies to encode the values of a function $g$ (which computes the degree) by manipulating the "spine" and "tails" of the structure components.

3. Key Contributions and Results

A. Coincidence of Spectra for Most Injection Structures

The authors establish that for "standard" injection structures, the PR-categoricity spectrum aligns perfectly with the classical $\Delta^0_\alpha$-categoricity hierarchy.

• Theorem 2.2: If $\mathcal{A}$ is a relatively $\Delta^0_1$-categorical injection structure with at least one infinite orbit and infinitely many finite orbits, then $PRCatSpec(\mathcal{A}) = \text{Cone}(\Delta^0_1)$.
• Theorem 2.3: If $\mathcal{A}$ is relatively $\Delta^0_2$-categorical but not $\Delta^0_1$-categorical, then $PRCatSpec(\mathcal{A}) = \text{Cone}(\Delta^0_2)$.
• Theorem 2.4: If $\mathcal{A}$ is relatively $\Delta^0_3$-categorical but not $\Delta^0_2$-categorical, then $PRCatSpec(\mathcal{A}) = \text{Cone}(\Delta^0_3)$.
• Significance: This suggests a robust correspondence between the classical Turing degree hierarchy and the PR-degree hierarchy for these structures.

B. Existence of Pathological Structures

• Theorem 3.1: There exists a computably categorical injection structure $\mathcal{A}$ such that $PRCatSpec(\mathcal{A}) \not\subseteq \text{Cone}(\Delta^0_1)$.
• Implication: This contrasts with the results in Section 2. It shows that while many structures behave "nicely," there are computably categorical structures where the PR-categoricity spectrum is strictly more complex than the $\Delta^0_1$ cone. This highlights a divergence between computable categoricity and punctual categoricity.

C. PR-Degrees within c.e. Turing Degrees

The paper proves that the landscape of PR-degrees is rich even when restricted to non-zero c.e. Turing degrees.

• Theorem 4.1: In every non-zero c.e. Turing degree $\mathbf{d}$, there exists a PR-degree $\mathbf{f} \equiv_T \mathbf{d}$ that is low for punctual isomorphism.
• Theorem 4.2: In every non-zero c.e. Turing degree $\mathbf{d}$, there exists a PR-degree $\mathbf{g} \equiv_T \mathbf{d}$ that is a degree of punctual categoricity.
• Significance: This demonstrates that within any non-trivial level of computational power (c.e. degrees), one can find PR-degrees that are "useless" for finding isomorphisms (low) and PR-degrees that are "essential" (degrees of categoricity). This mirrors results in classical computable structure theory but adapts them to the primitive recursive setting.

4. Technical Significance

1. Bridging Feasibility and Computability: The paper provides a rigorous framework for understanding how the restriction to primitive recursive functions (feasibility) alters the classification of structural complexity. It shows that while the hierarchy often mirrors the Turing hierarchy, the "gaps" and "pathologies" behave differently.
2. Refining Categoricity: The distinction between "computably categorical" and "punctually categorical" is sharpened. The paper proves that a structure can be computably categorical (easy to isomorph in the Turing sense) yet have a PR-spectrum that is not contained in the $\Delta^0_1$ cone, implying that finding isomorphisms in the punctual setting can be significantly harder than in the general computable setting.
3. Construction Techniques: The development of the "pressing" strategy adapted for PR-degrees (using finite delays and specific orbit sizes to encode information) is a novel contribution to the field of punctual structures. The use of "tails" and "spines" with rigid properties (Theorem 4.2) allows for the precise encoding of Turing degrees into PR-degrees.

5. Conclusion

The paper successfully extends the theory of degrees of categoricity to the realm of primitive recursive structures. It establishes that for a broad class of injection structures, the PR-categoricity spectrum coincides with the $\Delta^0_\alpha$ cones, but also constructs counterexamples showing that this is not universal. Furthermore, it proves the existence of "low" and "categorical" PR-degrees within every non-zero c.e. Turing degree, demonstrating the richness and complexity of the PR-degree structure in the context of isomorphism problems.