Punctually universal structures

We investigate the primitive recursive content of various classical universalitytype results in algebra and combinatorics, including the algebraic closure theorem, the universality of the dense linear order, and the random graph, all with respect to primitive recursive isomorphic embeddings in the respective classes. In the case of fields, we show Rabin’s result can be improved to give a primitive recursive embedding of a punctual field into a punctual algebraic closure. In the case of linear orders, we show the analog of Rabin’s theorem using the linear order that obtained from the given one by densifying the adjacency intervals. We also show that in the computable setting, decidability of the adjacency relation describes the uniqueness of this ‘densification’ over the given order. In the case of the random graph, we prove the result in presence of primitive recursive Skolem function. We also show that, in contrast with an earlier result of Melnikov and Ng, it makes the notion of the random graph punctually robust.