Bulletin of Symbolic Logic 6 (2):197-212 (2000)

Abstract
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. Several different notions of effectiveness of model-theoretic structures have been investigated. This communication is concerned withcomputablestructures, 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 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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/421207
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 63,219
Through your library

References found in this work BETA

Intrinsically Gs;0alpha; Relations.E. Barker - 1988 - Annals of Pure and Applied Logic 39 (2):105-130.

View all 14 references / Add more references

Citations of this work BETA

View all 6 citations / Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total views
35 ( #308,849 of 2,448,425 )

Recent downloads (6 months)
1 ( #449,843 of 2,448,425 )

How can I increase my downloads?

Downloads

My notes