The jump operation for structure degrees |
| |
Authors: | V Baleva |
| |
Institution: | (1) Sofia University, Bulgaria;(2) 6, allée Martin Luther King, 76620 Le Havre, France |
| |
Abstract: | One of the main problems in effective model theory is to find an appropriate information complexity measure of the algebraic
structures in the sense of computability. Unlike the commonly used degrees of structures, the structure degree measure is
total. We introduce and study the jump operation for structure degrees. We prove that it has all natural jump properties (including
jump inversion theorem, theorem of Ash), which show that our definition is relevant. We study the relation between the structure
degree jump (in the sense of Soskov) and the jump degrees of a structure (in the sense of Jockusch) and give necessary and
sufficient conditions for their existence in the terms of structure degrees. We show some properties, distinguishing the structure
degrees from the enumeration degrees. |
| |
Keywords: | 03D30 |
本文献已被 SpringerLink 等数据库收录! |
|