sp-Homogeneous Linear Orderings

David Gonzalez; Douglas Cenzer; Keng Meng Ng; Valentina Harizanov; Wesley Calvert

arxiv: 2509.25005 · v2 · submitted 2025-09-29 · 🧮 math.LO

sp-Homogeneous Linear Orderings

Wesley Calvert , Douglas Cenzer , David Gonzalez , Valentina Harizanov , Keng Meng Ng This is my paper

Pith reviewed 2026-05-18 12:17 UTC · model grok-4.3

classification 🧮 math.LO

keywords linear orderingssuccessor and predecessorsp-homogeneousrelative categoricitycomputability theorydescriptive set theoryΠ5^0-completeΣ6^0-complete

0 comments

The pith

Linear orderings expanded by successor and predecessor functions are always relatively Δ4 categorical when sp-homogeneous.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines linear orderings expanded by successor and predecessor functions, which model the relatively intrinsically computably enumerable information in these structures. It proves that sp-homogeneous orderings of this kind are always relatively Δ4 categorical. The authors classify exactly which ones are uniformly relatively Δ3 categorical and give a full classification of sp-homogeneity together with weak sp-homogeneity. They further establish that the set of sp-homogeneous linear orderings is Π5^0-complete while the weakly sp-homogeneous set is Σ6^0-complete, with proofs via both direct computability arguments and descriptive set theory.

Core claim

The successor and predecessor on linear orderings capture the relatively intrinsically computably enumerable information about orderings in much the same way that dependence captures that for vector spaces. In particular, the sp-homogeneous and weakly sp-homogeneous linear orderings are those which are (ultra-)homogeneous or weakly homogeneous with this additional structure. These orderings are always relatively Δ4 categorical, and the paper determines exactly which ones are (uniformly) relatively Δ3 categorical. It provides a classification for sp-homogeneity and weak sp-homogeneity, and shows that the set of sp-homogeneous linear orderings is Π5^0 complete while the set of weakly sp-homog-

What carries the argument

sp-homogeneity (and weak sp-homogeneity) for linear orderings expanded by successor and predecessor functions, which encodes homogeneity relative to the additional structure that captures intrinsic computable information about the ordering.

Load-bearing premise

Successor and predecessor functions capture the relatively intrinsically computably enumerable information about the ordering in the same way dependence does for vector spaces.

What would settle it

An sp-homogeneous linear ordering expanded by successor and predecessor that fails to be relatively Δ4 categorical, or whose set of realizations lies outside Π5^0, would falsify the main claims.

Figures

Figures reproduced from arXiv: 2509.25005 by David Gonzalez, Douglas Cenzer, Keng Meng Ng, Valentina Harizanov, Wesley Calvert.

**Figure 1.** Figure 1: A graph for ( 1 ln(2) ) (1−p) 2 (1−p)H( p 1−p ) from 0 to 1 2 with special attention on its maximum. Using the approximation for Binomial coefficients where the terms are linearly related, in this case by a limiting factor of p 1−p (see e.g. [17] Chapter 5.3), we get that R(m, p) = O ⎛ ⎝ ( 1 ln(2) ) (1−p)m 2 m(1−p)H( p 1−p )⎞ ⎠ = O ⎛ ⎝ (( 1 ln(2) ) (1−p) 2 (1−p)H( p 1−p ) ) m⎞ ⎠ . Where H(x) = −x log2 (x)… view at source ↗

read the original abstract

We study linear orderings expanded by functions for successor and predecessor. The successor and predecessor on linear orderings capture the relatively intrinsically computably enumerable information about orderings in much the same way that dependence captures that for vector spaces. In particular, the sp-homogeneous and weakly sp-homogeneous linear orderings are those which are (ultra-)homogeneous or weakly homogeneous with this additional structure. We demonstrate that these orderings are always relatively $\Delta_4$ categorical and determine exactly which ones are (uniformly) relatively $\Delta_3$ categorical. We also provide a classification for sp-homogeneity and weak sp-homogeneity. We establish that this is the best possible classification by showing that the set of sp-homogeneous linear orderings is $\Pi_5^0$ complete, and that the set of weakly sp-homogeneous linear orderings is $\Sigma_6^0$ complete. These results are obtained in two different ways, one using a hands-on computability theoretic approach and another using more abstract descriptive set theory.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper classifies sp-homogeneous linear orderings, shows they are all relatively Δ4 categorical with exact Δ3 cases, and proves Π5^0-completeness for the sp-homogeneous set plus Σ6^0 for the weakly sp-homogeneous set using two independent methods.

read the letter

