Hostname: page-component-7b7567c8c-p67k6 Total loading time: 0 Render date: 2026-11-19T21:27:31.398Z Has data issue: false hasContentIssue false

Degree Spectra of Relations on Computable Structures

Published online by Cambridge University Press:  15 January 2014

Denis R. Hirschfeldt*
Affiliation:
School of Mathematical and Computing Sciences, Victoria University of Wellington, New zealand E-mail: Denis.Hirschfeldt@mcs.vuw.ac.nz

Extract

There has been increasing interest over the last few decades in the study of the effective content of Mathematics. One field whose effective content has been the subject of a large body of work, dating back at least to the early 1960s, is model theory. (A valuable reference is the handbook [7]. In particular, the introduction and the articles by Ershov and Goncharov and by Harizanov give useful overviews, while the articles by Ash and by Goncharov cover material related to the topic of this communication.)

Several different notions of effectiveness of model-theoretic structures have been investigated. This communication is concerned with computable structures, that is, structures with computable domains whose constants, functions, and relations are uniformly computable.

In model theory, we identify isomorphic structures. From the point of view of computable model theory, however, two isomorphic structures might be very different. For example, under the standard ordering of ω the success or relation is computable, but it is not hard to construct a computable linear ordering of type ω in which the successor relation is not computable. In fact, for every computably enumerable (c. e.) degree a, we can construct a computable linear ordering of type ω in which the successor relation has degree a. It is also possible to build two isomorphic computable groups, only one of which has a computable center, or two isomorphic Boolean algebras, only one of which has a computable set of atoms. Thus, for the purposes of computable model theory, studying structures up to isomorphism is not enough.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable