摘要
Hughes Aircraft Company, P.O. Box 92912, Los Angeles, California 90009
Consider those structures that consist of a countable universe and a finite number of predicates and functions. Let = ‹∣∣, P 1, …, Pn , f 1, …, fm › be such a structure. We will restrict our consideration to structures, , whose universe, ∣∣, is a set of natural numbers, and thus we will be able to apply the notions of recursion theory to structures. Using deg(S) to refer to the degree of unsolvability of a set S, we can assign a degree of unsolvability to the structure by defining deg() to be the least upper bound of the degrees of the universe, predicates, and functions of . If we view as a presentation of the class of all structures which are isomorphic to (in the usual sense), then the deg() can be called the degree of the presentation .
While deg() is a natural degree to assign to the structure , it is not the only possibility. Indeed since a structure may have isomorphic presentations with different degrees, deg() has the deficiency of not being isomorphically invariant. We can assign degrees to some (but not all) structures in an isomorphically invariant fashion by looking at the class of the degrees of all presentations isomorphic to . If this class of degrees has a least element, we define it to be the degree of the isomorphism class of which we write deg([]).
(Received March 09 1979)
(Revised February 14 1980)
摘要译文
休斯飞机公司，P.O.箱92912，洛杉矶，加利福尼亚州90009
考虑这些结构，它由一个可数宇宙和谓词和功能的有限数量的。让= \u003c||，P 1，...，的Pn中，f 1，...，FM\u003e是这样的结构。我们会限制我们考虑的结构，它的宇宙，||，是一组自然数，因此，我们就可以递归论的概念应用到结构。使用度（S）是指一组S的不可解的程度，我们可以通过定义度分配一个程度不可解到该结构（）是最小上界宇宙，谓词和功能的程度的。如果我们认为作为一个演示文稿的类，它是同构的（通常意义上的）所有结构的，则度（）可以称得上是表现的程度。
而度（）是一种天然的程度分配给该结构，它不是唯一的可能性。事实上，由于结构可能有同构的演讲有不同程度，度（）已经不是同构不变的不足。我们可以通过观察类的所有演讲同构度的一个同构不变的方式分配学位的一些（但不是全部）结构。如果此类的程度有一个最小元素，我们把它定义为其中我们写度（[]）同构类的程度。
（收稿1979年3月9日）
（修订1980年2月14日）
Linda Jean Richter. Degrees of Structures[J]. The Journal of Symbolic Logic, 1981,46(4): 723 - 731