Colleague, the main points are that this work gives a classification of sp-homogeneous and weakly sp-homogeneous linear orderings in the successor-predecessor expansion, proves all of them are relatively Δ4 categorical while pinning down the exact ones that are uniformly relatively Δ3 categorical, and establishes the sharp completeness results: the sp-homogeneous set is Π5^0-complete and the weakly sp-homogeneous set is Σ6^0-complete. They reach these via a direct computability argument and a separate descriptive set theory argument, which is a strength because the two routes do not share the same potential gaps. The classification itself looks clean and organizes the homogeneity notions in this expanded structure without obvious circularity. The dual proofs supply decent external grounding for the complexity claims. One soft spot is the opening modeling assumption that successor and predecessor capture the relatively intrinsically computably enumerable information in the same way dependence does for vector spaces. The abstract states this to motivate the definition, but if the full text does not include an explicit check that no other r.i.c.e. relations are missed or that the expansion does not add extraneous computable content, that could limit how directly the categoricity and complexity results transfer to plain linear orders. It is a minor rather than load-bearing issue if the later sections address it. This is a specialized piece for people working in computable model theory and homogeneity questions for orderings. It has enough concrete theorems and reproducible complexity results to deserve a serious referee rather than a desk reject, even if the motivation paragraph needs tightening. I would send it out for review.

Referee Report

1 major / 0 minor

Summary. The manuscript examines linear orderings expanded by successor and predecessor functions. It defines sp-homogeneous and weakly sp-homogeneous orderings as the (ultra-)homogeneous or weakly homogeneous structures in this expansion. The authors prove that all such orderings are relatively Δ₄ categorical, determine exactly which are uniformly relatively Δ₃ categorical, classify sp-homogeneity and weak sp-homogeneity, and establish that the set of sp-homogeneous linear orderings is Π₅⁰-complete while the set of weakly sp-homogeneous orderings is Σ₆⁰-complete. Results are obtained via both a hands-on computability-theoretic approach and a descriptive set-theoretic approach.

Significance. Assuming the modeling of relatively intrinsically computably enumerable relations via the sp-expansion is appropriate, the work provides a sharp analysis of categoricity degrees for linear orderings and demonstrates optimality through arithmetic-hierarchy completeness results. The dual proof strategies (computability-theoretic and descriptive set-theoretic) supply independent grounding and increase confidence in the classification. This contributes to computable model theory by clarifying the role of natural expansions in relative categoricity questions for linear orders.

major comments (1)

[Introduction] Introduction (opening paragraph): the assertion that successor and predecessor 'capture the relatively intrinsically computably enumerable information about orderings in much the same way that dependence captures that for vector spaces' is used to motivate the definitions of sp-homogeneous and weakly sp-homogeneous orderings, yet the manuscript provides no explicit verification or theorem confirming that every r.i.c.e. relation is uniformly definable from the sp-structure or that the expansion introduces no extraneous computable information. This modeling choice is load-bearing for the central claims on relative Δ₄/Δ₃ categoricity and the Π₅⁰/Σ₆⁰-completeness results, as both proof strategies operate inside the sp-expansion.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading, positive overall assessment, and constructive major comment. We address the point regarding the introductory motivation below, and we are prepared to revise the manuscript accordingly.

read point-by-point responses

Referee: [Introduction] Introduction (opening paragraph): the assertion that successor and predecessor 'capture the relatively intrinsically computably enumerable information about orderings in much the same way that dependence captures that for vector spaces' is used to motivate the definitions of sp-homogeneous and weakly sp-homogeneous orderings, yet the manuscript provides no explicit verification or theorem confirming that every r.i.c.e. relation is uniformly definable from the sp-structure or that the expansion introduces no extraneous computable information. This modeling choice is load-bearing for the central claims on relative Δ₄/Δ₃ categoricity and the Π₅⁰/Σ₆⁰-completeness results, as both proof strategies operate inside the sp-expansion.

Authors: We agree that the opening paragraph presents the analogy as motivation without a self-contained verification or dedicated theorem in the current manuscript. While the analogy is standard in the computable model theory literature on linear orders (where successor and predecessor are known to uniformly capture r.i.c.e. relations without adding extraneous computable structure), we acknowledge that an explicit reference or short explanatory remark would strengthen the exposition. The definitions of sp-homogeneous and weakly sp-homogeneous structures are given directly in terms of the expanded language, and all subsequent proofs (both the hands-on computability arguments and the descriptive-set-theoretic arguments) are carried out entirely inside the sp-expansion; thus the central classification, relative categoricity, and completeness results do not logically depend on the motivational sentence. Nevertheless, we will add a brief clarifying paragraph (with a pointer to the relevant background on r.i.c.e. relations for linear orders) to address the referee’s concern. revision: partial

Circularity Check

