Abstract 1 Introduction 2 Relational Predecessor Trees with Ordering 3 Poset Trees 4 Modal Algebras References

Online and Feasible Presentability: From Trees to Modal Algebras

Nikolay Bazhenov ORCID Novosibirsk State University, Novosibirsk, Russia Dariusz Kalociński ORCID Institute of Computer Science, Polish Academy of Sciences, Warsaw, Poland Michał Wrocławski ORCID Faculty of Philosophy, University of Warsaw, Warsaw, Poland
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 algebra
Category:
Track B: Automata, Logic, Semantics, and Theory of Programming
Funding:
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.
Dariusz Kalociński: The work of D. Kalociński is supported by the National Science Centre Poland under the agreement No. 2023/49/B/HS1/03930.
Copyright and License:
[Uncaptioned image] © Nikolay Bazhenov, Dariusz Kalociński, and Michał Wrocławski; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation Computability
Related Version:
Full Version: https://arxiv.org/abs/2504.16663
Acknowledgements:
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 Puppis

1 Introduction

Suppose an infinite graph G=(,E) is given via a computer program P, which, for any pair x,y, determines whether E(x,y) 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 P, the presentation of G via P may be inefficient. Does there always exist a more efficient representation of G – that is a computer program P such that P computes E, G=(,E) is isomorphic to G, and E 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 G – such as requiring G 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 G 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 P which, on input x¯=x1,x2,,xn, determines R𝒜(x¯) and f𝒜(x¯), for every R,f from the signature of 𝒜. Intuitively, for arguments xis (where s), all the relations and function values are determined by the primitive recursive computation P(x¯) which should converge by the computational stage s. In a manner of speaking, our decision whether R(x¯), or what is f(x¯), must be quick, or made without delay. Here quick and without delay means now, that is at most at the stage s. 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 G 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 {0,1}<ω, i.e., the set of all finite binary strings. A structure 𝒮 in a finite signature L is P-TIME (or polynomial-time computable) if the domain of 𝒮 is a polynomial-time computable subset of 𝔹, and all the L-relations and L-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 {0,1} 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 L-structures (where L 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 𝒜1,𝒜2,. Adversaries are given via a computable enumeration. Each 𝒜i is a punctual/P-TIME L-structure and 𝒜1,𝒜2, contains all isomorphism-types of punctual/P-TIME copies of the structures from 𝔎. The proof must give a computable strategy for building 𝔎 such that i(𝒜i𝔎≇𝒜i).

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 p-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).

𝒯=(T,P,<,r) is a relational predecessor tree with ordering (abbreviated r.p.o. tree) if P is a binary relation and < is a partial ordering satisfying:

  1. 1.

    (T,P) is a directed graph such that all edges are oriented towards the root r, and the underlying undirected graph is connected and acyclic,

  2. 2.

    for every x,yT, xyyx iff x and y have the same parent.

The relation P 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 (P,), we define Px={yP:yx} and Px={yP:yx}.

Definition 7 (poset tree).

A partial order (P,) is a poset tree if (P,) has the greatest element (the root) and, for every xP, Px is a finite linear order.

