Online and Feasible Presentability: From Trees to Modal Algebras
Abstract
We investigate whether every computable member of a given class of structures admits a fully primitive recursive (also known as punctual) or fully P-TIME copy. A class with this property is referred to as punctually robust or P-TIME robust, respectively. We present both positive and negative results for structures corresponding to well-known representations of trees, such as binary trees, ordered trees, sequential (or prefix) trees, and partially ordered (poset) trees. A corollary of one of our results on trees is that semilattices and lattices are not punctually robust. In the main result of the paper, we demonstrate that, unlike Boolean algebras, modal algebras – that is, Boolean algebras with modality – are not punctually robust. The question of whether distributive lattices are punctually robust remains open. The paper contributes to a decades-old program on effective and feasible algebra, which has recently gained momentum due to rapid developments in punctual structure theory and its connections to online presentations of structures.
Keywords and phrases:
Algebraic structure, computable structure, fully primitive recursive structure, punctual structure, polynomial-time computable structure, punctual robustness, tree, semilattice, lattice, Boolean algebra, modal algebraCategory:
Track B: Automata, Logic, Semantics, and Theory of ProgrammingFunding:
Nikolay Bazhenov: The work of N. Bazhenov is supported by the Mathematical Center in Akademgorodok under the agreement No. 075-15-2025-349 with the Ministry of Science and Higher Education of the Russian Federation.Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation ComputabilityAcknowledgements:
We would like to thank Luca San Mauro and the reviewers for helpful comments.Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele PuppisSeries and Publisher:

1 Introduction
Suppose an infinite graph is given via a computer program , which, for any pair , determines whether holds. This graph is an infinite structure represented in a finitary manner. Such structures are called computable.111An infinite countable structure is computable if the domain of is a computable subset of and all the relations and functions from the signature of are uniformly computable [2]. However, without further restrictions on , the presentation of via may be inefficient. Does there always exist a more efficient representation of – that is a computer program such that computes , is isomorphic to , and is primitive recursive or even P-TIME computable?
The answer to the question posed above is negative [27]. However, if we impose certain structural restrictions on – such as requiring to be strongly locally finite or to be a tree – the answer becomes positive [14]. A more general condition that guarantees the existence of a nice copy of has been presented in [28].
The question raised in the opening paragraph admits several natural generalizations. For instance, one could replace graphs with other structures or explore alternative effectiveness conditions beyond primitive recursiveness or polynomial-time computability. Various instances of this question have drawn interest from researchers at the intersection of automata theory, complexity theory, and computable algebra. Notable examples include studies on algebraic structures represented by finite-state automata [30, 9, 22] and investigations into polynomial-time algebra [36, 13, 1]. Recently, Kalimullin, Melnikov, and Ng [27] initiated a research program at the intersection of computability and complexity, where primitive recursiveness serves as a fundamental tool for representing structures. Henceforth, we adopt this paradigm in the paper.
Definition 1 (punctual structure [27]).
An infinite structure over a finite signature is punctual if its domain is and all of its relations and functions are primitive recursive.
In the literature, punctual structures are also referred to as fully primitive recursive (fpr).
The purpose of the above definition was to capture the notion of an infinite structure which can be presented in an online fashion, or “without delay”. The requirement that the domain be (or any fixed primitive recursive subset of ) is significant. If, instead, we require the domain can be any primitive recursive subset of , a distinct notion arises (cf. Theorem 1.2 in [13] and the associated discussion). More importantly, structures satisfying the relaxed definition may lack the typical online characteristics [27, 5].
Henceforth, all structures, unless stated otherwise, are countably infinite.
A more detailed explanation of the underlying nature of punctual structures follows. This will be useful later, as many subsequent constructions adhere to this general pattern.
Essentially, a punctual structure may be given by a primitive recursive algorithm which, on input , determines and , for every from the signature of . Intuitively, for arguments (where ), all the relations and function values are determined by the primitive recursive computation which should converge by the computational stage . In a manner of speaking, our decision whether , or what is , must be quick, or made without delay. Here quick and without delay means now, that is at most at the stage . In fact, Definition 1 allows for a delay, but the delay itself must be primitive recursive – any instance of a truly unbounded search is prohibited.
As observed above, a punctual presentation of a structure possesses the following core property: input is received and processed incrementally, and decisions about incoming data must be made without access to the complete set of problem data. This property is a defining characteristic of online procedures in general, both in finite and infinite settings: in the finite setting, online algorithmics comprises a distinctive subfield of computer science, where performances of online algorithms are compared, relative to the offline performance, using competitive analysis (see, e.g., [10]); in the infinite setting, online graph coloring procedures from infinite combinatorics serve as a pertinent example (see, e.g., [31]). Due to the core property punctual structures share with online algorithms, it has been suggested that they encapsulate, at least partially, what may intuitively be described as a truly online presentation of a countably infinite structure; the justification of this approach is a delicate task and has been accomplished elsewhere [27, 5]. For alternative theoretical approaches, see [18, 3].
The theory of online structures has rapidly emerged as an intriguing subfield of computable structure theory, yielding an impressive amount of results across various topics, including universality [17, 20], degree structures [7, 23, 35], and definability [26], among others [6, 16, 34]. One of the central topics in online structure theory concerns punctual presentability.
Definition 2.
A structure is punctually presentable if it is isomorphic to a punctual one.
This definition formalizes the property we asked about in the opening paragraph of this paper. More generally, given a class of structures, we ask whether every computable member of has a punctual copy.
Definition 3 (punctual robustness [28]).
We say that a class of structures is punctually robust, if every computable member of is punctually presentable.
Turning to more feasible computations, similar notions naturally arise in the polynomial-time setting. As usual, our underlying model for P-TIME computations is provided by Turing machines.
Definition 4 (P-TIME structure and P-TIME robustness).
By we denote , i.e., the set of all finite binary strings. A structure in a finite signature is P-TIME (or polynomial-time computable) if the domain of is a polynomial-time computable subset of , and all the -relations and -functions of are polynomial-time computable. A P-TIME structure is fully P-TIME if the domain of is equal to . A structure is fully P-TIME presentable if it is isomorphic to a fully P-TIME structure.
We say that a class of structures is P-TIME robust if every computable member of is fully P-TIME presentable.
We note that for this framework, in place of the binary alphabet in the definition of P-TIME robustness, one can choose an arbitrary alphabet which contains at least two symbols (see, e.g., Chapter 3 in [11]).
A proof of punctual/P-TIME non-robustness for a given isomorphism-closed class of -structures (where indicates the signature) usually requires specific strategies tailored to the type of structure we are dealing with. However, the general scheme is an example of diagonalization and can be framed in game-theoretic terms as follows. We imagine playing a game against infinitely many adversaries . Adversaries are given via a computable enumeration. Each is a punctual/P-TIME -structure and contains all isomorphism-types of punctual/P-TIME copies of the structures from . The proof must give a computable strategy for building such that .
The following classes of structures have been shown to be punctually robust: equivalence structures [13, 27], (relational) successor trees [14], linear orders [24, 27], torsion-free abelian groups [27], Boolean algebras [27], abelian -groups [27], graphs with infinite semitransversals [28]; on the other hand, there are computable undirected graphs [27], computable torsion abelian groups [12], computable Archimedean ordered abelian groups [27] and functional predecessor trees [28] with no punctual copy.
Contributions
In this work we provide new results on punctual and P-TIME robustness of trees, (semi)lattices and modal algebras. Note that if a class is not punctually robust then it is not P-TIME robust either. Hence, P-TIME robustness is attested only for punctually robust classes. In the following, we briefly describe each of the three contributions.
The first group of results concerns trees. It is a continuation of the work by Cenzer and Remmel on (variations of) relational successor trees [14], as well as of Kalociński, San Mauro and Wrocławski on functional predecessor trees [28]. Our results extend this line of research to a few other well-known tree structures.
One of the fundamental types of tree-like structures is an ordered tree ([32], p. 306). This concept arises naturally by imposing an ordering on the children of each node in the tree. To avoid confusion with poset trees (to be defined), we use the term relational predecessor trees with ordering. The definition could have used the successor relation instead, without affecting Theorem 6 (see below).
Definition 5 (r.p.o. tree).
is a relational predecessor tree with ordering (abbreviated r.p.o. tree) if is a binary relation and is a partial ordering satisfying:
-
1.
is a directed graph such that all edges are oriented towards the root , and the underlying undirected graph is connected and acyclic,
-
2.
for every , iff and have the same parent.
The relation is the immediate predecessor relation of the tree. In Section 2 we prove:
Theorem 6.
The class of r.p.o. trees is punctually robust and P-TIME robust.
Theorem 6 unifies and expands on both the results of Cenzer and Remmel [14] on trees, and of Grigorieff [24] on linear orderings.
Another type of the tree that we consider is a poset tree. Given a partial order , we define and .
Definition 7 (poset tree).
A partial order is a poset tree if has the greatest element (the root) and, for every , is a finite linear order.
Such trees are well-known in set theory, where a tree is a partially ordered set , usually with the least element, such that for each , the set is well-ordered (see, e.g., Definition 9.10 in [25]). The inessential difference between the two definitions is the direction in which the tree grows. A more important difference is that, in set theory, a node may be infinitely far apart from the root. Our definition does not allow it. However, the following theorem of ours, which we prove in Section 3, works even for the class of trees in the set-theoretic sense (provided we reverse the growth direction):
Theorem 8.
Poset trees are not punctually robust.
While the underlying combinatorial idea behind the proof is quite intuitive, and some variants of it have been used elsewhere for a stronger notion of a tree [14], the present case requires much more care, as nodes in a poset tree do not carry information about their distances from the root. Even more importantly, Theorem 8 yields non-robustness of structures that lie intermediate between trees and Boolean algebras:
Corollary 9.
The following classes of structures are not punctually robust:
-
(i)
join semilattices and meet semilattices,
-
(ii)
lattices, complemented lattices, and non-distributive lattices.
The result holds under both order-theoretic and algebraic interpretation.
The remaining open question is whether the class of distributive lattices is punctually robust. The strategy used to obtain Theorem 8 is closely related to the “non-distributivity” of the computable poset tree we construct, and is therefore unlikely to provide a solution. To resolve the question, a different approach would be required, if distributive lattices are punctually robust at all.
The third contribution deals with modal algebras which are obtained from Boolean algebras by adding a modality operator. Boolean algebras constitute a classical object in mathematical logic. It is well-known that the class of Boolean algebras provides algebraic semantics for the classical propositional calculus (see, e.g., [37]). On the other hand, countable Boolean algebras are well-studied in computable structure theory – we refer to the monographs [21, 19] for a detailed exposition of results in this area.
Intuitively speaking, here we treat a modality as a formal logical operator which expresses the possibility of formulas: means that the statement is possible. More formally, one typically considers additional logical connectives (the possibility operator) and (the necessity operator), and defines an appropriate modal propositional calculus which extends the classical propositional calculus (see, e.g., the monograph [15]). Modal algebras provide algebraic semantics for (normal) modal logics. The formal definition of a modal algebra is given in Section 4. In contrast to Boolean algebras, there are only few known results about computable presentations of modal algebras – here we cite [29, 4].
It turns out that adding modality to the language of Boolean algebras enriches the computational content of the class: while (pure) Boolean algebras are punctually robust (informally, they are computationally “tame”) [27], modal algebras are not punctually robust (i.e., some of them can exhibit a “wilder” subrecursive behavior). In Section 4 we prove:
Theorem 10.
The class of modal algebras is not punctually robust.
Last but not least, we provide some elementary results about robustness of infinite binary trees and prefix trees – the details about them can be found in the related version.
2 Relational Predecessor Trees with Ordering
If holds and , then we say that is a child of (and is a parent of ). Notice that here we assume that the root does not have parents. If is a child of and is a child of , then we say that is a grandchild of . An analogous convention holds for all representations of trees under consideration in this article.
Definition 11.
If is a tree (r.p.o. tree or a different type) and is a node of that tree, then we define the depth of in the following way: for the root of the tree and whenever is a child of , then . In case of representations of trees with an empty node we also define . We also define to be the part of consisting only of nodes with a depth less or equal .
Because of the space limit, here we only prove a specific case of Theorem 6. The full proof of Theorem 6 appears in the related version.
Theorem 12.
The class of r.p.o. trees of unbounded depth is P-TIME robust.
Proof.
We fix a computable . We carry out the construction in stages . During each stage we perform a fixed number of steps of some algorithm calculating . We can assume that during each stage the algorithm at most once returns a true statement of the type either or for some and that in each such case and are connected to the root of the current approximation of .
We are going to construct a P-TIME copy . At the end of each stage structures and are going to be our current approximations of and respectively. We observe that according to the construction described below both of them will be rooted at every stage but at some stages they could be not isomorphic to each other. We are also going to construct an isomorphism .
To ensure that the construction is P-TIME, if for some time we do not discover any new relations in , we can delay establishing positive cases of relations in by putting new fresh strings into a reservoir set . The strings in that set will not be immediately put in a fixed place in the tree but we will guarantee that none of them can be in either relation with each other. Thus, while waiting to discover positive cases of relations in , we will keep adding negative cases of relations to . Since the tree has infinite depth, we are guaranteed to be able to add all the strings from the reservoir to the P-TIME tree at some point.
We order in the following way: if either or and additionally on the first position that they differ, has and has .
We construct the reservoir set . Initially . At the end of each stage we take the -least sequence from outside , add to and declare that is short.
We want to ensure that during infinitely many stages . We only intend to update to satisfy this condition if we discover such that and and the isomorphism is defined while and are not defined. Then we define where is the -least element of and we remove from .
For every other : , we take the -least sequences of length at least : and define for . We declare that all are long.
Verification
Lemma 13.
infinitely many times.
Proof.
Suppose that the depth of is at the end of some stage , is isomorphic to and does not change later.
Then the depth of is at most for all . This is because otherwise would have an element of depth such that is a path in starting from the root until . In this path some is the last element such that is defined. Since this path has not been prolonged in beyond we conclude that or . Hence the depth of is either or . Also since is in we conlude that the depth of is less or equal . Hence which is impossible.
Since the depth of is less or equal we obtain a contradiction with the assumption that this tree is unbounded. The above lemma implies that .
Lemma 14.
The domain of is .
Proof.
We observe that is a well-ordering on . We suppose that is the -least sequence not in the domain of .
Then was never added to because every sequence from is eventually added to (since gets extended infinitely many times and each time the -least sequence from is used to perform such extension). The sequence can only avoid getting added to if is long and was earlier added to but this is also a contradiction.
Lemma 15.
and are P-TIME.
Proof.
We observe that if and are in either relation from the signature, then either of them is long (maybe both of them). We assume that is long and that .
Then to discover that and are in a relation we perform the construction until stage and check if confirms that they are. We observe that if and do not enter a relation at the latest during stage , then they do not later.
We show that the above procedure is P-TIME. To perform the construction until stage we perform steps of the algorithm calculating and we add at most new sequences to , the length of each of them is at most . Hence the algorithm is P-TIME. Theorem 12 is proven.
3 Poset Trees
Let be a poset tree. We say that elements are adjacent, , if and only if , where is the strict partial order induced by . We say is a branching node of (or branches in ) if it has at least two children in . Such an induces a unique subtree of , called a branching and defined as . If is a branching node, we define , the length of , as the length of . By a binary branching we mean a tree with exactly two leaves sharing a parent. We say that is uniquely branching if for every , there exists at most one branching node such that . We say that a branching node belongs to the level of if the set contains precisely branching nodes. We denote the level of by and call its members -level nodes. Keep in mind that we number levels . Therefore, the first level is level . Level may be empty but if then , for . Let be a tree such that its level , , is nonempty. We define , the -level subtree of , as the least subtree of containing all nodes at levels together with their children. Notice that is the sum of the branchings for all such that . By we denote the root of the tree .
Lemma 16.
Let be a finite poset tree in which every internal node has exactly two children and let be such that, at every level of except the first, at most one node is in . Then there exists a leaf such that .
Proof.
By assumption, . Let be such that . The node has two children which are at the same level, so one of them, denote it by , is outside . Therefore, . This way we find a leaf such that . Let be disjoint finite trees and let be a leaf. is obtained from by attaching to in if and satisfy iff .
We are ready to start the proof of Theorem 8. We build a computable poset tree such that for every :
() |
Here, is a computable list of all binary primitive recursive functions.
Intuitively, the strategy will work as follows. We wait (in a dovetail fashion) until shows large enough fragment of itself (all nodes of up to level ) isomorphic to the corresponding fragment of that we construct (otherwise, we are done with in the limit). We enumerate fresh elements into so that the current outnumbers the current approximation of . These fresh elements form subtrees of attached to the leaves of . We now apply the pigeonhole principle: one of the subtrees must have more elements than the corresponding subtree in – we block the growth of that part in and make non-isomorphic to .
will be a uniquely branching poset tree with infinitely many levels. Alongside, we maintain a dynamic set of elements of whose role is to block the growth of the tree. At odd stages the tree grows wherever permits. At even stages, the strategies for monitor the relationship between and and put or withdraw elements from to satisfy . At any given stage we are dealing with an approximation of defined as follows: , where and for all , we have .
A node is closed (at a given stage) if there exists such that and at that stage. A node is open if is not closed.
Construction.
We proceed in stages. At the end of stage , we have a finite tree . We set .
At stage , the domain of is and . No is satisfied at stage , . At each subsequent stage , we start with a finite tree .
Stage (expansionary). Let be the open leaves of . Construct, for , a binary branching that branches at , with the root and other elements fresh (i.e., the domain of is extended by an interval , for a least sufficient to construct the branchings), such that after attaching to in , the length of the branching in the new tree starting at is equal to the height of plus . Declare that tree as (cf. Figure 1). Observe that if is uniquely branching, then is also uniquely branching.
Stage (non-expansionary). Set . For each , , apply the strategy for . Structurally and are the same, but they may differ with respect to open nodes (that is, at stage may be different from at stage ).
-strategy at stage .
Let . We consider the approximation of . Let . Therefore, is the approximation of that we considered at the previous non-expansionary stage (if ). We say that the strategy is ready if:
(1) | |||
(2) | |||
(3) | |||
(4) | |||
(5) |
If the strategy is not ready, withdraw all -level nodes from . If the strategy is ready and some node from level is in , we do nothing.
The remaining case is when the strategy is ready and nodes from level are not in . The situation is illustrated in Figure 2. Let be an isomorphism from to . Let be the -level nodes of . Each has two children which we denote by and . Each and is the root of a subtree of with cardinality and , respectively. In , we have the corresponding subtrees with roots and cardinalities . Since but has more elements than , the surplus of elements must be placed in the subtrees just described. By the pigeonhole principle, it follows that there exists , , such that . Take the least such and put into .
Verification
By construction, is a binary poset tree and that is uniquely branching. It is also easy to see that the domain of is and that is computable: it is sufficient to wait in an unbounded loop for a stage at which and respond how they are related in .
Lemma 17.
is infinite. Hence, it has infinitely many levels.
Proof.
It is sufficient to prove that at every stage , has at least one open leaf (and thus, the tree is extended at each expansionary stage). It is easy to see that has levels and (it looks like two binary branchings attached to the root). Let . Consider obtained from as follows: for every branching nodes such that and with no branching nodes between them, the path is collapsed to the single element (visually speaking, the nodes connecting two branching nodes from adjacent levels are erased). Observe that is a finite proper binary tree. By construction, and satisfy the premise of Lemma 16. Therefore, has an open leaf. It is immediate that has an open leaf as well. It is easy to see that has infinitely many branching nodes and infinitely many levels.
Lemma 18.
Every requirement is eventually satisfied.
Proof.
Fix a requirement and assume is a poset tree. We may additionally assume that is binary and that is nonempty (that is, has level ). If it does not, then is satisfied, because has infinitely many levels by Lemma 17.
Each of the properties (1), (2), (3) and (4) corresponds to a computable predicate of two variables, and . For satisfying the assumptions from the previous paragraph, the corresponding predicates hold in the limit – there is such that they are true when :
- Property (1).
-
Immediate.
- Property (2).
-
Recall that . For large enough , becomes a member of . Once this happens, is always a poset tree.
- Property (3).
-
The level of is nonempty by Lemma 17, it is present in for large enough by construction. Above we assumed that the level of is nonempty.
- Property (4).
-
For large enough , and .
Let be the least stage such that (1)-(4) hold for all stages . In particular, it means that starting from stage , we have and .
If (5) does not hold at stage , then it will not hold anymore, and thus is satisfied. So suppose (5) always holds starting from stage and let be the isomorphism from to . Note that this isomorphism is unique because is uniquely branching.
Observe that, at stage , the strategy for was not ready. If it were, then would be the least stage such that (1), (2), (3) and (4) hold for all even stages , which would contradict our choice of . Therefore, at stage all -level nodes were withdrawn from . Hence, at stage , the strategy for is ready and nodes from level are not in . It means that we put some from level of into . At stage , the subtree of with the root has fewer elements than the corresponding subtree of with root . And this property will hold forever because at any subsequent stage, the strategy is ready and , and in that case we do nothing. Therefore, at any subsequent expansionary stage, the subtree of with root does not grow. It remains to observe that if there were an isomorphism from to , it would have to map to , because and are isomorphic up to level and is uniquely branching so has only one legitimate choice for the value .
We recall that a partial ordering is called a join semilattice, meet semilattice, or lattice if, for any two elements in , there exists a least upper bound (denoted ), a greatest lower bound (denoted ), or both, respectively. Join semilattices, meet semilattices, and lattices are also represented as algebraic structures, namely , , and , respectively, and are characterized by appropriate axioms. For further details on lattices, we refer the reader to the standard literature [8].
We reserve the term (semi)lattice to refer specifically to these algebraic structures, while the term order-theoretic (semi)lattice is used for structures of the form . For (semi)lattices, the order and the operations and are mutually definable. Specifically, if and only if , and if and only if .
See 9
Proof of Corollary 9(i).
Let be the poset tree from Theorem 8. Since is a partial ordering of and the join of is well defined, is an order-theoretic join semilattice and, by Theorem 8, it has no punctual presentation. By defining , and arguing as above, is a computable order-theoretic meet semilattice with no punctual copy.
Let denote the join of and in . Consider the join semilattice . The join is a computable function of : we run the construction from the proof of Theorem 8 and wait for a stage at which both and enter . Then we have two cases:
-
1.
For -comparable , we return the maximum of with respect to .
-
2.
For -incomparable , the construction guarantees that , and thus can be computed from .
It follows that is a computable join semilattice.
To show that is not punctually presentable, assume otherwise. Let be a punctual copy of , and let . Hence, the relation is primitive recursive. But then is a punctual copy of which is impossible by Theorem 8.
An analogous proof works for , the meet semilattice induced by .
Proof of Corollary 9(ii).
Let be a punctual poset tree satisfying the following condition: for all , . We observe that via primitive recursive isomorphism . The root of is equal to .
Let be such that is a submodel of and , for all and , for all . It is easy to see that is a computable partial order. Moreover, is a lattice. The join of in is the same as in . The join of , where , is . The meet of such that is . The meet of such that is . It is clear that the corresponding algebraic structure where are the join and the meet functions of , respectively, is computable.
Observe that is a complemented lattice. The integer is the greatest element of and is the least. We show that each has a complement, that is, such that and . The construction of Theorem 8 guarantees that is a branching node in , and thus is a branching node in . Let be the two children of in . and are complements of each other. Assume that . Either or . If , and . Similarly, if , and .
Next, we prove that is not punctually presentable. Towards a contradiction, let be a punctual copy of . Let be the order-theoretic counterpart of , i.e., and are the join and meet of , respectively. Let be the least element of . It is clear that . Now, given a primitive recursive bijection , we define a punctual structure as follows: . The primitive recursiveness of follows from the following equivalences: and the fact that is primitive recursive. Hence is a punctual copy of which contradicts Theorem 8.
4 Modal Algebras
In this section, we mainly follow notations from the monographs [21, 33]. Boolean algebras are viewed as algebraic structures in the signature . Informally speaking, one can think of the signature functions as the usual set-theoretic operations: union, intersection, and complement. In addition, is a least element, and is a greatest element.
Let be a Boolean algebra. A function is called a modality if satisfies the following two properties:
-
for all ,
-
.
Informally, one can view as the result of applying the possibility operator to the “statement” . If is a modality, then the structure is called a modal algebra. Here we prove the following result:
See 10
The proof idea is similar to the one for non-punctual robustness of torsion abelian groups (Theorem 3.2 in [27]). We build a computable modal algebra . Given a punctual “adversary” structure (in the signature of modal algebras), we want to show an element with some specific properties. Namely, either generates (via the function ) an infinite substructure inside , or is a part of an -cycle of some finite size . In the first case, we will win “automatically”, since our will not contain elements generating infinite substructures. In the second case, we try to prevent some fixed prime factor of from appearing in the possible sizes of the -cycles. Preventing such from appearing is quite a delicate technical task which is achieved via careful “algebraic-flavored” arrangements. In each of the two cases, we ensure that . As usual, an appropriately organized priority construction allows to successfully deal with a whole computable sequence of adversaries.
We note that the construction for torsion abelian groups (from [27]) is a finite injury construction, while our construction of a modal algebra is injury-free. There are also some important differences related to the algebraic properties: for example, in the implemented construction, our -strategy has to work with a specifically selected tuple of witnesses (in place of just one element that was used in the proof idea), and this is selected based on the Boolean algebra specifics.
Before proceeding to the formal proof of Theorem 10, we give the necessary algebraic preliminaries. For a Boolean algebra , its ordering is defined in a standard way: if and only if . An element is an atom if is a minimal non-zero element in , i.e., and there is no with .
By we denote the set of atoms of . The Fréchet ideal is the ideal of generated by the set . Notice that the ideal contains precisely the finite sums of atoms.
Let be an element from a Boolean algebra . We put and .
Let be a tuple of elements from , and let . We define The following fact is well-known (see, e.g., Exercise 6 in § 1.2 of [21]):
Lemma 19.
Let be a Boolean algebra, and let be a tuple from . Then the subalgebra generated by the set contains precisely the finite sums of the elements , .
In addition, if and for , then the finite subalgebra has at least atoms. (Notice that an atom of the subalgebra is not necessarily an atom of the original algebra .)
It is not hard to prove the following ancillary result:
Lemma 20.
Let be an infinite Boolean algebra, and let be an arbitrary map from the set to . Then the function
is a modality. In addition, if the algebra is computable, and the sets and are computable, and the function is computable, then the modality is also computable.
Definition 21 (forward orbit).
Let be a modal algebra. For an element , the forward orbit of (with respect to ) is the set
Now we are ready to start the proof of Theorem 10. By we denote the Boolean algebra of all finite and cofinite subsets of . Beforehand, we choose our underlying computable Boolean algebra as follows. The algebra is a computable isomorphic copy of the direct product such that the sets and are computable.
In what follows, we identify with , and we use the following notations:
-
and .
-
Let be a computable list of all atoms of . We put and .
It is clear that is a computable list of all atoms of . In addition, we have and for all .
By Lemma 20, it is sufficient for us to construct a computable map Then the desired computable modal algebra is defined as
(6) |
4.1 Preparations for the Construction of
Firstly, we describe the basic module of the construction of the map , we call this module:
- Adding a -cycle to the map .
-
Given an odd prime number , we find the least such that the value is not yet defined. We also choose the least such that is undefined.
Let . For , we put: , , and .
We also say that the set is a -cycle. This concludes the description of the basic module.
We will ensure the following property of our (future) construction:
- (#)
-
For each odd prime , we add at most one -cycle to .
Property (#) is enough to prove the following useful lemma about the cardinalities of forward orbits.
Lemma 22.
Suppose that the modal algebra from Eq. (6) satisfies Property (#). In addition, assume that there are infinitely many primes such that we have added a -cycle to . Let and . Then the element satisfies precisely one of the following three cases:
-
1.
and .
-
2.
and .
-
3.
and for some and some odd primes such that for . (Note that here a -cycle has been added to at some stage of the construction.) In addition, if , then .
Furthermore, if , and for some , then the element satisfies Case 3.
Proof.
If , then Lemma 20 defines . Thus, assume that and .
By Property (#), for each prime the algebra contains at most one -cycle. We choose all prime numbers such that:
-
there exists an atom such that and belongs to the (unique) -cycle; and
-
there exists such that and belongs to the -cycle.
Notice that (at least one) such prime exists. Indeed, if there are no such primes , then the element satisfies the following condition:
-
if an atom belongs to a -cycle and , then every atom from this -cycle lies -below .
This condition implies that must be equal to (which contradicts our assumption).
Define . Then a straightforward computation shows the following: and for all we have: if , then . Hence, . We deduce that every element satisfies one of the three cases of the lemma.
Now suppose that and . Then for some , we have and . On the other hand, for all , we have and . By choosing from the -cycle of the atom , we deduce that must satisfy Case 3. (If and , then one can make a similar argument.) Lemma 22 is proven.
4.2 Requirements and the Construction of
Observe the following: the modal algebra from Eq. (6) has a punctual copy if and only if the structure has a punctual copy. Thus, we fix a uniformly computable list containing all punctual structures in the signature . We satisfy the following requirements:
-
The structure is not isomorphic to .
In what follows, we will abuse the notations: we identify the structures and .
At a stage , we will have a finite list of active requirements. Each active requirement possesses a corresponding witness . Active requirements may be (forever) deactivated. In addition, at a stage we will have at most one requirement on the alert. The intended (full) life-cycle of a given requirement is as follows:
-
inactive on the alert active deactivated.
Along the construction, we always do the following background monitoring procedure. At a stage , for each with , we consider the finite set Assume that at the stage we have witnessed one of the following conditions:
-
(a)
Some of the elements from the set
do not satisfy the axioms of Boolean algebras or the axioms of modal algebras. (Notice that here the set is the “potential” Boolean subalgebra generated by the set inside .)
-
(b)
or or or .
-
(c)
There exist and such that , , and
-
either and , or
-
and , or
-
and .
-
-
(d)
There exist and such that , , , and .
Then we declare the requirement deactivated. Indeed, in this case the structure cannot be isomorphic to . To observe this non-isomorphism for Condition (c) above, we recall the following fact: if , and , then precisely one of the elements satisfies and . By Lemma 22, the remaining element satisfies and . In addition, we have .
To observe non-isomorphism for Condition (d), we recall the following: if and , then and every satisfies and .
Due to the described monitoring procedure, in the main construction given below, we may assume (without loss of generality) that every considered structure has the following properties, for :
- (P.0)
-
The reduct of to the signature is a punctual modal algebra. In addition, , , and .
- (P.1)
-
If , and , then and .
- (P.2)
-
If and for , then at most one element satisfies .
Now we are ready to describe the main construction. Let be the increasing list of all odd prime numbers.
Construction.
At stage , there are no active requirements. We declare that the requirement is on the alert.
Stage .
Roughly speaking, the main goal of the stage is to decide whether to add a -cycle to the map . In addition, our actions will ensure the following property:
- ()
-
Suppose that by the end of the stage , an active requirement has a witness . Then satisfies one of the following two conditions:
-
either the forward orbit is infinite, or
-
the set is finite and the following implication holds: if has a form , where and are prime numbers, then some prime must divide .
-
Intuitively speaking, the choice of such form is dictated by Lemma 22. If the decomposition of has any other form, then Lemma 22 ensures that .
If the structure does not contain a -cycle by the end of the stage , then we say that the prime is forbidden from entering the structure .
Our actions at the stage go as follows. If there is a requirement which is currently on the alert, then firstly we execute the following strategy.
4.2.1 Strategy for Which Is on the Alert
Let be the Boolean subalgebra of generated by the following elements: , , and the elements of all -cycles added to at stages . By Lemma 19, the algebra is finite, and one can computably recover this structure . In addition, Lemma 20 ensures that the values are defined for all .
Define . Consider the -least elements from the structure such that . We define the following finite Boolean subalgebra of :
By Lemma 19, the algebra has at least atoms. Applying Property (P.2) of the construction, we deduce that at most two of these atoms satisfy (indeed, at most one atom below , and at most one atom below ). Therefore, among the atoms of we can find -many pairwise distinct elements such that , , and for .
By Property (P.1), we obtain that and . We define We compute the values Then one of the following five cases is satisfied:
Case (i.a).
There exists such that the function is not injective on the set (i.e., there exist such that and ).
Then we (safely) declare the requirement deactivated. Indeed, by item (3) of Lemma 22, the structure cannot be isomorphic to our structure . In all cases (i.) below, we will assume that the function is injective on the set .
Case (i.b).
There exists with the following properties:
-
and .
-
Consider the prime decomposition , where for and . For some , either has already been forbidden from entering , or , or .
Then by Lemma 22, our structure cannot be isomorphic to , since does not contain elements with . We declare the requirement deactivated.
Case (i.c).
Neither of Cases (i.a) and (i.b) is satisfied, and there exists with the following properties:
-
and .
-
For some , the prime divides .
We declare the requirement active, and we set . Note the following: if , then will definitely satisfy Property () at the end of stage .
Case (i.d).
Neither of Cases (i.a)–(i.c) is satisfied, and there exists such that for all , we have . Notice that this condition is equivalent to the condition . We declare the requirement active, and we define .
Case (i.e).
Suppose that neither of Cases (i.a)–(i.d) is satisfied. Then every , , has the following properties:
- (e.1)
-
and .
- (e.2)
-
The number has prime decomposition , where for , and and has not been forbidden from entering .
We show that in this case the structure is not isomorphic to . In order to prove this, it is enough to establish the following fact:
Claim 23.
does not contain -many pairwise disjoint elements satisfying:
(7) |
Proof.
Suppose that an element satisfies Eq. (7). Consider the prime number . By the proof of Lemma 22, there exists an atom such that and belongs to a -cycle. By the definition of the finite algebra , we have . We define . We notice the following fact: if , then . Indeed, if , then .
Now, towards a contradiction, assume that contains -many pairwise disjoint elements satisfying Eq. (7). Then the algebra contains at least -many pairwise distinct elements . This contradicts the choice of .
Indeed, recall that for . Hence, the structure does contain -many disjoint elements satisfying Eq. (7). Thus, Claim 23 implies that . Therefore, in Case (i.e), we safely declare the requirement deactivated.
This concludes the description of the strategy for which is on the alert. After executing this strategy, one-by-one, we execute strategies for the currently active requirements (see below). Notice that in Cases (i.c) and (i.d) above, this execution also includes our requirement ( had been on the alert, but then it moved to becoming active).
4.2.2 Strategy for an Active Requirement
As usual, here we assume the following: if the requirement was active at the end of the previous stage , then it satisfied Property () at that moment. Consider the witness for . Recall that
(8) |
We compute the values , for all . One of the following two cases is satisfied:
Case (ii.a).
Suppose that for some . Then we have . In particular, the set is finite. For , we compute its prime decomposition
Similarly to Case (i.b), if for some either was already forbidden, or , or , then . Thus, we declare such deactivated. Hence, in what follows we may assume that where .
If some equals , then we forbid adding a -cycle to the map . Since will not have -cycles, by Lemma 22, we deduce that is not isomorphic to . We safely declare the requirement deactivated.
If , then stays active. Here we claim that some must be equal to for some . Indeed, if was already active at the stage , then this fact is guaranteed by the “-version” of Property (). Otherwise, moved from being on the alert to being active at the stage . But then this move was triggered by Case (i.c), and some with must divide . We observe that in Case (ii.a), the requirement will satisfy Property () at the end of the stage .
Case (ii.b).
Otherwise, for all . Then the requirement stays active. Observe that here .
In Case (ii.b) we need to show that the requirement will still satisfy Property () by the end of the stage . Towards a contradiction, assume that Property () fails. Then the set is finite, and we have , where the primes satisfy . By Eq. (8), we obtain that This contradicts the fact that .
We deduce that in each of the two cases, an active requirement will satisfy Property () by the end of the stage . This concludes the description of the strategy for an active .
If by the end of the stage , no strategy has forbidden to add a -cycle to , then we proceed as follows:
-
Add a -cycle to the map .
-
Find the least such that the requirement has never been on the alert before. Declare this being on the alert.
4.3 Verification
Lemma 24.
For every , the value is eventually defined. Consequently, the structure from Eq. (6) is a well-defined computable modal algebra.
Proof.
It is sufficient to show that our construction adds a -cycle for infinitely many . Towards a contradiction, assume that for every , the structure never gets a -cycle. Then for every , the requirement is never declared on the alert. Consequently, such never becomes active.
Choose a large enough stage with the following property: if a requirement , where , is eventually declared deactivated, then was deactivated before the stage . Since the -cycle is forever forbidden, this forbiddance was triggered by the following action: at the stage , some currently active requirement , where , forbade , and after that this was deactivated. But this contradicts the choice of the stage . We deduce that is defined for all atoms from . Lemma 24 is proved.
Lemma 25.
Every requirement is satisfied.
Proof.
Since our construction adds a -cycle for infinitely many (as discussed in Lemma 24), every requirement is eventually declared being on the alert. If a requirement is eventually deactivated, then (as discussed in detail in the construction description) we have and is satisfied.
Suppose that a requirement is never deactivated. Then there exists a stage such that is active at every stage . Consider the corresponding witness . If the forward orbit is infinite, then by Lemma 22, is not isomorphic to . Therefore, we may assume that the set is finite.
Since , there exists a large enough stage such that for every , the active requirement satisfies Case (ii.a) at the stage . The requirement is never deactivated, hence, we have for some and some primes . But then Property () of the construction implies that for every , there exists a prime such that divides . Hence, has infinitely many divisors, which gives a contradiction. We conclude that for every , the structure is not isomorphic to .
References
- [1] Pavel E. Alaev and Victor L. Selivanov. Polynomial computability of fields of algebraic numbers. Doklady Mathematics, 98(1):341–343, 2018. doi:10.1134/S1064562418050137.
- [2] Chris J. Ash and Julia Knight. Computable structures and the hyperarithmetical hierarchy. Elsevier, 2000.
- [3] Matthew Askes and Rod Downey. Online, computable and punctual structure theory. Logic Journal of the IGPL, 31(6):1251–1293, August 2022. doi:10.1093/jigpal/jzac065.
- [4] Nikolay Bazhenov. Categoricity spectra for polymodal algebras. Studia Logica, 104(6):1083–1097, 2016. doi:10.1007/S11225-016-9667-Y.
- [5] Nikolay Bazhenov, Rod Downey, Iskander Kalimullin, and Alexander Melnikov. Foundations of online structure theory. Bulletin of Symbolic Logic, 25(2):141–181, 2019. doi:10.1017/bsl.2019.20.
- [6] Nikolay Bazhenov, Marta Fiori-Carones, Lu Liu, and Alexander G. Melnikov. Primitive recursive reverse mathematics. Annals of Pure and Applied Logic, 175(1):103354, 2024. doi:10.1016/J.APAL.2023.103354.
- [7] Nikolay Bazhenov, Iskander Kalimullin, Alexander Melnikov, and Keng Meng Ng. Online presentations of finitely generated structures. Theoretical Computer Science, 844:195–216, 2020. doi:10.1016/j.tcs.2020.08.021.
- [8] Garrett Birkhoff. Lattice Theory, volume 25 of Colloquium Publications. American Mathematical Society, Providence, Rhode Island, 1940.
- [9] Achim Blumensath and Erich Grädel. Automatic structures. In 15th Annual IEEE Symposium on Logic in Computer Science, Santa Barbara, California, USA, June 26-29, 2000, pages 51–62. IEEE Computer Society, 2000. doi:10.1109/LICS.2000.855755.
- [10] A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 2005.
- [11] D. Cenzer and J. B. Remmel. Complexity theoretic model theory and algebra. In Handbook of recursive mathematics, Vol. 1, volume 138 of Studies in Logic and the Foundations of Mathematics, pages 381–513. North-Holland, Amsterdam, 1998. doi:10.1016/S0049-237X(98)80011-6.
- [12] Douglas Cenzer and Jeffrey Remmel. Polynomial-time abelian groups. Annals of Pure and Applied Logic, 56(1):313–363, 1992. doi:10.1016/0168-0072(92)90076-C.
- [13] Douglas Cenzer and Jeffrey B. Remmel. Polynomial-time versus recursive models. Annals of Pure and Applied Logic, 54(1):17–58, 1991. doi:10.1016/0168-0072(91)90008-A.
- [14] Douglas Cenzer and Jeffrey B. Remmel. Feasible graphs with standard universe. Annals of Pure and Applied Logic, 94(1):21–35, 1998. doi:10.1016/S0168-0072(97)00064-X.
- [15] Alexander Chagrov and Michael Zakharyaschev. Modal Logic. Oxford University Press, Oxford, 1997.
- [16] Marina Dorzhieva and Alexander G. Melnikov. Punctually presented structures I: closure theorems. Computability, 12(4):323–337, 2023. doi:10.3233/COM-230448.
- [17] Rod Downey, Noam Greenberg, Alexander Melnikov, Keng Meng Ng, and Daniel Turetsky. Punctual categoricity and universality. The Journal of Symbolic Logic, 85(4):1427–1466, 2020. doi:10.1017/jsl.2020.51.
- [18] Rod Downey, Alexander Melnikov, and Keng Meng Ng. Foundations of Online Structure Theory II: The Operator Approach. Logical Methods in Computer Science, 17(3):6:1–6:35, July 2021. doi:10.46298/lmcs-17(3:6)2021.
- [19] Rodney Downey and Alexander Melnikov. Computable structure theory: A unified approach. Springer, to appear. URL: https://homepages.ecs.vuw.ac.nz/˜melnikal/maindoc.pdf.
- [20] Rodney G. Downey, Matthew Harrison-Trainor, Iskander Sh. Kalimullin, Alexander G. Melnikov, and Daniel Turetsky. Graphs are not universal for online computability. Journal of Computer and System Sciences, 112:1–12, 2020. doi:10.1016/J.JCSS.2020.02.004.
- [21] Sergei S. Goncharov. Countable Boolean Algebras and Decidability. Consultants Bureau, New York, 1997.
- [22] Erich Grädel. Automatic structures: Twenty years later. In Holger Hermanns, Lijun Zhang, Naoki Kobayashi, and Dale Miller, editors, LICS ’20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, July 8-11, 2020, pages 21–34. ACM, 2020. doi:10.1145/3373718.3394734.
- [23] Noam Greenberg, Matthew Harrison-Trainor, Alexander Melnikov, and Dan Turetsky. Non-density in punctual computability. Annals of Pure and Applied Logic, 172(9):102985, 2021. doi:10.1016/j.apal.2021.102985.
- [24] Serge Grigorieff. Every recursive linear ordering has a copy in DTIME-SPACE. Journal of Symbolic Logic, 55(1):260–276, 1990. doi:10.2307/2274966.
- [25] Thomas Jech. Set Theory: The Third Millennium Edition, revised and expanded. Springer Monographs in Mathematics. Springer Berlin Heidelberg, 2007.
- [26] Iskander Sh. Kalimullin, Alexander G. Melnikov, and Antonio Montalbán. Punctual definability on structures. Annals of Pure and Applied Logic, 172(8):102987, 2021. doi:10.1016/J.APAL.2021.102987.
- [27] Iskander Sh. Kalimullin, Alexander G. Melnikov, and Keng Meng Ng. Algebraic structures computable without delay. Theoretical Computer Science, 674:73–98, 2017. doi:10.1016/J.TCS.2017.01.029.
- [28] Dariusz Kalociński, Luca San Mauro, and Michał Wrocławski. Punctual Presentability in Certain Classes of Algebraic Structures. In Rastislav Královič and Antonín Kučera, editors, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), volume 306 of Leibniz International Proceedings in Informatics (LIPIcs), pages 65:1–65:15, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISSN: 1868-8969. doi:10.4230/LIPIcs.MFCS.2024.65.
- [29] Bakhadyr Khoussainov and Tomasz Kowalski. Computable isomorphisms of Boolean algebras with operators. Studia Logica, 100(3):481–496, 2012. doi:10.1007/S11225-012-9411-1.
- [30] Bakhadyr Khoussainov and Anil Nerode. Automatic presentations of structures. In Daniel Leivant, editor, Logic and Computational Complexity, volume 960 of Lecture Notes in Computer Science, pages 367–392. Springer Berlin Heidelberg, 1995. doi:10.1007/3-540-60178-3_93.
- [31] H. A. Kierstead. Recursive and on-line graph coloring. In Yu L. Ershov, S. S. Goncharov, A. Nerode, J. B. Remmel, and V. W. Marek, editors, Handbook of Recursive Mathematics, Vol. 2, volume 139 of Studies in Logic and the Foundations of Mathematics, pages 1233–1269. Elsevier, 1998. ISSN: 0049-237X. doi:10.1016/S0049-237X(98)80051-7.
- [32] Donald E. Knuth. The Art of Computer Programming. Volume I. Fundamental Algorithms. The Art of Computer Programming. Addison-Wesley, Reading, Massachusetts, 1968.
- [33] Sabine Koppelberg. Handbook of Boolean Algebras, Volume 1. North-Holland, Amsterdam, 1989.
- [34] Alexander Melnikov and Keng Meng Ng. A structure of punctual dimension two. Proceedings of the American Mathematical Society, 148(7):3113–3128, 2020. doi:10.1090/proc/15020.
- [35] Alexander G. Melnikov and Keng Meng Ng. The back-and-forth method and computability without delay. Israel Journal of Mathematics, 234(2):959–1000, 2019. doi:10.1007/s11856-019-1948-5.
- [36] Anil Nerode and Jeffrey B. Remmel. Complexity-theoretic algebra II: Boolean algebras. Annals of Pure and Applied Logic, 44(1–2):71–99, 1989. doi:10.1016/0168-0072(89)90047-X.
- [37] Helena Rasiowa and Roman Sikorski. The Mathematics of Metamathematics. Państwowe Wydawnictwo Naukowe, Warsaw, 1963.