0 steps flagged

No significant circularity; results derived independently inside explicit sp-expansion

full rationale

The paper explicitly studies linear orderings expanded by successor and predecessor, defines sp-homogeneous and weakly sp-homogeneous as (weak) homogeneity in that expansion, and proves relative Δ4 categoricity, exact Δ3 cases, classification, and Π5^0/Σ6^0-completeness via two separate methods (computability-theoretic and descriptive set theory). No equations, definitions, or self-citations reduce any claimed result to a fitted input or prior self-result by construction. The analogy to dependence in vector spaces is presented as motivation for the modeling choice and does not appear in the formal derivation chain or completeness arguments.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard background axioms of linear orders and computability theory; the sp-homogeneous notion is defined by expanding the language with successor and predecessor, which is a modeling choice rather than a new invented entity.

axioms (2)

domain assumption Linear orderings expanded by successor and predecessor capture relatively intrinsically computably enumerable information analogously to dependence in vector spaces.
Invoked in the first paragraph to motivate the sp-homogeneous definition.
standard math Standard axioms and definitions of relative Δ_n categoricity and arithmetic hierarchy completeness.
Background results from computability theory used throughout.

pith-pipeline@v0.9.0 · 5716 in / 1547 out tokens · 40143 ms · 2026-05-18T12:17:32.197875+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We study linear orderings expanded by functions for successor and predecessor. The successor and predecessor on linear orderings capture the relatively intrinsically computably enumerable information about orderings in much the same way that dependence captures that for vector spaces.
IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean absolute_floor_iff_bare_distinguishability unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 3.6. (1) {e : L_e is sp-homogeneous} is Π₅⁰ complete.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[1]

Adams and D

F. Adams and D. Cenzer,Computability and categoricity of weakly ultrahomogeneous structures, Com- putability6(2017), 365–389

work page 2017
[2]

Adams, D

F. Adams, D. Cenzer, and S. Ng,Computability and categoricity of weakly homogeneous boolean algebras and Abelian p-groups, Aspects of Computation and Automata with Applications, World Scientific Press, Singapore, 2020, pp. 141–158

work page 2020
[3]

Ash and J

C. Ash and J. Knight,Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, no. 144, Elsevier, Amsterdam, 2000

work page 2000
[4]

C. J. Ash and J. F. Knight,Pairs of recursive structures, Annals of Pure and Applied Logic46(1990), no. 3, 211–234. MR 91b:03061

work page 1990
[5]

R. Chen, D. Gonzalez, and M. Harrison-Trainor,Optimal syntactic defintions of back-and-forth types, Submitted for publication

work page
[6]

Flajolet and R

P. Flajolet and R. Sedgewick,Analytic combinatorics, 1 ed., Cambridge University Press, Cambridge, 2009

work page 2009
[7]

Fraïssé,Theory of relations, vol

R. Fraïssé,Theory of relations, vol. 145, Elsevier, Amsterdam, 1986

work page 1986
[8]

Frolov and M

A. Frolov and M. Zubkov,On categoricity of scattered linear orders of constructive ranks, Archive for Mathematical Logic64(2024), no. 1, 279–297

work page 2024
[9]

Gonzalez and D

D. Gonzalez and D. Rossegger,Scott sentence complexities of linear orderings, The Journal of Symbolic Logic (2024), 1–30

work page 2024
[10]

Harris and A

K. Harris and A. Montalbán,Boolean algebra approximations, Transactions of the American Mathematical Society366(2014), no. 10, 5223–5256

work page 2014
[11]

A. H. Lachlan,Homogeneous structures, Proceedings of the International Congress of Mathematicians, vol. 1, American Mathematical Society, Providence, RI, 1986, p. 314–321

work page 1986
[12]

Marker,Model theory: an introduction, vol

D. Marker,Model theory: an introduction, vol. 217, Springer Science & Business Media, New York, 2002. HOMOGENEOUS LINEAR ORDERINGS 45

work page 2002
[13]

McCoy,Partial results in∆ 0 3-categoricity in linear orderings and Boolean algebras, Algebra and Logic41(2002), 295–305

C.F.D. McCoy,Partial results in∆ 0 3-categoricity in linear orderings and Boolean algebras, Algebra and Logic41(2002), 295–305

work page 2002
[14]

,∆ 0 2-categoricity in Boolean algebras and linear orderings, Annals of Pure and Applied Logic119 (2003), 85–120

work page 2003
[15]

Montalbán,Counting the back-and-forth types, Journal of Logic and Computation22(2012), 857–876

A. Montalbán,Counting the back-and-forth types, Journal of Logic and Computation22(2012), 857–876

work page 2012
[16]

