Hostname: page-component-74656f9884-skzmx Total loading time: 0 Render date: 2026-11-06T07:39:23.219Z Has data issue: false hasContentIssue false
  • English
  • Français

K. J. Khoo, H. T. Koh, K. M. Ng. A discrete linear order with non-dense punctual degrees. Theoretical Computer Science, vol. 1047 (2025), Paper no. 115324, 20 pp. - N. Bazhenov, K. M. Ng, L. S. Mauro, A. Sorbi. Primitive recursive equivalence relations and their primitive recursive complexity. Computability, vol.11, nos. 3-4 (2022), pp. 187–221. - B. S. Kalmurzayev, N. A. Bazhenov, A. M. Iskakov. Computably enumerable equivalence relations via primitive recursive reductions, Journal of Logic and Computation, vol. 35, no. 2 (2024), Paper no. exad082, 31 pp.

Review products

K. J. Khoo, H. T. Koh, K. M. Ng. A discrete linear order with non-dense punctual degrees. Theoretical Computer Science, vol. 1047 (2025), Paper no. 115324, 20 pp.
N. Bazhenov, K. M. Ng, L. S. Mauro, A. Sorbi. Primitive recursive equivalence relations and their primitive recursive complexity. Computability, vol.11, nos. 3-4 (2022), pp. 187–221.
B. S. Kalmurzayev, N. A. Bazhenov, A. M. Iskakov. Computably enumerable equivalence relations via primitive recursive reductions, Journal of Logic and Computation, vol. 35, no. 2 (2024), Paper no. exad082, 31 pp.

Published online by Cambridge University Press:  24 April 2026

Ellen Hammatt
Ellen Hammatt*
Affiliation:
Institut für Diskrete Mathematik und Geometrie,TU Wien, Wiedner Hauptstrasse 8–10/104, 1040 Wien, Austria. E-mail: ellen.hammatt@tuwien.ac.at
Rights & Permissions [Opens in a new window]

Abstract

An abstract is not available for this content. As you have access to this content, full HTML content is provided on this page. A PDF of this content is also available in through the ‘Save PDF’ action button.

Information

Type
Review
Information
Bulletin of Symbolic Logic , Volume 32 , Issue 3 , September 2026 , pp. 487 - 490
Check for updates
Copyright
© The Author(s), 2026. Published by Cambridge University Press on behalf of The Association for Symbolic Logic

The articles under review contribute to punctual structure theory and, more specifically, to the study of various degree structures formed by primitive recursive reductions. Punctual structure theory is the systematic study of presentations with domain $\mathbb {N}$ double struck upper N and primitive recursive functions and relations. This systematic study began in Kalimullin, Melnikov, and Ng, Algebraic structures computable without delay, Theoretical Computer Science , vol. 674 (2017), pp. 73–98, inspired by the previous definition of primitive recursive presentations introduced by Malcev. We highlight that the inverse of a primitive recursive function may not be primitive recursive. Therefore, in contrast to computable isomorphisms, the notion of primitive recursive isomorphism induces a reduction of punctual presentations rather than an equivalence relation. All three articles under review study the degree structure induced by some primitive recursive reduction but vary in the exact form of this reduction as well as the set of objects the reduction is applied to. These structural properties include density and lattice properties. The second and third articles consider primitive recursive versions of Ceers, that is, the degree structure obtained by considering the class of computably enumerable equivalence relations under the reduction $\leq $ less than or equals defined by $R\leq S$ upper R less than or equals upper S if there is a computable f such that $x R y$ x upper R y if and only if $f(x) S f(y)$ f left parenthesis x right parenthesis upper S f left parenthesis y right parenthesis for all $x,y$ x comma y .

In A discrete linear order with non-dense punctual degrees, Khoo, Koh, and Ng consider the degree structure induced by considering the collection of punctual presentations of a fixed structure $\mathcal {A}$ script upper A under primitive recursive isomorphism. This is called the punctual degrees of $\mathcal {A}$ script upper A (notated as PR( $\mathcal {A}$ script upper A )). In particular, they show that the punctual degrees of $D=\zeta +\zeta ^2+\dots $ upper D equals zeta plus zeta squared plus ellipsis , where $\zeta =(\mathbb {Z},<)$ zeta equals left parenthesis double struck upper Z comma less than right parenthesis , are not dense. Initially, results were accumulated showing that punctual degrees of various structures were dense, leading to an initial conjecture that all structures have dense punctual degrees. This conjecture was found to be false. Now there is an ongoing project to understand structures with non-dense punctual degrees. This article contributes significantly to this area by giving another natural structure with non-dense punctual degrees. Moreover, it is a discrete linear order, showing that the density of $\eta $ eta is not the ‘cause’ of the non-density of PR $(\eta )$ left parenthesis eta right parenthesis ( $\eta =(\mathbb {Q},<)$ eta equals left parenthesis double struck upper Q comma less than right parenthesis is another natural example of a structure with non-dense punctual degrees). No sufficient conditions have been obtained yet for the non-density of punctual degrees in any natural classes. There are also plenty of open questions for the density of punctual degrees. For example, in this article, the authors leave open the question of whether the punctual degrees of $\zeta ^k$ zeta Superscript k for $k>1$ k greater than 1 or $\zeta \cdot \omega $ zeta dot omega are dense.

