Complexity of Computable Transformations and Independence Exponents of Raw Projection Spectra

We study two finite relations underlying quantitative metamathematics. For a total computable map of Cantor space, the maximum same-length prefix-free complexity distortion equals, up to a uniform additive constant, the logarithm of the largest row or column degree of its finite prefix relation. Consequently uniform bounded distortion is equivalent to bounded prefix degrees. This differs sharply from pointwise preservation: one computable involution preserves every point’s complexity up to a point-dependent constant while attaining asymptotically maximal worst-case distortion. Separately, for arithmetic cell systems, provable cell pullback is equivalent to image conjugacy for every consistent finite extension of the base theory. Combining these gives a precise joint classification with distinct information and semantic conditions. For finite truth-pattern classes, the Sauer–Shelah inequality implies that projection entropy, maximal independent-coordinate size,coordinate-query Littlestone dimension, and Boolean free rank have the same normalized lower and upper exponents. We derive an existential criterion for raw saturation and exact deletion bounds. Finally, in the atomless Lindenbaum algebra of a consistent c.e. extension of PA, an exhaustive neutral coordinate list modulo equality and complementation has worst-subset surjectivity order eventually equal to one; no such complete representative list is c.e. These statements give classifications and method boundaries, not a determinationof the raw PA exponent.Keywords: Kolmogorov complexity; computable transformations; Stone duality; Lindenbaum algebra; VC dimension; Littlestone dimension; incompleteness.