Title: Effective Reducibilities on Structures and Degrees of Presentability

Summary: We consider presentations of structures in admissible sets and some effective reducibilities between structures and their degrees of presentability. Degrees of Sigma-definability of structures, as well as degrees of presentability with respect to different effective reducibilities, are natural measures of complexity which are total, i.e. defined for any structure. We also consider properties of structures invariant under various effective reducibilities, and study how a degree of presentability of a structure depends from a domain for presentations ( i.e. from the choice of an admissible set).

PDF (original)

Corrections (1)

PDF (corrected)