zbMATH — the first resource for mathematics

Copyable structures. (English) Zbl 1327.03037
In this paper, a class \({\mathbb K}\) of mathematical structures is called listable if there exists a Turing functional which, for every oracle \(X\), produces an \(X\)-computable sequence of structures listing all the \(X\)-computable structures in \({\mathbb K}\), and \({\mathbb K}\) has the low property if, for every \(X,Y\in 2^{\omega}\) with \(X'\equiv_TY'\) and every structure \({\mathcal A}\in {\mathbb K}\), we have that \({\mathcal A}\) has an \(X\)-computable copy if and only if \(A\) has a \(Y\)-computable copy. (The author notes that these notions had already been studied for some classes of structures by several authors.) In this paper, the author also introduced the notions of copyable and diagonalizable classes of structures and showed how these notions are connected to listability and low properties.
With a class of structures \({\mathbb K}\), a game \(G({\mathbb K})\) of two players \(C\) and \(D\) is associated, in which each player builds a structure in \({\mathbb K}\). The player \(C\) tries to get both structures isomorphic (to copy), and \(D\) tries to get these structures different (to diagonalize). By definition, if \(C\) has a computable winning strategy, then \({\mathbb K}\) is copyable, and if \(D\) has a winning strategy, then \({\mathbb K}\) is diagonalizable. The classes of structures with the low property are characterized as the classes whose structural jumps are listable.
The paper also contains a number of other related results. In particular, it is proved that each listable class is copyable, the class of infinite linear orderings with no maximal elements is copyable, and the class of linear orderings is diagonalizable.

03D80 Applications of computability and recursion theory
03D45 Theory of numerations, effectively presented structures
06A05 Total orders
Full Text: DOI Euclid Link