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)