In 2017, Kalimullin, Melnikov and Ng initiated the systematic study of the primitive recursive content of mathematics. The main idea of such studies is eliminating unbounded search from various abstract algorithms in computable structure theory. The main definition in the theory of punctual structures is the following. An algebraic structure is punctual (or fully primitive recursive) if its domain is the set of natural numbers and the operations and relations are represented by primitive recursive functions. An instance of this is called a punctual presentation.

In computable structure theory, computable presentations are viewed up to computable isomorphism. In the punctual setting, this is no longer straightforward due to the fact that the inverse of a primitive recursive bijection does not need to be primitive recursive. We notice that this induces a natural partial order on punctual presentation. This partial order induces a degree structure on all punctual presentations \(\mathcal{M}\) which we call the punctual degrees of \(\mathcal{M}\) and denote \(PR(\mathcal{M})\).

We study the properties of the punctual degrees for linear orders. In [1], we showed that the punctual degrees of \((\mathbb{Z},<)\) is dense. In contrast, Koh, Melnikov and Ng [2] have recently proven that the punctual degrees of \(\mathbb{Q}\) is not dense.

We study this further investigating whether we can embed the atomless Boolean algebra into the punctual degrees for linear orders. The first step towards this is to build a diamond, where we construct presentations \(A,B,C,D\) so that \(C\) and \(D\) are incomparable, \(A=\inf(C,D)\) and \(B=\sup(C,D)\). We will discuss the complications and techniques required to embed the diamond and atomless Boolean algebra in the punctual degrees of rigid linear orders and the rational numbers. All work presented is joint work with Dorzhieva.

Bibliography

1. Koh, Heer Tern and Melnikov, Alexander and Ng, Keng Meng, A non-density aspect of the rationals, to appear.
2. Dorzhieva, Marina and Downey, Rod and Hammatt, Ellen and Melnikov, Alexander and Ng, Keng Meng, Punctually presented structures II: comparing presentations, to appear.