UNIFORM PROCEDURES IN UNCOUNTABLE STRUCTURES

作者：Greenberg Noam^*; Melnikov Alexander G; Knight Julia F; Turetsky Daniel

来源：Journal of Symbolic Logic, 2018, 83(2): 529-550.

DOI：10.1017/jsl.2017.91

• relative computable categoricity
• effective Polish spaces
• admissible recursion theory

This article contributes to the general program of extending techniques and ideas of effective algebra to computable metric space theory. It is well-known that relative computable categoricity (to be defined) of a computable algebraic structure is equivalent to having a c.e. Scott family with finitely many parameters (e.g., [ID. The first main result of the article extends this characterisation to computable Polish metric spaces. The second main result illustrates that just a slight change of the definitions will give us a new notion of categoricity unseen in the countable case (to be stated formally). The second result also shows that the characterisation of computably categorical closed subspaces of R(n )contained in [17] cannot be improved. The third main result extends the characterisation to not necessarily separable structures of cardinality kappa using kappa-computability.

• 出版日期2018-6