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
v3 · 2026-09-19 · History
Domain-specific #
1615
Domain group
Formal Sciences
Origin domain
Mathematics
Subdomain
Computability Theory → Mathematics
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]

How would you explain it like I'm…

Endless Name Tags

Suppose every toy in a box has one number tag, like "toy 3." Cylindrification gives each toy endless tags instead: "toy 3, copy 0," "toy 3, copy 1," "toy 3, copy 2," and on and on. The copy number is ignored, so every one of those tags still means the very same toy.

Infinite Names for Each Thing

In computer science math, a numbering is a way of naming objects with whole numbers, like giving each program or set a number. Cylindrification takes a numbering and gives every object infinitely many new names. It does this by pairing each old number with an extra number that is simply ignored: the pair (n, k) names the same object as n did, for every k. A fixed, computable rule turns each pair into a single whole number. So each old name grows into an endless family of names for the same thing.

Numbering with an Ignored Coordinate

In computability theory, a numbering ν assigns objects to natural-number indices. Cylindrification builds a new numbering c(ν) by adding an ignored extra coordinate. Using a fixed computable pairing function that turns a pair (n, k) into a single number ⟨n, k⟩ and back, the new numbering is defined on ⟨n, k⟩ exactly when n was a valid index, and c(ν)(⟨n, k⟩) = ν(n). The second coordinate k has no effect on which object is named. So each original index n becomes an infinite, computable 'fiber' of indices ⟨n, 0⟩, ⟨n, 1⟩, ⟨n, 2⟩, …, all naming the same object. Ershov introduced this construction as part of his systematic theory of numberings.

 

In the theory of numberings, cylindrification transforms a numbering ν into c(ν) by adjoining a coordinate that the naming ignores. Fix a computable bijective pairing function ⟨n, k⟩. Then dom c(ν) = {⟨n, k⟩ : n ∈ dom ν} and c(ν)(⟨n, k⟩) = ν(n). Each original index n thus expands into the infinite computable fiber {⟨n, k⟩ : k ∈ ℕ} of indices naming the same object, while the set of named objects is unchanged. The construction depends on the chosen pairing function and preserves the domain condition: ⟨n, k⟩ is an index exactly when n was. Ershov introduced it within his systematic theory of numberings, where it provides a canonical way to give every named object infinitely many computably organized names.

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.

This entry is a kind of Redundancy.

Redundancy is the broader abstraction this entry instantiates. Projection, Alias-to-Authority Mapping, Embedding, Pairing, and Template Instantiation are related primes.

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) — outgoing typed relations

  • Cylindrification is a kind of Redundancy Prime

    Redundancy is the broader abstraction this entry instantiates.

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 — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25

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).not authoritative 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 ↩