Such trees are well-known in set theory, where a tree is a partially ordered set (P,<), usually with the least element, such that for each xP, the set P<x 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:

  1. (i)

    join semilattices and meet semilattices,

  2. (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: p means that the statement p 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 P(x,y) holds and xr, then we say that x is a child of y (and y is a parent of x). Notice that here we assume that the root r does not have parents. If x is a child of y and y is a child of z, then we say that x is a grandchild of z. 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 a is a node of that tree, then we define the depth of a in the following way: for the root of the tree d𝒯(r)=0 and whenever b is a child of a, then d𝒯(b)=d𝒯(a)+1. In case of representations of trees with an empty node e we also define d𝒯(e)=1. We also define 𝒯n to be the part of 𝒯 consisting only of nodes with a depth less or equal n.

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 𝒯=(𝔹,P𝒯,<𝒯,r𝒯). We carry out the construction in stages s=0,1,. During each stage we perform a fixed number l 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 P𝒯(a,b) or a<𝒯b for some a,b𝔹 and that in each such case a and b 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 s structures 𝒯s and s 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 A. 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 lh(α)<lh(β) or lh(α)=lh(β) and additionally on the first position that they differ, α has 0 and β has 1.

We construct the reservoir set A. Initially A=. At the end of each stage s we take the -least sequence α from outside s, add α to A and declare that α is short.

We want to ensure that during infinitely many stages 𝒯ss. We only intend to update s to satisfy this condition if we discover a,b,c𝒯 such that P𝒯(b,a) and P𝒯(c,b) and the isomorphism φ(a)=α is defined while φ(b) and φ(c) are not defined. Then we define φ(c)=β where β is the -least element of A and we remove β from A.

For every other d𝒯sφ1[s]: d1,,dj, we take the -least sequences of length at least s: δ1,,δj and define φ(di)=δi for 1ij. We declare that all δi are long.

Verification
Lemma 13.

s𝒯s infinitely many times.

Proof.

Suppose that the depth of 𝒯s is ds at the end of some stage s, s is isomorphic to 𝒯s and s does not change later.

Then the depth of 𝒯t is at most ds+1 for all ts. This is because otherwise 𝒯t would have an element a of depth dt>ds+1 such that a0,,adt is a path in 𝒯t starting from the root a0=r until adt=a. In this path some ai is the last element such that φ(ai)=αi is defined. Since this path has not been prolonged in t beyond αi we conclude that i=dt or i=dt1. Hence the depth of αi is either dt or dt1. Also since αi is in s we conlude that the depth of αi is less or equal ds. Hence dt1ds which is impossible.

Since the depth of 𝒯t is less or equal ds+1 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 A because every sequence from A is eventually added to (since gets extended infinitely many times and each time the -least sequence from A is used to perform such extension). The sequence α can only avoid getting added to A if α is long and was earlier added to but this is also a contradiction.

Lemma 15.

P 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 lh(α)lh(β)=s.

Then to discover that α and β are in a relation we perform the construction until stage s and check if s confirms that they are. We observe that if α and β do not enter a relation at the latest during stage s, then they do not later.

We show that the above procedure is P-TIME. To perform the construction until stage s we perform l×s steps of the algorithm calculating 𝒯 and we add at most s new sequences to , the length of each of them is at most s. Hence the algorithm is P-TIME. Theorem 12 is proven.

3 Poset Trees

Let (T,) be a poset tree. We say that elements x,yT are adjacent, Adj(x,y), if and only if x<y¬zT(x<z<y), where < is the strict partial order induced by . We say xT is a branching node of T (or x branches in T) if it has at least two children in T. Such an x induces a unique subtree of T, called a branching and defined as br(x,T)={yT:Adj(y,x)}Tx. If x is a branching node, we define |br(x,T)|, the length of br(x,T), as the length of Tx. By a binary branching we mean a tree with exactly two leaves sharing a parent. We say that (T,) is uniquely branching if for every n, there exists at most one branching node xT such that |Tx|=n. We say that a branching node xT belongs to the level n of T if the set T>x contains precisely n branching nodes. We denote the level n of T by T[n] and call its members n-level nodes. Keep in mind that we number levels 0,1,. Therefore, the first level is level 0. Level T[n] may be empty but if T[n] then T[k], for k<n. Let (T,) be a tree such that its level i, i, is nonempty. We define T[i], the i-level subtree of T, as the least subtree of T containing all nodes at levels i together with their children. Notice that T[i] is the sum of the branchings br(x,T) for all xT[j] such that ji. By r(T) we denote the root of the tree T.

Lemma 16.

Let (T,) be a finite poset tree in which every internal node has exactly two children and let FT be such that, at every level of T except the first, at most one node is in F. Then there exists a leaf yT such that TyF=.

Proof.

By assumption, r(T)F. Let xT be such that TxF=. The node x has two children which are at the same level, so one of them, denote it by x, is outside F. Therefore, TxF=. This way we find a leaf y such that TyF=. Let T,T^ be disjoint finite trees and let zT be a leaf. T is obtained from T by attaching T^ to z in T if dom(T)=dom(T)(dom(T^){r(T^)}) and x,ydom(T) satisfy AdjT(x,y) iff AdjT(x,y)AdjT^(x,y)AdjT^(x,r(T^))y=z.

We are ready to start the proof of Theorem 8. We build a computable poset tree 𝒯=(,T) such that for every i:

 𝒫i=(,ϕi(2)) is a poset tree𝒯≇𝒫i. (Ri)

Here, (ϕi(2))i is a computable list of all binary primitive recursive functions.

Intuitively, the strategy will work as follows. We wait (in a dovetail fashion) until 𝒫i shows large enough fragment P of itself (all nodes of 𝒫i up to level i) isomorphic to the corresponding fragment of 𝒯 that we construct (otherwise, we are done with 𝒫i in the limit). We enumerate fresh elements into 𝒫i so that the current 𝒫i outnumbers the current approximation of 𝒯. These fresh elements form subtrees of 𝒫i attached to the leaves of P. 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 𝒫i non-isomorphic to 𝒯.

𝒯 will be a uniquely branching poset tree with infinitely many levels. Alongside, we maintain a dynamic set F of elements of 𝒯 whose role is to block the growth of the tree. At odd stages the tree grows wherever F permits. At even stages, the strategies for 𝒫i monitor the relationship between 𝒯 and 𝒫i and put or withdraw elements from F to satisfy Ri. At any given stage s we are dealing with an approximation 𝒫i,s of 𝒫i defined as follows: 𝒫i,s=(Ni,s,i,s), where Ni,s={0,1,,s1} and for all x,yNi,s, we have xi,syϕi(2)(x,y)=1.

A node y𝒯 is closed (at a given stage) if there exists x such that yTx and xF at that stage. A node y is open if y is not closed.

Construction.

We proceed in stages. At the end of stage s, we have a finite tree 𝒯s. We set 𝒯=s𝒯s.

At stage s=0, the domain of 𝒯0 is T0={0} and 0T0. No Ri is satisfied at stage 0, F=. At each subsequent stage s>0, we start with a finite tree 𝒯s1.

Stage s=2t+1 (expansionary). Let l1,l2,,ln be the open leaves of 𝒯s1. Construct, for 1jn, a binary branching bj that branches at xj, with the root lj and other elements fresh (i.e., the domain of 𝒯 is extended by an interval [|Ts|;b), for a least b sufficient to construct the branchings), such that after attaching bj to lj in 𝒯s1, the length of the branching in the new tree starting at xj is equal to the height of 𝒯s1 plus j1. Declare that tree as 𝒯s (cf. Figure 1). Observe that if 𝒯s1 is uniquely branching, then 𝒯s is also uniquely branching.

Figure 1: Obtaining 𝒯s (black and gray) from 𝒯s1 (black) at odd stage s by attaching binary branchings bj (left) to lj in 𝒯s1, for 1jn.

Stage s=2t>0 (non-expansionary). Set 𝒯s=𝒯s1. For each 𝒫i, 0is, apply the strategy for 𝒫i. Structurally 𝒯s and 𝒯s1 are the same, but they may differ with respect to open nodes (that is, F at stage s1 may be different from F at stage s).

𝓟𝒊-strategy at stage 𝒔=𝟐𝒕.

Let s=max(s,|Ts|+1). We consider the approximation 𝒫i,s of 𝒫i. Let s′′=max(s2,|Ts2|+1). Therefore, 𝒫i,s′′ is the approximation of 𝒫i that we considered at the previous non-expansionary stage (if is′′). We say that the strategy is ready if:

is2, that is, 𝒫i was considered at the previous non-expansionary stage (1)
𝒫i,s is a poset tree, (2)
𝒯s[i+1] and 𝒫i,s[i+1], (3)
(𝒫i,s)[i+1]=(𝒫i,s′′)[i+1],(𝒯s)[i+1]=(𝒯s2)[i+1], and (4)
(𝒯s)[i+1](𝒫i,s)[i+1]. (5)

If the strategy is not ready, withdraw all (i+1)-level nodes from F. If the strategy is ready and some node from level i+1 is in F, we do nothing.

The remaining case is when the strategy is ready and nodes from level i+1 are not in F. The situation is illustrated in Figure 2. Let f be an isomorphism from (𝒯s)[i+1] to (𝒫i,s)[i+1]. Let x1,,xn be the (i+1)-level nodes of (𝒯s)[i+1]. Each xj has two children which we denote by lj and lj. Each lj and lj is the root of a subtree of 𝒯s with cardinality Nj and Nj, respectively. In 𝒫i,s, we have the corresponding subtrees with roots f(lj),f(lj) and cardinalities Mj,Mj. Since (𝒫i,s)[i+1](Ts)[i+1] but 𝒫i,s has more elements than 𝒯s, the surplus of elements must be placed in the subtrees just described. By the pigeonhole principle, it follows that there exists j, 1jn, such that Mj+Mj>Nj+Nj. Take the least such j and put xj into F.

Figure 2: Schematic representation of 𝒯s and 𝒫i,s from the point of view of the strategy for 𝒫i at stage s. Solid lines correspond to the tree (𝒯s)[i+1] (left) and (𝒫i,s)[i+1] (right). The strategy for 𝒫i monitors the cardinalities of the subtrees, which are represented by dashed triangles.
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 xTy is computable: it is sufficient to wait in an unbounded loop for a stage s at which x,y𝒯s and respond how they are related in 𝒯s.

Lemma 17.

𝒯 is infinite. Hence, it has infinitely many levels.

Proof.

It is sufficient to prove that at every stage s, 𝒯s has at least one open leaf (and thus, the tree is extended at each expansionary stage). It is easy to see that 𝒯3 has levels 0 and 1 (it looks like two binary branchings attached to the root). Let s3. Consider 𝒯s obtained from 𝒯s as follows: for every branching nodes x,yTs such that x<Ty and with no branching nodes between them, the path {zTs:x<TzTy} is collapsed to the single element y (visually speaking, the nodes connecting two branching nodes from adjacent levels are erased). Observe that 𝒯s is a finite proper binary tree. By construction, 𝒯s and F satisfy the premise of Lemma 16. Therefore, 𝒯s has an open leaf. It is immediate that 𝒯s 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 Ri and assume 𝒫i is a poset tree. We may additionally assume that 𝒫i is binary and that 𝒫i[i+1] is nonempty (that is, 𝒫i has level i+1). If it does not, then Ri 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, i and s. For 𝒫i satisfying the assumptions from the previous paragraph, the corresponding predicates hold in the limit – there is s0 such that they are true when s>s0:

Property (1).

Immediate.

Property (2).

Recall that s=max(s,|Ts|+1). For large enough s, r(𝒫i) becomes a member of 𝒫i,s. Once this happens, 𝒫i,s is always a poset tree.

Property (3).

The level i+1 of 𝒯 is nonempty by Lemma 17, it is present in 𝒯s for large enough s by construction. Above we assumed that the level i+1 of 𝒫i is nonempty.

Property (4).

For large enough s, 𝒯[i+1]𝒯s and (𝒫i)[i+1]𝒫i,s.

Let s0 be the least stage such that (1)-(4) hold for all stages ss0. In particular, it means that starting from stage s0, we have (𝒫i,s)[i+1]=(𝒫i)[i+1] and (𝒯s)[i+1]=(𝒯)[i+1].

If (5) does not hold at stage s0, then it will not hold anymore, and thus Ri is satisfied. So suppose (5) always holds starting from stage s0 and let f be the isomorphism from (𝒯s0)[i+1] to (𝒫i,s0)[i+1]. Note that this isomorphism is unique because 𝒯 is uniquely branching.

Observe that, at stage s02, the strategy for 𝒫i was not ready. If it were, then s0=s02 would be the least stage such that (1), (2), (3) and (4) hold for all even stages ss0, which would contradict our choice of s0. Therefore, at stage s02 all (i+1)-level nodes were withdrawn from F. Hence, at stage s0, the strategy for 𝒫i is ready and nodes from level i+1 are not in F. It means that we put some xj from level i+1 of 𝒯 into F. At stage s0, the subtree of 𝒯 with the root xj has fewer elements than the corresponding subtree of 𝒫i with root f(xj). And this property will hold forever because at any subsequent stage, the strategy is ready and xjF, and in that case we do nothing. Therefore, at any subsequent expansionary stage, the subtree of 𝒯 with root xj does not grow. It remains to observe that if there were an isomorphism g from 𝒯 to 𝒫i, it would have to map xj to f(xj), because 𝒯 and 𝒫i are isomorphic up to level i+1 and 𝒯 is uniquely branching so f has only one legitimate choice for the value f(xj).

We recall that a partial ordering =(L,) is called a join semilattice, meet semilattice, or lattice if, for any two elements a,b in , there exists a least upper bound (denoted ab), a greatest lower bound (denoted ab), or both, respectively. Join semilattices, meet semilattices, and lattices are also represented as algebraic structures, namely (L,), (L,), and (L,,), 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 (L,). For (semi)lattices, the order and the operations and are mutually definable. Specifically, xy if and only if xy=y, and xy if and only if xy=x.

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 x,y is well defined, 𝒯 is an order-theoretic join semilattice and, by Theorem 8, it has no punctual presentation. By defining xyyx, and arguing as above, 𝒯=(,) is a computable order-theoretic meet semilattice with no punctual copy.

Let xy denote the join of x and y in 𝒯. Consider the join semilattice (,). The join xy is a computable function of x,y: we run the construction from the proof of Theorem 8 and wait for a stage s at which both x and y enter Ts. Then we have two cases:

  1. 1.

    For -comparable x,y, we return the maximum of x,y with respect to .

  2. 2.

    For -incomparable x,y, the construction guarantees that TxTyTs, and thus xy can be computed from Ts.

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 xyxy=y. Hence, the relation xy 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 =({0},) be a punctual poset tree satisfying the following condition: for all x,y{0}, xyx1y1. We observe that 𝒯 via primitive recursive isomorphism φ:{0}. The root of is equal to 1.

Let =(,) be such that is a submodel of and 0x, for all x and x0, for all x{0}. It is easy to see that is a computable partial order. Moreover, is a lattice. The join of x,y{0} in is the same as in . The join of 0,x, where x, is x. The meet of x,y such that xy is x. The meet of x,y such that xy,yx is 0. 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 1 is the greatest element of and 0 is the least. We show that each a has a complement, that is, b such that ab=1 and ab=0. The construction of Theorem 8 guarantees that 0 is a branching node in 𝒯, and thus 1 is a branching node in . Let l,r be the two children of 1 in . 0 and 1 are complements of each other. Assume that a{0,1}. Either al or ar. If al, ar=1 and ar=0. Similarly, if ar, al=1 and al=0.

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 0 be the least element of . It is clear that ({0},)𝒯. Now, given a primitive recursive bijection f:{0}, we define a punctual structure 𝒯=(,) as follows: xyf(x)f(y). The primitive recursiveness of follows from the following equivalences: xyf(x)f(y)f(x)f(y)=f(y) 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 {,,C,0,1}. Informally speaking, one can think of the signature functions as the usual set-theoretic operations: union, intersection, and complement. In addition, 0 is a least element, and 1 is a greatest element.

Let be a Boolean algebra. A function f: is called a modality if f satisfies the following two properties:

  • f(ab)=f(a)f(b) for all a,b,

  • f(0)=0.

Informally, one can view f(x) as the result of applying the possibility operator =f to the “statement” x. If f is a modality, then the structure (,f) 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 𝒫e (in the signature of modal algebras), we want 𝒫e to show an element ce with some specific properties. Namely, either ce generates (via the function f𝒫e) an infinite substructure inside 𝒫e, or ce is a part of an f𝒫e-cycle of some finite size Ne. 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 p of Ne from appearing in the possible sizes of the f𝒜-cycles. Preventing such p 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 𝒜≇𝒫e. 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 Re-strategy has to work with a specifically selected tuple a¯=a0,a1,,aM of witnesses (in place of just one element ce that was used in the proof idea), and this a 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: xy if and only if xy=y. An element a is an atom if a is a minimal non-zero element in , i.e., 0<a and there is no b with 0<b<a.

By Atom() we denote the set of atoms of . The Fréchet ideal Fr() is the ideal of generated by the set Atom(). Notice that the ideal Fr() contains precisely the finite sums of atoms.

Let a be an element from a Boolean algebra . We put a0=C(a) and a1=a.

Let a¯=a0,a1,,an be a tuple of elements from , and let ε¯=(ε0,ε1,,εn){0,1}n+1. We define a¯ε¯=a0ε0a1ε1anεn. 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 a¯=a0,,an be a tuple from . Then the subalgebra gr(a¯) generated by the set {a0,,an} contains precisely the finite sums of the elements a¯ε¯, ε{0,1}n+1.

In addition, if ai{0,1} and aiaj for ij, then the finite subalgebra gr(a¯) has at least n+2 atoms. (Notice that an atom of the subalgebra gr(a¯) 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 g be an arbitrary map from the set Atom() to . Then the function

F[g](x)={0,if x=0,g(a0)g(a1)g(an),if x=a0a1an,aiAtom(),1,if xFr(),

is a modality. In addition, if the algebra is computable, and the sets Atom() and Fr() are computable, and the function g is computable, then the modality F[g] is also computable.

Definition 21 (forward orbit).

Let (,f) be a modal algebra. For an element a, the forward orbit of a (with respect to f) is the set FOrb(a)={f(n)(a):n}.

Now we are ready to start the proof of Theorem 10. By B() 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 B()×B() such that the sets Atom() and Fr() are computable.

In what follows, we identify with B()×B(), and we use the following notations:

  • 0=(1B(),0B()) and 1=(0B(),1B()).

  • Let {wi:i} be a computable list of all atoms of B(). We put ui=(wi,0B()) and vi=(0B(),wi).

It is clear that {ui,vi:i} is a computable list of all atoms of . In addition, we have ui<0 and vi<1 for all i.

By Lemma 20, it is sufficient for us to construct a computable map g:Atom(). Then the desired computable modal algebra 𝒜 is defined as

𝒜=(,F[g]). (6)

4.1 Preparations for the Construction of 𝒈

Firstly, we describe the basic module of the construction of the map g, we call this module:

Adding a p-cycle to the map g.

Given an odd prime number p, we find the least i such that the value g(ui) is not yet defined. We also choose the least j such that g(vj) is undefined.

Let k=p2. For 0m<k, we put: g(ui+m)=vj+m, g(vj+m)=ui+m+1, and g(ui+k)=ui.

We also say that the set {ui+m:mk}{vj+:<k} is a p-cycle. This concludes the description of the basic module.

We will ensure the following property of our (future) construction:

(#)

For each odd prime p, we add at most one p-cycle to g.

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 p such that we have added a p-cycle to g. Let a𝒜 and a0. Then the element a satisfies precisely one of the following three cases:

  1. 1.

    aFr() and F[g](a)=1.

  2. 2.

    aFr() and F[g](a)=a.

  3. 3.

    aFr() and card(FOrb(a))=q1q2qn for some n1 and some odd primes qi such that qiqj for ij. (Note that here a qi-cycle has been added to g at some stage of the construction.) In addition, if 0i<j<card(FOrb(a)), then F[g](i)(a)F[g](j)(a).

Furthermore, if aFr(), a0 and ak for some k{0,1}, then the element a satisfies Case 3.

Proof.

If aFr(), then Lemma 20 defines F[g](a)=1. Thus, assume that aFr() and F[g](a)a.

By Property (#), for each prime p the algebra 𝒜 contains at most one p-cycle. We choose all prime numbers q1,q2,,qn such that:

  • there exists an atom wAtom() such that wa and w belongs to the (unique) qi-cycle; and

  • there exists wAtom() such that wa and w belongs to the qi-cycle.

Notice that (at least one) such prime qi exists. Indeed, if there are no such primes qi, then the element a satisfies the following condition:

if an atom w belongs to a q-cycle and wa, then every atom from this q-cycle lies -below a.

This condition implies that F[g](a) must be equal to a (which contradicts our assumption).

Define M=q1q2qn. Then a straightforward computation shows the following: F[g](M)(a)=a and for all i,j we have: if 0i<j<M, then F[g](i)(a)F[g](j)(a). Hence, card(FOrb(a))=M. We deduce that every element a0 satisfies one of the three cases of the lemma.

Now suppose that aFr(){0} and a0. Then for some i, we have uiAtom() and uia. On the other hand, for all j, we have vjAtom() and vja. By choosing vj from the q-cycle of the atom ui, we deduce that a must satisfy Case 3. (If aFr(){0} and a1, 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 (𝒜,0,1) has a punctual copy. Thus, we fix a uniformly computable list (𝒫e)e containing all punctual structures in the signature {,,C,0,1,f}{0,1}. We satisfy the following requirements:

Re:

The structure (𝒜,0,1) is not isomorphic to 𝒫e.

In what follows, we will abuse the notations: we identify the structures 𝒜 and (𝒜,0,1).

At a stage s, we will have a finite list of active requirements. Each active requirement Re possesses a corresponding witness ce𝒫e. Active requirements may be (forever) deactivated. In addition, at a stage s we will have at most one requirement Re0 on the alert. The intended (full) life-cycle of a given requirement Re is as follows:

inactive on the alert active deactivated.

Along the construction, we always do the following background monitoring procedure. At a stage s, for each 𝒫e with es, we consider the finite set Se,s={0𝒫e,1𝒫e,0,𝒫e,1,𝒫e}{x:xs}. Assume that at the stage s we have witnessed one of the following conditions:

  1. (a)

    Some of the elements from the set

    Xe,s={a¯ε¯:a¯=(a1,,an), 1ncard(Se,s),aiSe,s,ε¯{0,1}n}

    do not satisfy the axioms of Boolean algebras or the axioms of modal algebras. (Notice that here the set Xe,s is the “potential” Boolean subalgebra gr𝒫e(Se,s) generated by the set Se,s inside 𝒫e.)

  2. (b)

    0,𝒫e1,𝒫e1𝒫e or 0,𝒫e1,𝒫e0𝒫e or f𝒫e(0,𝒫e)1𝒫e or f𝒫e(1,𝒫e)1𝒫e.

  3. (c)

    There exist k{0,1} and x,ySe,s{0𝒫e,k,𝒫e} such that xy=k,𝒫e, xy=0𝒫e, and

    • either f𝒫e(x)1𝒫e and f𝒫e(y)1𝒫e, or

    • f𝒫e(x)=1𝒫e and f𝒫e(y)=y, or

    • f𝒫e(x)=1𝒫e and 1𝒫e{f𝒫e(m)(y):ms}.

  4. (d)

    There exist k{0,1} and x,ySe,s such that xy=0𝒫e, x𝒫ek,𝒫e, y𝒫ek,𝒫e, and f𝒫e(x)=f𝒫e(y)=1𝒫e.

Then we declare the requirement Re deactivated. Indeed, in this case the structure 𝒫e cannot be isomorphic to (𝒜,0,1). To observe this non-isomorphism for Condition (c) above, we recall the following fact: if xy=0, xy=0 and x,y{0,0}, then precisely one of the elements b{x,y} satisfies bFr() and F[g](b)=1. By Lemma 22, the remaining element a{x,y} satisfies aFr() and F[g](a)a. In addition, we have 1FOrb(a).

To observe non-isomorphism for Condition (d), we recall the following: if x0 and F[g](x)=1, then xFr() and every y0C(x) satisfies yFr() and F[g](y)1.

Due to the described monitoring procedure, in the main construction given below, we may assume (without loss of generality) that every considered structure 𝒫e has the following properties, for k{0,1}:

(P.0)

The reduct of 𝒫e to the signature {,,C,0,1,f} is a punctual modal algebra. In addition, 0,𝒫e1,𝒫e=1𝒫e, 0,𝒫e1,𝒫e=0𝒫e, and f𝒫e(0,𝒫e)=f𝒫e(1,𝒫e)=1𝒫e.

(P.1)

If y𝒫ek,𝒫e, y0𝒫e and f𝒫e(y)1𝒫e, then f𝒫e(y)y and 1𝒫eFOrb𝒫e(y).

(P.2)

If x1,x2,,xn𝒫ek,𝒫e and xixj=0𝒫e for ij, then at most one element y{x1,x2,,xn} satisfies f𝒫e(y)=1𝒫e.

Now we are ready to describe the main construction. Let (ps)s1 be the increasing list of all odd prime numbers.

Construction.

At stage 0, there are no active requirements. We declare that the requirement R0 is on the alert.

Stage 𝒔>𝟎.

Roughly speaking, the main goal of the stage s is to decide whether to add a ps-cycle to the map g. In addition, our actions will ensure the following property:

()

Suppose that by the end of the stage s, an active requirement Re has a witness ce𝒫e. Then ce satisfies one of the following two conditions:

  • either the forward orbit FOrb𝒫e(ce) is infinite, or

  • the set FOrb𝒫e(ce) is finite and the following implication holds: if r=card(FOrb𝒫e(ce)) has a form r=q1q2qn, where n1 and 2<q1<q2<<qn are prime numbers, then some prime q>ps must divide r.

Intuitively speaking, the choice of such form r=q1q2qn is dictated by Lemma 22. If the decomposition of r has any other form, then Lemma 22 ensures that 𝒜≇𝒫e.

If the structure 𝒜 does not contain a ps-cycle by the end of the stage s, then we say that the prime ps is forbidden from entering the structure 𝒜.

Our actions at the stage s go as follows. If there is a requirement Re0 which is currently on the alert, then firstly we execute the following strategy.

4.2.1 Strategy for 𝑹𝒆 Which Is on the Alert

Let 𝒟s be the Boolean subalgebra of generated by the following elements: 0, 1, and the elements of all q-cycles added to g at stages t<s. By Lemma 19, the algebra 𝒟s is finite, and one can computably recover this structure 𝒟s. In addition, Lemma 20 ensures that the values F[g](x) are defined for all x𝒟s.

Define M=card(𝒟s). Consider the -least elements b0<b1<<bM1 from the structure 𝒫e such that bi{0𝒫e,1𝒫e,0,𝒫e,1,𝒫e}. We define the following finite Boolean subalgebra of 𝒫e: 𝒬s=gr𝒫e({0,𝒫e,1,𝒫e,b0,b1,,bM1}).

By Lemma 19, the algebra 𝒬s has at least M+3 atoms. Applying Property (P.2) of the construction, we deduce that at most two of these atoms x satisfy f𝒫e(x)=1𝒫e (indeed, at most one atom below 0,𝒫e, and at most one atom below 1,𝒫e). Therefore, among the atoms of 𝒬s we can find (M+1)-many pairwise distinct elements a0,a1,,aM such that f𝒫e(ai)1𝒫e, ai0𝒫e, and aiaj=0𝒫e for ij.

By Property (P.1), we obtain that f𝒫e(ai)ai and 1𝒫eFOrb𝒫e(ai). We define L=j=1spj. We compute the values f𝒫e(j)(ai),for iM and jL. Then one of the following five cases is satisfied:

Case (i.a).

There exists ai such that the function f𝒫e is not injective on the set {f𝒫e(j)(ai):jL} (i.e., there exist j1<j2L such that f𝒫e(j1)(ai)f𝒫e(j2)(ai) and f𝒫e(j1+1)(ai)=f𝒫e(j2+1)(ai)).

Then we (safely) declare the requirement Re deactivated. Indeed, by item (3) of Lemma 22, the structure 𝒫e cannot be isomorphic to our structure 𝒜. In all cases (i.X) below, we will assume that the function f𝒫e is injective on the set {f𝒫e(j)(ai):jL}.

Case (i.b).

There exists ai with the following properties:

  • FOrb(ai){f𝒫e(j)(ai):jL} and N=card(FOrb(ai)).

  • Consider the prime decomposition N=q1α1q2α2qα, where qjqk for jk and αj1. For some j, either qj has already been forbidden from entering 𝒜, or qj=2, or αj2.

Then by Lemma 22, our structure 𝒜 cannot be isomorphic to 𝒫e, since 𝒜 does not contain elements bFr() with card(FOrb(b))=N. We declare the requirement Re deactivated.

Case (i.c).

Neither of Cases (i.a) and (i.b) is satisfied, and there exists ai with the following properties:

  • FOrb(ai){f𝒫e(j)(ai):jL} and N=card(FOrb(ai)).

  • For some ts, the prime pt divides N.

We declare the requirement Re active, and we set ce=ai. Note the following: if t>s, then Re will definitely satisfy Property () at the end of stage s.

Case (i.d).

Neither of Cases (i.a)–(i.c) is satisfied, and there exists ai such that for all j<kL, we have f𝒫e(j)(ai)f𝒫e(k)(ai). Notice that this condition is equivalent to the condition card(FOrb(ai))L+1. We declare the requirement Re active, and we define ce=ai.

Case (i.e).

Suppose that neither of Cases (i.a)–(i.d) is satisfied. Then every ai, iM, has the following properties:

(e.1)

FOrb(ai){f𝒫e(j)(ai):jL} and Ni=card(FOrb(ai))L.

(e.2)

The number Ni has prime decomposition Ni=qi,1qi,i, where qi,jqi,k for jk, and 3qi,j<ps and qi,j has not been forbidden from entering 𝒜.

We show that in this case the structure 𝒫e is not isomorphic to 𝒜. In order to prove this, it is enough to establish the following fact:

Claim 23.

𝒜 does not contain (M+1)-many pairwise disjoint elements a satisfying:

card(FOrb(a))=Ni for some Ni with Property (e.2). (7)
Proof.

Suppose that an element a𝒜 satisfies Eq. (7). Consider the prime number qi,1. By the proof of Lemma 22, there exists an atom aAtom() such that aa and a belongs to a qi,1-cycle. By the definition of the finite algebra 𝒟s, we have a𝒟s. We define θ(a)=a. We notice the following fact: if ab=0, then θ(a)θ(b). Indeed, if θ(a)=θ(b), then 0θ(a)ab.

Now, towards a contradiction, assume that 𝒜 contains (M+1)-many pairwise disjoint elements a satisfying Eq. (7). Then the algebra 𝒟s contains at least (M+1)-many pairwise distinct elements θ(a). This contradicts the choice of M=card(𝒟s).

Indeed, recall that aiaj=0𝒫e for ij. Hence, the structure 𝒫e does contain (M+1)-many disjoint elements a0,,aM satisfying Eq. (7). Thus, Claim 23 implies that 𝒫e≇𝒜. Therefore, in Case (i.e), we safely declare the requirement Re deactivated.

This concludes the description of the strategy for Re=Re0 which is on the alert. After executing this strategy, one-by-one, we execute strategies for the currently active requirements Re (see below). Notice that in Cases (i.c) and (i.d) above, this execution also includes our requirement Re0 (Re0 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 Re was active at the end of the previous stage s1, then it satisfied Property () at that moment. Consider the witness ce for Re. Recall that

L=j=1spj. (8)

We compute the values f𝒫e(i)(ce), for all iL. One of the following two cases is satisfied:

Case (ii.a).

Suppose that f𝒫e(j)(ce)=f𝒫e(k)(ce) for some j<kL. Then we have FOrb𝒫e(ce){f𝒫e(i)(ce):iL}. In particular, the set FOrb𝒫e(ce) is finite. For N=card(FOrb𝒫e(ce)), we compute its prime decomposition N=q1α1q2α2qα.

Similarly to Case (i.b), if for some i either qi was already forbidden, or qi=2, or αi2, then 𝒫e≇𝒜. Thus, we declare such Re deactivated. Hence, in what follows we may assume that N=q1q2q, where 2<q1<q2<<q.

If some qi equals ps, then we forbid adding a ps-cycle to the map g. Since 𝒜 will not have ps-cycles, by Lemma 22, we deduce that 𝒫e is not isomorphic to 𝒜. We safely declare the requirement Re deactivated.

If ps{qi:i}, then Re stays active. Here we claim that some qi must be equal to pt for some t>s. Indeed, if Re was already active at the stage s1, then this fact is guaranteed by the “(s1)-version” of Property (). Otherwise, Re moved from being on the alert to being active at the stage s. But then this move was triggered by Case (i.c), and some pt with t>s must divide N. We observe that in Case (ii.a), the requirement Re will satisfy Property () at the end of the stage s.

Case (ii.b).

Otherwise, f𝒫e(j)(ce)f𝒫e(k)(ce) for all j<kL. Then the requirement Re stays active. Observe that here N=card(FOrb𝒫e(ce))L+1.

In Case (ii.b) we need to show that the requirement Re will still satisfy Property () by the end of the stage s. Towards a contradiction, assume that Property () fails. Then the set FOrb𝒫e(ce) is finite, and we have N=q1q2q, where the primes qi satisfy 2<q1<q2<<qps. By Eq. (8), we obtain that N=qq1q2q1psps1ps(2)ps(1)L. This contradicts the fact that N>L.

We deduce that in each of the two cases, an active requirement Re will satisfy Property () by the end of the stage s. This concludes the description of the strategy for an active Re.

If by the end of the stage s, no strategy has forbidden to add a ps-cycle to g, then we proceed as follows:

  • Add a ps-cycle to the map g.

  • Find the least i such that the requirement Ri has never been on the alert before. Declare this Ri being on the alert.

4.3 Verification

Lemma 24.

For every aAtom(), the value g(a) 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 ps-cycle for infinitely many s1. Towards a contradiction, assume that for every s>s0, the structure 𝒜 never gets a ps-cycle. Then for every s>s0, the requirement Rs is never declared on the alert. Consequently, such Rs never becomes active.

Choose a large enough stage s>s0 with the following property: if a requirement Re, where es0, is eventually declared deactivated, then Re was deactivated before the stage s. Since the ps-cycle is forever forbidden, this forbiddance was triggered by the following action: at the stage s, some currently active requirement Ri, where is0, forbade ps, and after that this Ri was deactivated. But this contradicts the choice of the stage s. We deduce that g(a) is defined for all atoms a from . Lemma 24 is proved.

Lemma 25.

Every requirement Re is satisfied.

Proof.

Since our construction adds a ps-cycle for infinitely many s (as discussed in Lemma 24), every requirement Re is eventually declared being on the alert. If a requirement Re is eventually deactivated, then (as discussed in detail in the construction description) we have 𝒫e≇𝒜 and Re is satisfied.

Suppose that a requirement Re is never deactivated. Then there exists a stage s0 such that Re is active at every stage ss0. Consider the corresponding witness ce𝒫e. If the forward orbit FOrb𝒫e(ce) is infinite, then by Lemma 22, 𝒫e is not isomorphic to 𝒜. Therefore, we may assume that the set FOrb𝒫e(ce) is finite.

Since N=card(FOrb𝒫e(ce))<ω, there exists a large enough stage ss0 such that for every ss, the active requirement Re satisfies Case (ii.a) at the stage s. The requirement Re is never deactivated, hence, we have N=q1q2q for some 1 and some primes 2<q1<q2<<q. But then Property () of the construction implies that for every ss, there exists a prime q>ps such that q divides N. Hence, N has infinitely many divisors, which gives a contradiction. We conclude that for every e, the structure 𝒜 is not isomorphic to 𝒫e.

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(n,log(n)). 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.