REVIEW 5 minor 2 references
The Complexity of the Set of Validities of a Theory
T0 review · 0 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper proves that the schemata valid in every decidable theory form a Π3-complete set, settling a question posed in 1960.
desk verdict Settles Vaught's 1960 question with a correct Π3-completeness proof; abstract overstates scope from complete to all decidable theories. 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 schematic language S, which has no identity, constants, or function symbols, but has countably many relation symbols of each arity. A sentence φ of S belongs to V(T) exactly when every substitution of L-formulas for the relation symbols of φ produces a member of T. For ℵ0-categorical theories, the load-bearing invariant is the Ryll-Nardzewski function RN_T(n), the number of complete n-types consistent with T; Theorem 3.8 proves V(T) is Turing equivalent to RN_T by encoding 'there are at least k n-types' as a validity. For the V_dec theorem, the mechanism is the translation θ ↦ θ*, where θ* adds a conjunct stating that ≈ is a congruence with respect to R and replaces identity and the edge relation of a graph sentence θ by ≈ and R. Lemma 4.7 shows θ has a decidable complete extension iff ¬θ* is not in V_dec, turning the Π3-complete index set of trees with no computable path into a many-one reduction to V_dec.
What would settle it
Take a complete decidable non-ℵ0-categorical theory such as Presburger arithmetic and determine its validity set: Theorem 3.13 predicts it is Π1-complete, so a proof that it is decidable, or merely co-c.e. but not Π1-complete, would falsify the paper's dichotomy. For the main V_dec theorem, one could test Lemma 4.7 on a specific graph sentence with no decidable complete extension: if the translated sentence ¬θ* turns out to be a validity of some decidable theory, the reduction from index sets would fail.
Extended reading notes
Core claim
For a theory T, V(T) is defined as the set of sentences in a purely schematic language—relation symbols only, no identity—such that every simultaneous substitution of T-formulas for the relation symbols yields a theorem of T. The paper proves a trichotomy for decidable T: V(T) is always Π1; when T is complete and ℵ0-categorical, the Turing degree of V(T) is exactly the degree of the function counting consistent n-types; when T is complete, decidable, and not ℵ0-categorical with infinite models, V(T) is Π1-complete. The main result is that the intersection V_dec of V(T) over all decidable T is Π3-complete, proved by reducing to V_dec the Π3-complete problem of whether a Π1 class has no computable path. This gives the exact position of the common validities in the arithmetical hierarchy, answering the 1960 question.
Load-bearing premise
The proof that the common validities are Π3-complete relies on a deep earlier representation theorem: every computably enumerable tree of paths can be matched, degree for degree, to the decidable complete extensions of a single finitely axiomatized graph theory, and if that theorem is false or misapplied the main hardness reduction has no foundation.
Editorial extensions
If this is right
- No decidable, c.e., or co-c.e. procedure can decide which schemata are valid in every decidable theory; the problem is exactly as hard as the most difficult arithmetical statements at the third level.
- For a complete decidable ℵ0-categorical theory, the validity set is decidable exactly when the Ryll-Nardzewski function is computable, and its Turing degree can be any c.e. degree below the halting problem.
- For a complete decidable non-ℵ0-categorical theory, the validity set is as hard as the complement of the halting problem, so such theories never have decidable validity sets.
- If a complete theory is not ℵ0-categorical and lacks the strict order property, its validity set computes the halting problem even when the theory itself is only computable from some non-trivial degree d.
- The common validities V_dec remain Π3-complete even when the intersection is restricted to decidable complete theories, so completeness is a robust phenomenon, not an artifact of incomplete theories.
Reading between the lines
- The paper's distinction between Ryll-Nardzewski counts and full validity sets suggests that finer invariants, such as the orbit structure of n-tuples under automorphisms, may be needed to characterize V(T) completely; the random graph versus random tournament example points in that direction.
- A natural next problem is the analogous set V_fa for finitely axiomatizable complete theories; the paper notes it remains open, and the same Π3 upper bound suggests the method might either prove it Π3-complete or locate a genuine drop in complexity.
- Theorem 5.4 shows some non-ℵ0-categorical theories have weak validity sets, while Theorem 5.3 shows NSOP theories force high complexity; whether the strict order property is exactly the dividing line for when V(T) computes ∅′ is a testable conjecture that the paper leaves implicit.
- One could attempt to classify the degrees of V(T) for undecidable theories between the PA-degree lower bound and the ∅′-computing cases, looking for a full analogue of the c.e.-degree spectrum obtained in the ℵ0-categorical case.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper introduces the notion V(T), the set of first-order schemata all of whose substitution instances are theorems of a theory T. It shows that for decidable T, V(T) is Π^0_1 and strictly contains the set V of logically valid schemata. For complete decidable theories, it gives a dichotomy: if T is ℵ0-categorical, V(T) is Turing equivalent to the Ryll-Nardzewski function, which can realize any c.e. degree in [0,0'] by a result of Schmerl; if T is not ℵ0-categorical, V(T) is Π^0_1-complete. The main theorem is that the intersection V_dec of V(T) over all decidable T is Π^0_3-complete, answering a question of Vaught from 1960. The paper also studies undecidable theories, showing that V(T) has PA degree when T is non-ℵ0-categorical and complete, and that for NSOP theories it can compute ∅'.
Significance. The main result, the Π^0_3-completeness of V_dec, is a substantial and likely correct resolution of a longstanding question. The proof is coherent: it combines the Hanf/Peretyat'kin coding of Π^0_1 classes by finitely axiomatized graph theories with a clean lemma (Lemma 4.7) that relates decidable complete extensions to membership in V_dec. The paper is transparent about its external dependencies and does not rely on circular reasoning. The apparent bound issue in Theorem 3.8 raised in the reading notes does not land: with 2^k predicate variables, the relevant count is the number of definable n-relations, 2^{RN_T(n)}, so the condition RN_T(n)<k is correct. The classification for complete decidable theories is also interesting, though the manuscript overstates its scope by omitting the word 'complete' in the abstract.
minor comments (5)
- [Abstract and Section 3] The abstract and introduction state that the paper provides a complete model-theoretic characterization of V(T) for decidable theories T, but the results in Section 3 apply only to complete decidable theories. Theorem 3.8 covers complete ℵ0-categorical theories and Theorem 3.13 covers complete non-ℵ0-categorical theories, while Theorem 3.1 is only an upper bound for arbitrary decidable theories. The claims should be rephrased to say 'complete decidable theories'.
- [Theorem 3.4, proof] The displayed bound '2^{3n^2}' is inconsistent with the example of 8 formulas for n=2 variables; the bound should be replaced by a correct finite bound for the number of quantifier-free formulas up to equivalence.
- [Lemma 4.7] The right-to-left direction would benefit from an explicit description of the quotient construction that turns a model of the definable extension in (6) into a model of θ, together with a verification that the resulting complete L-theory is decidable.
- [Theorem 3.8, proof] There are several typographical slips in this proof, including 'V(t)' for 'V(T)' and the missing word in 'It follows at once that IfTis...'.
- [Corollaries 3.10 and 3.11] The phrases 'V(T) is in a' and 'RN_T is in a' should be 'has Turing degree a' for precision, since Schmerl's theorem and the equivalence are degree-theoretic.
Circularity Check
No significant circularity: the central Pi_3-completeness result is an external reduction via Hanf/Peretyat'kin and Gasarch-Martin, and the only self-citation is a non-load-bearing textbook pointer for PA degrees.
full rationale
Theorem 4.4 is proved by reducing the Gasarch-Martin Pi_3-complete set {e : T_e has no computable path} to V_dec. The reduction uses Theorem 4.5 (Hanf/Peretyat'kin), an external black box, and Lemma 4.7, which is proved in the paper and does not define V_dec in terms of the target property: its right-to-left direction constructs a complete decidable L-extension from a substitution instance, while its left-to-right direction is immediate from completeness and consistency. The Section 3 characterization uses the Ryll-Nardzewski function RN_T and proves V(T) ≡_T RN_T by explicit coding (Theorem 3.8), then uses Schmerl's external theorem (Theorem 3.9) to realize all c.e. degrees; no fitted parameter is renamed as a prediction. The single self-citation is footnote 5's reference to Downey-Hirschfeldt for background on PA degrees; the fact it supports (only c.e. PA degree is 0') is standard external mathematics and is not load-bearing. No equation in the paper equates a conclusion to its input by construction, so there are no circular steps.
Assumptions & free parameters
assumptions (10)
- standard math Godel completeness and Church-Turing undecidability: V is Sigma_1-complete.
- standard math Hilbert-Bernays completeness theorem: for PA, the schematic validities coincide with the pure validities.
- standard math Engeler/Ryll-Nardzewski/Svenonius: a complete theory is aleph_0-categorical iff there are finitely many n-types for each n.
- domain assumption Schmerl's theorem: every c.e. degree a in [0, 0'] is realized as the Ryll-Nardzewski degree of a complete decidable aleph_0-categorical theory.
- domain assumption Hanf/Peretyat'kin: complete extensions of a finitely axiomatized graph theory correspond to paths through an associated Pi_1 class.
- domain assumption Gasarch-Martin: the index set of Pi_1 classes with no computable path is Pi_3-complete.
- domain assumption Jockusch-Lerman-Soare-Solovay: n-CEA PA degrees compute 0'.
- domain assumption Scott Basis Theorem: every nonempty Pi_1 class has a member computable from each PA degree.
- standard math There exists a Turing machine whose output sets Z_0 and Z_1 are effectively inseparable.
- standard math The only c.e. PA degree is 0'.
Cite this review
Pith. "Pith review of The Complexity of the Set of Validities of a Theory." pith.science (2026). https://pith.science/paper/EIDOPLLI
@misc{pith2026250608901,
author = {Pith},
title = {Pith review of: The Complexity of the Set of Validities of a Theory},
year = {2026},
howpublished = {\url{https://pith.science/paper/EIDOPLLI}},
note = {Machine review of arXiv:2506.08901}
}
abstract
We study the collection of first-order logical schemata all of whose instances are theorems of a given theory $T$; we call these the validities of $T$ ($\mathsf{V}(T)$). It is easy to see that if $T$ is a decidable theory, then $\mathsf{V}(T)$ is distinct from the set of valid formulas of first-order logic as customarily understood. We provide a complete model-theoretic characterization of the complexity, in the sense of Turing degree, of $\mathsf{V}(T)$ for decidable theories $T$, and answer a question posed by Vaught in 1960 concerning the complexity of the collection of validities common to all decidable theories.
Reference graph
Works this paper leans on
-
[1]
Effectively decidable theories
Alan Cobham. Effectively decidable theories. InSummaries of talks at the Summer Institute of Symbolic Logic at Cornell University, volume 1, pages 391–395. 1957. Rodney G. Downey and Denis R. Hirschfeldt.Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer, 2010. Gary Ebbs and Warren Goldfarb. First-order logical valid...
work page 1957
-
[2]
Boston, Boston, MA, 1993. William Hanf. Model-theoretic methods in the study of elementary logic. In J. Addison, L. Henkin, and A. Tarski, editors,The Theory of Models, pages 132–145. North Holland, 1965. William Hanf. The Boolean algebra of logic.Bull. Amer. Math. Soc., 81(2):587–589, 1975. Carl G. Jockusch, Jr., Manuel Lerman, Robert I. Soare, and Rober...
work page 1993
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.