Primitive recursive equivalence relations and their primitive recursive complexity considers the punctual version of this degree structure, Peq. This is the degree structure consisting of punctual equivalence relations under a primitive recursive reduction $\leq _{pr}$ less than or equals Subscript p r Baseline defined by $R\leq _{pr} S$ upper R less than or equals Subscript p r Baseline upper S if there is a primitive recursive f such that $xRy$ x upper R y if and only if $f(x)Sf(y)$ f left parenthesis x right parenthesis upper S f left parenthesis y right parenthesis for all $x,y$ x comma y . We note that all computable equivalence relations have a punctual presentation, and therefore every computable equivalence relation appears in this degree structure. However, the objects are all punctual presentations and hence form a subset of the computable presentations. We also highlight that Peq is different from considering the punctual degrees of a fixed equivalence relation PR $(E)$ left parenthesis upper E right parenthesis where only punctual presentations of a fixed equivalence relation are considered and reductions are primitive recursive isomorphisms. Since this is the first time this degree structure has been considered, the authors explore the basic features of Peq. They show that Peq is a dense distributive lattice, unlike the classical Ceers, which is neither an upper or a lower semilattice. Additionally, each degree in Peq is join-reducible, and every degree below the top is meet-reducible. Unlike Ceers, every punctual equivalence relation is pr-equivalent to one of some normal form related to membership in a primitive recursive set. In the study of the classical Ceers, light and dark ceers are studied, that is, the equivalence relations R such that $R \geq _c Id$ upper R greater than or equals Subscript c Baseline upper I d and $R\perp _c Id,$ upper R up tack Subscript c Baseline upper I d comma respectively. However, in the setting of Peq, the authors show that $Id$ upper I d is the maximum degree and hence Peq has neither light nor dark degrees. While Peq seems particularly well-behaved compared to Ceers, it also has some surprising properties that show its intricacies. For example, not every interval embeds the diamond; moreover, there is a characterisation based on the complexity of primitive recursive sets. The authors also show that Peq is not rigid or homogeneous. They also consider the properties of lower cones of degrees in Peq and show that no proper lower cone is equivalent to the whole of Peq and provide a sufficient condition for the lower cones of two degrees to be isomorphic. Primitive recursive equivalence relations and their primitive recursive complexity concludes with several open questions, including whether there are incomparable degrees with non-isomorphic lower cones, whether there are continuum many automorphisms of Peq and whether the theory of Peq is decidable.