,Computable Structure Theory: Within the Arithmetic, Perspectives in Logic, Cambridge University Press, Cambridge, 2021

work page 2021
[17]

Spencer and L

J.H. Spencer and L. Florescu,Asymptopia, Student Mathematical Library, American Mathematical Society, Providence, 2014

work page 2014
[18]

Torrezão de Sousa and J

S. Torrezão de Sousa and J. K. Truss,Countable homogeneous coloured partial orders, Dissertationes Math- ematicae455(2008), 48. MR 2440324 School of Mathematical and Statistical Sciences, Mail Code 4408, Southern Illinois Univer- sity, Carbondale, 1245 Lincoln Drive, Carbondale, Illinois 62901 Email address:wcalvert@siu.edu Department of Mathematics, Univ...

work page 2008

[1] [1]

Adams and D

F. Adams and D. Cenzer,Computability and categoricity of weakly ultrahomogeneous structures, Com- putability6(2017), 365–389

work page 2017

[2] [2]

Adams, D

F. Adams, D. Cenzer, and S. Ng,Computability and categoricity of weakly homogeneous boolean algebras and Abelian p-groups, Aspects of Computation and Automata with Applications, World Scientific Press, Singapore, 2020, pp. 141–158

work page 2020

[3] [3]

Ash and J

C. Ash and J. Knight,Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, no. 144, Elsevier, Amsterdam, 2000

work page 2000

[4] [4]

C. J. Ash and J. F. Knight,Pairs of recursive structures, Annals of Pure and Applied Logic46(1990), no. 3, 211–234. MR 91b:03061

work page 1990

[5] [5]

R. Chen, D. Gonzalez, and M. Harrison-Trainor,Optimal syntactic defintions of back-and-forth types, Submitted for publication

work page

[6] [6]

Flajolet and R

P. Flajolet and R. Sedgewick,Analytic combinatorics, 1 ed., Cambridge University Press, Cambridge, 2009

work page 2009

[7] [7]

Fraïssé,Theory of relations, vol

R. Fraïssé,Theory of relations, vol. 145, Elsevier, Amsterdam, 1986

work page 1986

[8] [8]

Frolov and M

A. Frolov and M. Zubkov,On categoricity of scattered linear orders of constructive ranks, Archive for Mathematical Logic64(2024), no. 1, 279–297

work page 2024

[9] [9]

Gonzalez and D

D. Gonzalez and D. Rossegger,Scott sentence complexities of linear orderings, The Journal of Symbolic Logic (2024), 1–30

work page 2024

[10] [10]

Harris and A

K. Harris and A. Montalbán,Boolean algebra approximations, Transactions of the American Mathematical Society366(2014), no. 10, 5223–5256

work page 2014

[11] [11]

A. H. Lachlan,Homogeneous structures, Proceedings of the International Congress of Mathematicians, vol. 1, American Mathematical Society, Providence, RI, 1986, p. 314–321

work page 1986

[12] [12]

Marker,Model theory: an introduction, vol

D. Marker,Model theory: an introduction, vol. 217, Springer Science & Business Media, New York, 2002. HOMOGENEOUS LINEAR ORDERINGS 45

work page 2002

[13] [13]

McCoy,Partial results in∆ 0 3-categoricity in linear orderings and Boolean algebras, Algebra and Logic41(2002), 295–305

C.F.D. McCoy,Partial results in∆ 0 3-categoricity in linear orderings and Boolean algebras, Algebra and Logic41(2002), 295–305

work page 2002

[14] [14]

,∆ 0 2-categoricity in Boolean algebras and linear orderings, Annals of Pure and Applied Logic119 (2003), 85–120

work page 2003

[15] [15]

Montalbán,Counting the back-and-forth types, Journal of Logic and Computation22(2012), 857–876

A. Montalbán,Counting the back-and-forth types, Journal of Logic and Computation22(2012), 857–876

work page 2012

[16] [16]

,Computable Structure Theory: Within the Arithmetic, Perspectives in Logic, Cambridge University Press, Cambridge, 2021

work page 2021

[17] [17]

Spencer and L

J.H. Spencer and L. Florescu,Asymptopia, Student Mathematical Library, American Mathematical Society, Providence, 2014

work page 2014

[18] [18]

Torrezão de Sousa and J

S. Torrezão de Sousa and J. K. Truss,Countable homogeneous coloured partial orders, Dissertationes Math- ematicae455(2008), 48. MR 2440324 School of Mathematical and Statistical Sciences, Mail Code 4408, Southern Illinois Univer- sity, Carbondale, 1245 Lincoln Drive, Carbondale, Illinois 62901 Email address:wcalvert@siu.edu Department of Mathematics, Univ...

work page 2008