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.

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.

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.

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.

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.

Relationships to Other Abstractions

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

• Cylindrification → is a kind of Redundancy → is a kind of Reserve → is a decomposition of Economy Of Force → is a kind of Allocation → presupposes Scarcity → is a decomposition of Constraint

Show alternative paths (11)

Neighborhood in Abstraction Space

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

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

• Numbering (Computability Theory) — 0.84
• Friedberg numbering — 0.83
• Pattern Language (Formal Languages) — 0.80
• Back-and-Forth Method — 0.80
• Double Recursion — 0.80

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