{"id":"9782e948-f77a-4446-9a68-136a71bb3184","arxiv_id":"2608.04654","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A computable graph has cohesive powers of degree 0'' over Δ2 cohesive sets, and a computable linear order has cohesive powers with no computable presentation.","lead":"This paper studies cohesive powers, a computability-theoretic analogue of ultrapowers, and asks how much information they can encode. It claims to build a graph whose cohesive powers always compute the Turing degree 0'' and a linear order whose cohesive powers never have computable presentations.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.3 and 4.3 assume a presentation can locate the element [f] (and endpoints [f],[g]), but no formula or search procedure is provided; without this, the claimed c.e.-ness of 0'' in every presentation is not established.","rationale":"The reader's weakest_assumption pinpoints the same gap that I consider most load-bearing. The proof of Theorem 3.3 needs an effective way to refer to [f] in an arbitrary presentation of the cohesive power. Since the language of G has no constants and no defining formula is proposed, the predicate 'cycle containing the element corresponding to [f]' is not available to a procedure that receives only the atomic diagram of a presentation P. The X=∅ test makes the stakes clear: the construction gives [c_{a_0}] cycles of every length ⟨k,ℓ⟩+3, so an existential search over all elements would enumerate everything, not X. A separate, smaller issue is that the forward direction of Theorem 3.3 invokes Theorem 2.4 for a Σ1 formula; the stated theorem covers Σ2 (power-to-almost-all) and Π2 (almost-all-to-power), so the cited implication needs justification, though here it can be repaired by explicitly selecting computable witnesses for the cycles. This does not fix the parameter problem. Theorem 4.3 inherits the same issue through Lemma 4.2, since the endpoints [f] and [g] are not named in the language of L. The conditional verdict is therefore appropriate; the central constructions are plausible but the proofs as written do not establish that every presentation computes 0''.","tokens_in":19272,"tokens_out":16840,"duration_ms":161086,"concrete_test":"Take the graph G constructed in Theorem 3.3 for the Σ3 set X=∅, so Φ(k) is always false. In Q_C G, verify that [c_{a_0}] lies on cycles of every length ⟨k,ℓ⟩+3, while [f] lies on no such cycle. Then attempt to implement the enumeration of X using only the atomic diagram of an arbitrary presentation P, with no extra parameter. Since the two elements have different cycle-containment sets, the procedure must select [f]; check whether any first-order formula without parameters (or computable infinitary formula) defines [f] in Q_C G. If no such formula can be exhibited, the proof's enumeration step fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central reduction in Theorem 3.3 enumerates X in a presentation P of Q_C G as 'the k for which there is a cycle of length ⟨k,ℓ⟩+3 containing the element corresponding to [f].' But the language of G has no constants and the proof gives no definition of [f] in P. This is not a minor omission: for the graph built from X=∅, the constant function a_0 lies on a cycle of length ⟨k,ℓ⟩+3 for every k and ℓ (the construction adds such a cycle for n=0 unconditionally), while [f] lies on none. Thus any naive 'exists an element on such a cycle' predicate is satisfied for all k, and the intended set X is only obtained by selecting the non-definable element [f]. The same problem occurs in Theorem 4.3, where a presentation P of Q_C L is assumed to contain named elements a,b for [f] and [g]; the interval (a,b) is then used to compute a copy of Q_C L_n, but no way to find a,b from P is provided.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":19414,"tokens_out":14755,"duration_ms":161213,"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":[{"comment":"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":"Section 3, Proposition 3.1"},{"comment":"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":"Section 3, Theorem 3.3"},{"comment":"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.","section":"Section 4, Theorem 4.3"}],"minor_comments":[{"comment":"The running head spells the first author's name as 'DA VID GONZALEZ'; this should be corrected to 'DAVID GONZALEZ'.","section":"Throughout"},{"comment":"The paragraph following Lemma 4.2 refers to 'Theorem 4.2' where it should refer to 'Lemma 4.2'.","section":"After Lemma 4.2"},{"comment":"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.","section":"Proof of Theorem 3.3"},{"comment":"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.","section":"Proof of Theorem 4.1"}],"recommendation":"major_revision","confidential_remarks":"The gap about locating [f] and [g] in arbitrary presentations is common to Propositions 3.1, 3.3, and 4.3. The authors may be able to repair the statements by adding constants for the distinguished elements or by proving definability, but as written the central claims are not established. I recommend major revision rather than rejection because the constructions are substantial and may be salvageable with a modified framework."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The two constructions are new and worth a look: a graph whose cohesive powers all compute 0'' and a linear order with no computable cohesive-power presentations, answering an open question from the introduction. The background is thorough, the sequence of lemmas is well-organized, and Proposition 3.2 plus the construction in Theorem 4.1 are genuinely novel tools. The paper deserves attention from anyone working on cohesive powers or degree spectra of linear orders.\n\nThe soft spot is a real one, and it is load-bearing. In the proofs of Theorems 3.3 and 4.3, the authors assert that an arbitrary presentation contains a recognizable element corresponding to [f] (or the pair [f],[g]), but they provide no formula or search procedure to find it. The structures have no constants, so an isomorphism from the abstract cohesive power to a concrete presentation need not preserve any obvious marker for this element. The stress-test example is telling: when X=∅, the constant function a_0 lies on cycles of length ⟨k,l⟩+3 for every k,l, while [f] lies on none. So simply enumerating k based on the existence of a cycle of that length containing “the” element would fail if one picked the wrong element. The same issue appears in Theorem 4.3, where the interval (a,b) is only useful if a and b are identifiable in the presentation. Without that, the claims that every presentation computes 0'' and that P'' has PA-degree relative to 0'' are not established as written.\n\nThis is not a fatal flaw in the underlying ideas. Adding constants for these elements to the language, or proving that they are first-order definable in the cohesive power, would likely repair the proofs. But that is not a minor omission; it is a gap in the central derivations. The rest of the paper, especially the construction of the linear orders in Theorem 4.1 and the analysis of the shuffle sum, appears solid.\n\nFor peer review: I would send this to a competent referee. The constructions are interesting and probably correct in spirit, but the current version needs major revision to justify the identification of the key elements in arbitrary presentations. I would not accept it as is, but I would engage with it seriously rather than desk-reject.","headline":"New constructions, but the main theorems have a gap: they assume presentations can find the element [f] without showing how.","tokens_in":20005,"tokens_out":12953,"would_cite":true,"duration_ms":137252,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03D45","03D30","03C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["cohesive powers","computable structures","Turing degrees","double jump","PA-degree","linear orders","graphs","degree spectra"],"falsifier":"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.","tokens_in":18985,"feed_emoji":"♾️","tokens_out":10327,"duration_ms":108573,"temperature":0.7,"pith_summary":"The paper asks what information a cohesive power can encode. Cohesive powers are countable miniature ultrapowers built from a cohesive set and partial computable functions instead of from an ultrafilter and all functions; the authors show they are strong coding devices. They build a computable graph G such that, for every cohesive set C, every presentation of the cohesive power of G over C computes the Turing double jump 0'', and for Δ2-cohesive sets the power has degree exactly 0''. They then build a computable linear order L such that, for every cohesive set C, the double jump of every presentation of the cohesive power of L has PA-degree relative to 0'', so no cohesive power of L has a computable presentation. This converts the well-known no-computable-copy behavior of nonstandard models of arithmetic into a general property of the cohesive-power construction.","feed_headline":"All cohesive powers of one computable graph compute the double jump","feed_subtitle":"A companion linear order has cohesive powers with no computable presentation, extending a classical limitation of arithmetic.","key_machinery":"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.","core_discovery":"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''.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the cohesive-power definitions, the ultraproduct-style preservation lemmas used in both main proofs, the order-type analysis of cohesive powers of N, and the generalized-sum commutation theorem.","marker":"[4]"},{"why":"Introduces the cohesive power construction and its fundamental theorem, the foundation on which all later encodings rest.","marker":"[3]"},{"why":"Shows that a cohesive power of arithmetic has no computable presentation, the phenomenon that this paper extends from arithmetic to graphs and linear orders.","marker":"[28]"},{"why":"Gives the theorem that a linear order has a degree only if it has a computable copy; used to derive the no-minimum-degree corollary and to explain why the graph construction cannot be replaced by a linear order.","marker":"[25]"},{"why":"Supplies the delimiter-identification technique used in the linear-order theorem to locate the coding regions R_k inside the cohesive power.","marker":"[11]"},{"why":"Provides the no-computable-copy theorem for nonstandard models of arithmetic that motivates the whole investigation.","marker":"[12]"},{"why":"Gives the earlier classification of cohesive powers of computable copies of ω, the baseline result that the new linear-order theorem surpasses.","marker":"[27]"}],"fun_headline_variants":["Cohesive powers of one graph always compute the double jump","A single graph's cohesive powers have exact degree 0''","No cohesive power of this linear order is computable","One graph's cohesive powers code double jump, one order can't","Cohesive powers: a graph reaches 0'', an order avoids computability"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Cohesive powers of one graph always compute the double jump","A single graph's cohesive powers have exact degree 0''","No cohesive power of this linear order is computable","One graph's cohesive powers code double jump, one order can't","Cohesive powers: a graph reaches 0'', an order avoids computability"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000949,"raw_usage":{"total_tokens":4030,"prompt_tokens":907,"completion_tokens":3123,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":523,"completion_tokens_details":{"reasoning_tokens":3050}},"tokens_in":523,"tokens_out":3123,"duration_ms":25857,"temperature":1.0,"reasoning_tokens":3050,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:44:42.612225+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Soskova, and Stefan V","cited_arxiv_id":null,"evidence_quote":"Supplies the cohesive-power definitions, the ultraproduct-style preservation lemmas used in both main proofs, the order-type analysis of cohesive powers of N, and the generalized-sum commutation theorem."},{"cited_title":"Sv. Kliment Ohridski","cited_arxiv_id":null,"evidence_quote":"Introduces the cohesive power construction and its fundamental theorem, the foundation on which all later encodings rest."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows that a cohesive power of arithmetic has no computable presentation, the phenomenon that this paper extends from arithmetic to graphs and linear orders."},{"cited_title":"4, 723–731","cited_arxiv_id":null,"evidence_quote":"Gives the theorem that a linear order has a degree only if it has a computable copy; used to derive the no-minimum-degree corollary and to explain why the graph construction cannot be replaced by a linear order."},{"cited_title":"Jockusch Jr","cited_arxiv_id":null,"evidence_quote":"Supplies the delimiter-identification technique used in the linear-order theorem to locate the coding regions R_k inside the cohesive power."},{"cited_title":"15, The Clarendon Press, Oxford University Press, New York, 1991","cited_arxiv_id":null,"evidence_quote":"Provides the no-computable-copy theorem for nonstandard models of arithmetic that motivates the whole investigation."},{"cited_title":"To appear in The Journal of Symbolic Logic","cited_arxiv_id":null,"evidence_quote":"Gives the earlier classification of cohesive powers of computable copies of ω, the baseline result that the new linear-order theorem surpasses."}],"review_version":1}