Skip to content

Cylindrification

Extend a numbering by pairing every original index with an ignored auxiliary coordinate, creating infinitely many computably organized names for each numbered object and converting ordinary reducibility comparisons into one-one form.

Version
v2 · 2026-09-06 · History
Domain-specific #
1615
Origin domain
mathematics
Subdomain
computability theory
Aliases
Cylindrification of a numbering, Numbering cylindrification, Cylinder construction for numberings

Core Idea

In computability-theoretic numbering theory, cylindrification turns a numbering \(\nu\) into a new numbering \(c(\nu)\) by adjoining an ignored coordinate. Using a fixed computable bijective pairing function \(\langle n,k\rangle\), define

\[ \operatorname{dom} c(\nu)=\{\langle n,k\rangle:n\in\operatorname{dom}\nu\},\qquad c(\nu)(\langle n,k\rangle)=\nu(n). \]

Every original index therefore expands into an infinite computable fiber of indices naming the same object. Ershov introduced the construction in the systematic theory of numberings.[1]

Structural Signature

  • A partial or total numbering \(\nu\) of a family of objects.
  • A declared computable pairing bijection on natural numbers.
  • An original index coordinate \(n\).
  • An auxiliary coordinate \(k\) that does not affect denotation.
  • A paired index \(\langle n,k\rangle\).
  • Domain replication across every admissible auxiliary value.
  • Constant denotation along each fiber over \(n\).
  • A computable embedding of original indices into the cylinder.
  • Infinite, effectively separable synonymous indices for each original index.
  • Interaction with many-one numbering reducibility \(\leq\).
  • Interaction with injective or one-one reducibility \(\leq_1\).
  • The characteristic comparison \(\nu\leq\mu\) iff \(c(\nu)\leq_1 c(\mu)\) under the standard setup.
  • A cylindric numbering characterized, up to the relevant equivalence, by matching its cylindrification.

What It Is Not

It is not geometric extrusion, cylindrical algebraic decomposition, cylindric algebra, or adding a genuinely new argument on which the numbered object depends. It does not change the numbered family and does not make an uncomputable translation computable. The auxiliary coordinate creates index multiplicity, not semantic content.

Scope of Application

Cylindrification is used in the structure theory of numberings, computable reducibilities, principal and precomplete numberings, and Rogers-style degree or semilattice analysis. It provides spare indices that allow translations to be made injective while preserving the objects denoted. Rogers supplies the classical framework of indices, acceptable systems, reducibilities, and computable pairing in which this maneuver is interpreted.[2]

Clarity

Specify the numbering convention, object family, partial-domain rule, pairing function, and reducibility notions. The equality \(c(\nu)(\langle n,k\rangle)=\nu(n)\) is the defining invariant. “Increases arity” means it increases index coordinates before pairing; the final numbering may still be presented as a unary partial map on natural numbers.

Manages Complexity

The construction trades unique or scarce indices for a controlled reservoir of synonyms. When a reduction would otherwise reuse target indices, the auxiliary coordinate can separate occurrences injectively without changing their denotations. Thus an ordinary translation problem can be lifted into a one-one translation problem with predictable bookkeeping.

Abstract Reasoning

  1. Fix a computable pairing bijection and projections.
  2. Start with the numbering \(\nu\) and its domain.
  3. Replace each index \(n\) by the fiber \(\{\langle n,k\rangle:k\in\mathbb N\}\).
  4. Define every member of the fiber to denote \(\nu(n)\).
  5. Embed \(n\) by a fixed auxiliary value, proving \(\nu\leq_1 c(\nu)\).
  6. Given a reduction between original numberings, use the auxiliary coordinate to separate target indices.
  7. Verify computability and injectivity of the lifted translation.
  8. Compare the cylindrified numberings under one-one reducibility.

Odifreddi gives the surrounding recursion-theoretic apparatus for pairing, indices, and reducibilities.[3]

Knowledge Transfer

The portable pattern is add a semantically inert coordinate to create an unlimited supply of distinguishable names, then use that naming slack to satisfy an injectivity constraint without changing the represented objects. The proposed immediate parent is Redundancy.

Examples

If \(\nu(7)=A\), then \(c(\nu)(\langle7,0\rangle)=c(\nu)(\langle7,1\rangle)=\cdots=A\). The paired indices are distinct natural numbers even though they denote the same object.

A computable reduction that maps several source indices to one target index can assign different auxiliary coordinates to those occurrences after cylindrification, producing an injective target-index map when the theorem's hypotheses hold.[4]

Structural Tensions

  • Extensional sameness versus intensional index distinctness.
  • Redundancy versus injectivity.
  • Unary coding versus multi-coordinate reasoning.
  • Choice of pairing convention versus invariant computability class.
  • Semantic preservation versus representational expansion.

Structural–Framed Character

Naming slack through an inert coordinate is structural. Effective numberings, pairing functions, index fibers, and reducibility are constitutive. The abstraction is domain-specific.

Structural Core vs. Domain Accent

The structural core is name + inert tag -> many distinct names for one referent -> injective routing capacity. The domain accent is computability-theoretic numbering reducibility.

Redundancy is the proposed immediate parent. Projection, Alias-to-Authority Mapping, Embedding, Pairing, and Template Instantiation are related primes.

The prospective queue contains one strict edge to prime:redundancy. No live DAG mutation is authorized.

Relationships to Other Abstractions

Local relationship map for CylindrificationParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.CylindrificationDOMAINPrime abstraction: Redundancy — is a kind ofRedundancyPRIME

Current abstraction Cylindrification Domain-specific

Parents (1) — more general patterns this builds on

  • Cylindrification is a kind of Redundancy Prime

    Redundancy is the proposed immediate parent.

Hierarchy paths (12) — routes to 8 parentless roots

Neighborhood in Abstraction Space

Cylindrification sits in a sparse region of the domain-specific corpus (86th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Formal Patterns & Indiscernibility (6 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With

  • Cylindrical algebraic decomposition.
  • Cylindric algebras in algebraic logic.
  • Geometric Cartesian product with a line.
  • A genuine extra argument that changes output.
  • Arbitrary duplicate labels without an effective pairing structure.
  • The assertion that cylindrification changes the numbered objects.

References

[1] Yuri L. Ershov, “Theorie der Numerierungen I,” Zeitschrift für mathematische Logik und Grundlagen der Mathematik 19, nos. 19–25 (1973): 289–388, doi:10.1002/malq.19730191901. registry ↩

[2] Hartley Rogers Jr., Theory of Recursive Functions and Effective Computability (McGraw-Hill, 1967; MIT Press reprint, 1987). registry ↩

[3] Piergiorgio Odifreddi, Classical Recursion Theory, vol. 1 (North-Holland, 1989), doi:10.1016/S0049-237X(08)70207-9. registry ↩

[4] Yuri L. Ershov, Theory of Numberings (Nauka, 1977), in Russian. registry ↩