REVIEW 3 major objections 4 minor 31 references
Tennenbaum-like theorems for cohesive powers
T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read A single computable graph is shown to have the property that every presentation of a cohesive power over any cohesive set computes 0'', and a single computable linear order is shown to have cohesive powers with no computable presentation.
desk verdict New constructions, but the main theorems have a gap: they assume presentations can find the element [f] without showing how. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the cohesive power Q_C A of a computable structure A over a cohesive set C: equivalence classes [φ] of partial computable functions φ:N→|A| that are defined on all but finitely many elements of C, with equality on a cofinite subset of C. It behaves like an ultrapower for Δ2 and Σ2 formulas, which is what lets combinatorial facts about the ground structure be lifted to the power. The graph theorem is carried by cycles: G is built so that a Σ3 set X is witnessed by vertices a_n lying on cycles of prescribed lengths, and X becomes c.e. in every presentation because the power inherits the Σ1 sentence that a given element lies on a cycle of length L. The linear-order theorem is carried by a generalized-sum decomposition: the order L is a sum of blocks whose cohesive power splits as Σ_k(S_k+R_k)+J, where each S_k is a uniquely identifiable finite-and-dense delimiter pattern, and P'' locates S_k to read the presence or absence of a maximum in the coding interval R_k; the successor relation in the coding orders is kept uniformly c.e. so that the relevant properties stay arithmetical and the double jump can decode a separating set.
What would settle it
A concrete test: in the cohesive power of the graph G over some cohesive set C, compare the existential first-order type of the element [f] represented by n↦a_n with that of the element represented by n↦a_{n+1}; if an automorphism of the cohesive power moves [f] to that other element, then no presentation can canonically single out [f], and the cycle-enumeration argument in the graph theorem is not presentation-independent.
Extended reading notes
Core claim
The central discovery is that the cohesive power construction has large, controllable encoding strength. For a particular computable graph G, a Σ3 set X is coded by arranging that k is in X exactly when the element [f], represented by the function n↦a_n, lies on a cycle of length ⟨k,ℓ⟩+3 for some ℓ; an ultraproduct-style preservation lemma for Σ1 formulas turns this into a criterion inside every cohesive power Q_C G, making X c.e. in every presentation and hence making 0'' computable from every presentation. For a computable linear order L, the proof decomposes the cohesive power into delimited blocks S_k+R_k+..., uses the double jump of a presentation to identify the delimiters, and reads off whether R_k has a maximum; the resulting set separates two disjoint Σ3 sets, so the double jump has PA-degree over 0''. Consequently no presentation of Q_C L is computable, and by the classical theorem on degrees of linear orders Q_C L has no Turing degree at all. If the cohesive set is restricted to Δ2, these lower bounds are sharp: the graph's cohesive powers have the exact degree 0''.
Load-bearing premise
The proofs that every presentation of a cohesive power computes 0'' assume that, given any presentation, one can recognize the element represented by the function n↦a_n, even though the graph has no constant symbols and other elements can lie on cycles of the same lengths.
Editorial extensions
If this is right
- For every Δ2 cohesive set C, the cohesive power of the graph G has degree exactly 0'': one can build a presentation from 0'', and no presentation avoids computing 0''.
- For every cohesive set C, the cohesive power of the linear order L admits no computable presentation; indeed its double jump always has PA-degree relative to 0''.
- The linear order L gives an example of a computable structure whose cohesive powers have no Turing degree, because a linear order has a degree if and only if it has a computable copy.
- Over Δ_k cohesive sets with k≥2, every cohesive power of a uniformly computable family has a Δ_{k+1} presentation, so the 0'' lower bound for the graph is the best possible among Δ2 cohesive powers.
Reading between the lines
- Editorial inference: the cycle-coding method for graphs is a template: replacing the particular Σ3 set X with another arithmetic set would produce a computable graph whose cohesive powers all compute that set's double jump, so the encoding strength of cohesive powers is likely tunable across the arithmetic hierarchy.
- Editorial inference: the linear-order theorem suggests that the absence of a computable presentation is a pervasive phenomenon for cohesive powers, not an artifact of coding-rich structures; one may ask whether similar delimiting techniques can realize prescribed degree spectra above 0'' for cohesive powers of linear orders.
- Editorial inference: the proof's reliance on identifying the element [f] in arbitrary presentations is the main point to probe; if [f] is not uniformly definable, the graph result may need a modified statement, for example adding a constant to the language or coding the identity into a definable substructure.
- Editorial inference: a testable strengthening would be to replace the graph by a finite-language or finitely branching version; the paper's use of infinitely many unary predicates in the initial encoding proposition is only for convenience, and a finite-language version may expose the limits of the method.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies cohesive powers of computable structures and proves Tennenbaum-like theorems. It constructs a computable graph G such that for every cohesive set C, every presentation of the cohesive power Q_C G computes 0''; for Δ2 cohesive sets this gives degree 0''. It also constructs a computable linear order L such that for every cohesive set C and every presentation P of Q_C L, the double jump P'' has PA-degree relative to 0'', so Q_C L has no computable presentation and, by Richter's theorem, no degree. Section 3 also contains a general encoding result (Proposition 3.1) and a Δ_{k+1} upper bound (Proposition 3.2), while Section 4 contains the main linear-order construction. Section 2 reviews cohesive powers, a Łoś theorem for them, and a commutation theorem for generalized sums.
Significance. If the proofs are completed, the results would be significant: they would show that cohesive powers of graphs can encode 0'' uniformly across all cohesive sets, and that a fixed computable linear order can have cohesive powers with no computable presentations, answering the paper's Question (3). The paper is self-contained, builds on but does not circularly use prior work, and supplies detailed constructions. The main obstacle is not the overall strategy but the absence of a uniform way to locate distinguished equivalence classes in arbitrary presentations; this issue affects all three central theorems.
major comments (3)
- [Section 3, Proposition 3.1] The proof says that every presentation P computes X because 'if a ∈ |P| is the element corresponding to [f]', then the set of σ with Uσ(a) consists exactly of the initial segments of X. However, the structure A has no constants and the proof gives no formula or search procedure that identifies the image of [f] in an arbitrary presentation. This is not a cosmetic issue: for every computable path Y there is a total computable φ with φ(n) ∈ U_{Y↾n} for all n, so the cohesive power realizes every computable path. Thus the path X is not unique, and the proof does not show how P can select an element whose path is X rather than some other realized path. The claim that every presentation of Q_C A computes X is therefore not established.
- [Section 3, Theorem 3.3] The proof asserts that X is c.e. in every presentation of Q_C G by enumerating the k for which there is a cycle of length ⟨k,ℓ⟩+3 containing the element corresponding to [f]. This presupposes that [f] is identifiable from the presentation, but the graph G has no constant symbols and no formula defining [f] is provided. The problem is concrete: the construction adds a cycle of length ⟨k,ℓ⟩+3 containing a0 for every k and ℓ, because the triple n=0 satisfies the condition unconditionally. Hence the element [c_{a0}] represented by the constant function with value a0 lies on cycles of every such length, while [f] may lie on none of them for k outside X. Consequently any enumeration that searches over all elements will enumerate all k regardless of X, and the proof gives no way to select [f] among the elements that lie on all such cycles. The claimed reduction of 0'' to every presentation is not justified, and this gap is load-bearing for Corollary 3.4.
- [Section 4, Theorem 4.3] The proof assumes that a presentation P of Q_C L contains elements a,b corresponding to the equivalence classes [f] and [g], and then uses the interval (a,b) as a copy of Q_C L_n. The linear order L has no constant symbols, and no formula or P-computable search is given to locate these two elements. Moreover, even if one could find some interval that is isomorphic to a cohesive product of the L_n's, the proof would need to show that it is the specific Q_C L_n from Theorem 4.1 rather than a product along a nonstandard index path. Without a method to identify the interval (a,b), the argument that P'' has PA-degree relative to 0'' is unsupported, so the Tennenbaum-like conclusion for Q_C L does not follow from the proof as written.
minor comments (4)
- [Throughout] The running head spells the first author's name as 'DA VID GONZALEZ'; this should be corrected to 'DAVID GONZALEZ'.
- [After Lemma 4.2] The paragraph following Lemma 4.2 refers to 'Theorem 4.2' where it should refer to 'Lemma 4.2'.
- [Proof of Theorem 3.3] The uses of Theorem 2.4 for the formulas Ψ_{k,ℓ} and ¬Ψ_{k,ℓ} are correct only if these formulas are uniformly decidable in the computable graph G; this should be stated explicitly for clarity.
- [Proof of Theorem 4.1] In the priority argument for the orders M_{n,6k+5}, the text says that once a column plays in some M_{n,6k+5}, it does not play again 'on account of column i'; the intended meaning is that a fixed column can play in only one n, but this is not stated precisely and should be clarified.
Circularity Check
No circular reduction: the graph and linear-order constructions are new and target external benchmarks; reliance on prior cohesive-power theorems is independent support, and the unproven assumption about locating [f] in arbitrary presentations is a correctness gap, not a circularity.
full rationale
The paper's central claims are proved by explicit constructions: Theorem 3.3 builds a computable graph whose cycle structure encodes a Sigma-3 set through the element [f], and Theorem 4.1 builds linear orders whose cohesive powers have delimited blocks coding an AB-separator. These are not fitted parameters renamed as predictions, and no construction or equation is defined in terms of the quantity it purports to establish. The paper does rely heavily on prior results on cohesive powers, especially [4, Theorems 2.4, 2.5, 4.5 and Lemma 4.2], and on [27] and [28]. Some of these authors overlap with the present authors, but the cited theorems are published, parameter-free, and do not assume the conclusions of this paper; they therefore function as independent support rather than a circular chain. The one genuinely problematic step is the assertion in Theorems 3.1, 3.3, and 4.3 that a presentation of a cohesive power contains a recognizable element corresponding to [f] (or endpoints [f] and [g]): the language has no constants for these elements and no search procedure is supplied, so the claimed enumeration of X or the interval (a,b) is not justified as an algorithm relative to an arbitrary presentation. This is a missing proof or soundness gap, not a circularity, because it does not make the theorem's conclusion equivalent to its hypotheses by construction. Hence the circularity score is 0.
Assumptions & free parameters
assumptions (3)
- domain assumption Existence of cohesive sets and of Δ2 cohesive sets.
- standard math Los theorem for cohesive powers applies to Σ2 and Π2 formulas.
- standard math There are disjoint Σ3 sets A and B whose separators are exactly the DNC2 functions relative to 0''.
Cite this review
Pith. "Pith review of Tennenbaum-like theorems for cohesive powers." pith.science (2026). https://pith.science/paper/GW3JMPWC
@misc{pith2026260804654,
author = {Pith},
title = {Pith review of: Tennenbaum-like theorems for cohesive powers},
year = {2026},
howpublished = {\url{https://pith.science/paper/GW3JMPWC}},
note = {Machine review of arXiv:2608.04654}
}
abstract
We investigate the encoding ability of the cohesive power construction. We compute a graph $\mathcal{G}$ where the cohesive power $\prod_C \mathcal{G}$ of $\mathcal{G}$ by any $\Delta_2$ cohesive set $C$ has degree $0''$. That is, $0''$ computes a presentation of $\prod_C \mathcal{G}$, and every presentation of $\prod_C \mathcal{G}$ computes $0''$. We also compute a linear order $\mathcal{L}$ where no cohesive power of $\mathcal{L}$ has a computable presentation. We accomplish this by ensuring that if $\mathcal{P}$ is a presentation of a cohesive power of $\mathcal{L}$, then $\mathcal{P}''$ has $\mathrm{PA}$-degree relative to $0''$.
Reference graph
Works this paper leans on
-
[1]
Christopher J. Ash, Carl G. Jockusch Jr., and Julia F. Knight,Jumps of orderings, Transactions of the American Mathematical Society319(1990), no. 2, 573–599
work page 1990
-
[2]
Christopher J. Ash and Julia F. Knight,Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000
work page 2000
-
[3]
Rumen Dimitrov,Cohesive powers of computable structures, Godishnik na Sofi ˘ ıskiya Universitet “Sv. Kliment Ohridski”. Fakultet po Matematika i Informatika. Annuaire de l’Universit´ e de Sofia “St. Kliment Ohridski”. Facult´ e de Math´ ematiques et Informatique99(2009), 193–201
work page 2009
-
[4]
Rumen Dimitrov, Valentina Harizanov, Andrey Morozov, Paul Shafer, Alexandra A. Soskova, and Stefan V. Vatev, On cohesive powers of linear orders, The Journal of Symbolic Logic88(2023), no. 3, 947–1004
work page 2023
-
[5]
Scott, and Stanley Tennenbaum,Models of arithmetic through function rings, Notices of the American Mathematical Society6(1959), no
Solomon Feferman, Dana S. Scott, and Stanley Tennenbaum,Models of arithmetic through function rings, Notices of the American Mathematical Society6(1959), no. 2, 173–174. Abstract 556-31
1959
-
[6]
Harvey Friedman and Lee Stanley,A Borel reducibility theory for classes of countable structures, The Journal of Symbolic Logic54(1989), no. 3, 894–914
work page 1989
-
[7]
Su Gao,Some dichotomy theorems for isomorphism relations of countable models, The Journal of Symbolic Logic66 (2001), no. 2, 902–922
work page 2001
-
[8]
ArXiv preprint arXiv:2411.12084
David Gonzalez and Matthew Harrison-Trainor,Scott spectral gaps are bounded for linear orderings, 2025. ArXiv preprint arXiv:2411.12084
arXiv 2025
Show all 31 references
-
[9]
2, 111–126
Yoram Hirschfeld,Models of arithmetic and recursive functions, Israel Journal of Mathematics20(1975), no. 2, 111–126
1975
-
[10]
Wheeler,Forcing, Arithmetic, Division Rings, Lecture Notes in Mathematics, vol
Yoram Hirschfeld and William H. Wheeler,Forcing, Arithmetic, Division Rings, Lecture Notes in Mathematics, vol. 454, Springer-Verlag, Berlin–New York, 1975
1975
-
[11]
Jockusch Jr
Carl G. Jockusch Jr. and Robert I. Soare,Degrees of orderings not isomorphic to recursive linear orderings, 1991, pp. 39–64. International Symposium on Mathematical Logic and its Applications (Nagoya, 1988)
1991
-
[12]
15, The Clarendon Press, Oxford University Press, New York, 1991
Richard Kaye,Models of Peano Arithmetic, Oxford Logic Guides, vol. 15, The Clarendon Press, Oxford University Press, New York, 1991
1991
-
[13]
Knight,Degrees coded in jumps of orderings, The Journal of Symbolic Logic51(1986), no
Julia F. Knight,Degrees coded in jumps of orderings, The Journal of Symbolic Logic51(1986), no. 4, 1034–1042
1986
-
[14]
Manuel Lerman,Recursive functions modulo co- r-maximal sets, Transactions of the American Mathematical Society 148(1970), 429–444
1970
-
[15]
,Degrees of Unsolvability: Local and Global Theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983
1983
-
[16]
McLaughlin,Embeddings of and into Nerode semirings, Israel Journal of Mathematics60(1987), no
Thomas G. McLaughlin,Embeddings of and into Nerode semirings, Israel Journal of Mathematics60(1987), no. 1, 65–88
1987
-
[17]
3, 197–209
,Some extension and rearrangement theorems for Nerode semirings, Zeitschrift f¨ ur Mathematische Logik und Grundlagen der Mathematik35(1989), no. 3, 197–209
1989
-
[18]
2, 143–191
,Sub-arithmetical ultrapowers: a survey, Annals of Pure and Applied Logic49(1990), no. 2, 143–191
1990
-
[19]
4, 287–296
,Recursive ultrapowers, simple models, and cofinal extensions, Archive for Mathematical Logic31(1992), no. 4, 287–296
1992
-
[20]
4, 431–435
,A note on effective ultrapowers: uniform failure of bounded collection, Mathematical Logic Quarterly39 (1993), no. 4, 431–435
1993
-
[21]
5-6, 379–384
, ∆1 ultrapowers are totally rigid, Archive for Mathematical Logic46(2007), no. 5-6, 379–384
2007
-
[22]
2, 470–486
Russell Miller,The∆ 0 2-spectrum of a linear order, The Journal of Symbolic Logic66(2001), no. 2, 470–486
2001
-
[23]
Antonio Montalb´ an,Computable Structure Theory: Within the Arithmetic, Perspectives in Logic, Cambridge University Press, 2021
2021
-
[24]
,Computable Structure Theory: Beyond the Arithmetic, Perspectives in Logic, Cambridge University Press, 2026
2026
-
[25]
4, 723–731
Linda Jean Richter,Degrees of structures, The Journal of Symbolic Logic46(1981), no. 4, 723–731
1981
-
[26]
Rosenstein,Linear Orderings, Pure and Applied Mathematics, vol
Joseph G. Rosenstein,Linear Orderings, Pure and Applied Mathematics, vol. 98, Academic Press, New York–London, 1982
1982
-
[27]
To appear in The Journal of Symbolic Logic
Paul Shafer,Effective powers of ω over∆ 2 cohesive sets and infiniteΠ 1 sets without∆ 2 cohesive subsets, 2023. To appear in The Journal of Symbolic Logic
2023
-
[28]
V. Yu. Shavrukov,R.e. prime powers and total rigidity, Advances in Mathematics360(2020), 106884, 50
2020
-
[29]
1, 150–161
Thoralf Skolem, ¨Uber die nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abz¨ ahlbar unendlich vieler aussagen mit ausschliesslich Zahlenvariablen, Fundamenta Mathematicae23(1934), no. 1, 150–161
1934
-
[30]
Soare,Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987
Robert I. Soare,Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987
1987
-
[31]
Stanley Tennenbaum,Non-Archimedean models for arithmetic, Notices of the American Mathematical Society6 (1959), no. 270. TENNENBAUM-LIKE THEOREMS FOR COHESIVE POWERS 15 Department of Mathematics, University of Notre Dame, Hurley Hall, 255 Hurley, Notre Dame, IN 46556, United S...
1959
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.