In Computably enumerable equivalence relations via primitive recursive reductions, the authors take a different approach to studying primitive recursive versions of Ceers. The main focus of the article is to use the primitive recursive reduction in Primitive recursive equivalence relations and their primitive recursive complexity but consider this reduction on Ceers rather than restricting this class. Throughout the article, the authors also investigate some other related degree structures including $(\textbf {CompEq},\leq _{pr})$ left parenthesis bold CompEq comma less than or equals Subscript p r Baseline right parenthesis , $(\textbf {FinEq},\leq _{pr})$ left parenthesis bold FinEq comma less than or equals Subscript p r Baseline right parenthesis , $(\textbf {Ceprs},\leq _{pr}),$ left parenthesis bold Ceprs comma less than or equals Subscript p r Baseline right parenthesis comma and $(\textbf {Celps},\leq _{pr})$ left parenthesis bold Celps comma less than or equals Subscript p r Baseline right parenthesis . These are the degree structures under $\leq _{pr}$ less than or equals Subscript p r Baseline -reduction of computable equivalence relations, computable equivalence relations with only finitely many classes, c.e. preorders and c.e. linear preorders, respectively. As in the classical case, the authors show that $(\textbf {Ceers},\leq _{pr})$ left parenthesis bold Ceers comma less than or equals Subscript p r Baseline right parenthesis is neither an upper or a lower semilattice. However, a structural difference between Ceers and $(\textbf {Ceers},\leq _{pr})$ left parenthesis bold Ceers comma less than or equals Subscript p r Baseline right parenthesis is highlighted by considering light and dark ceers. That is, every dark ceer has an infimum under $\leq _{pr}$ less than or equals Subscript p r Baseline with a dark ceer as well as a light one. In the case of computable reduction, a dark ceer does not have an infimum under $\leq _c$ less than or equals Subscript c Baseline with any incomparable dark ceer. Since $(\textbf {Ceers},\leq _{pr})$ left parenthesis bold Ceers comma less than or equals Subscript p r Baseline right parenthesis gives this finer look into the classical Ceers, the authors consider the structure under $\leq _{pr}$ less than or equals Subscript p r Baseline within $\leq _c$ less than or equals Subscript c Baseline -degrees. They show that within every $\leq _c$ less than or equals Subscript c Baseline -degree there are at least two $\leq _{pr}$ less than or equals Subscript p r Baseline -degrees and give a sufficient condition for when a $\leq _c$ less than or equals Subscript c Baseline -degree contains an infinite descending chain and a sufficient condition for when a $\leq _c$ less than or equals Subscript c Baseline -degree contains an infinite anti-chain. The authors also show that there are two $\leq _{pr}$ less than or equals Subscript p r Baseline -incomparable degrees in $(\textbf {FinEq},\leq _{pr})$ left parenthesis bold FinEq comma less than or equals Subscript p r Baseline right parenthesis , $(\textbf {CompEq},\leq _{pr})\setminus (\textbf {FinEq},\leq _{pr}),$ left parenthesis bold CompEq comma less than or equals Subscript p r Baseline right parenthesis minus left parenthesis bold FinEq comma less than or equals Subscript p r Baseline right parenthesis comma and $(\textbf {Ceers},\leq _{pr})$ left parenthesis bold Ceers comma less than or equals Subscript p r Baseline right parenthesis that realise each of the following cases: they have a supremum and an infimum; neither has a supremum nor an infimum; and they have an infimum but no supremum. Additionally, there are two $\leq _{pr}$ less than or equals Subscript p r Baseline -incomparable degrees in $(\textbf {Ceers},\leq _{pr})$ left parenthesis bold Ceers comma less than or equals Subscript p r Baseline right parenthesis such that they have a supremum and no infimum. Hence for $(\textbf {Ceers},\leq _{pr})$ left parenthesis bold Ceers comma less than or equals Subscript p r Baseline right parenthesis every combination of having or not having supremums and infimums can be realised. Kalmurzayev, Bazhenov, and Iskakov also investigate the definability of $(\textbf {Ceers},\leq _{pr})$ left parenthesis bold Ceers comma less than or equals Subscript p r Baseline right parenthesis inside other degree structures as well as definable subsets of $(\textbf {Ceers},\leq _{pr})$ left parenthesis bold Ceers comma less than or equals Subscript p r Baseline right parenthesis . For example, they show that $(\textbf {FinEq},\leq _{pr})$ left parenthesis bold FinEq comma less than or equals Subscript p r Baseline right parenthesis is first-order definable in $(\textbf {Ceers},\leq _{pr})$ left parenthesis bold Ceers comma less than or equals Subscript p r Baseline right parenthesis as well as that $(\textbf {Ceers},\leq _{pr})$ left parenthesis bold Ceers comma less than or equals Subscript p r Baseline right parenthesis and $(\textbf {Celps},\leq _{pr})$ left parenthesis bold Celps comma less than or equals Subscript p r Baseline right parenthesis are first-order definable inside $(\textbf {Ceprs},\leq _{pr})$ left parenthesis bold Ceprs comma less than or equals Subscript p r Baseline right parenthesis . The authors conclude the article by showing that the theory of $(\textbf {Celps},\leq _{pr})$ left parenthesis bold Celps comma less than or equals Subscript p r Baseline right parenthesis and $(\textbf {Ceprs},\leq _{pr})$ left parenthesis bold Ceprs comma less than or equals Subscript p r Baseline right parenthesis are hereditarily undecidable and conjecture that the theory of $(\textbf {Ceers},\leq _{pr})$ left parenthesis bold Ceers comma less than or equals Subscript p r Baseline right parenthesis is hereditarily undecidable.

The three articles under review are great examples of different ways in which primitive recursive reductions can form degree structures with interesting properties that differ from those formed using computable reductions. Together, they illustrate that these are not just better behaved degree structures but show interesting structural intricacies. The comparison between Primitive recursive equivalence relations and their primitive recursive complexity and Computably enumerable equivalence relations via primitive recursive reductions shows structural differences resulting from changing the computational complexity of the class of structures as well as the reduction. Primitive recursive equivalence relations and their primitive recursive complexity shows that Peq is very well-behaved; however, A discrete linear order with non-dense punctual degrees shows that degree structures on punctual presentations are not always well-behaved.