Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T17:40:25.723Z Has data issue: false hasContentIssue false

Computably categorical structures and expansions by constants

Published online by Cambridge University Press:  12 March 2014

Peter Cholak
Affiliation:
Department of Mathematics, University of Notre Dame, Notre Dame, IN, 46556, USA. E-mail: Peter.Cholak.1@nd.edu
Sergey Goncharov
Affiliation:
Department of Mathematics, Novosibirsk University, Novosibirsk, Russia E-mail: gonchar@imi.nsu.nsk.su
Bakhadyr Khoussainov
Affiliation:
Department of Mathematics, Cornell University, Ithaca, NY 14853., USADepartment of Computer Science, University of Auckland, Auckland, New Zealand E-mail: bmk@cs.auckland.ac.nz
Richard A. Shore
Affiliation:
Department of Mathematics, Cornell University, Ithaca, NY 14853., USA E-mail: shore@math.cornell.edu

Extract

Effective model theory is the subject that analyzes the typical notions and results of model theory to determine their effective content and counterparts. The subject has been developed both in the former Soviet Union and in the west with various names (recursive model theory, constructive model theory, etc.) and divergent terminology. (We use “effective model theory” as the most general and descriptive designation. Harizanov [6] is an excellent introduction to the subject as is Millar [13].) The basic subjects of model theory include languages, structures, theories, models and various types of maps between these objects. There are many ways to introduce considerations of effectiveness into the area. The two most prominent derive from starting, on the one hand, with the notion of a theory and its models or, on the other, with just structures.

If one begins with theories, then a natural version of effectiveness is to consider decidable theories (i.e., ones with a decidable (equivalently, computable or recursive) set of theorems). When one moves to models and wants them to be effective, one might start with the requirement that the model (of any theory) have a decidable theory (i.e., Th (), the set of sentences true in , is decidable). Typically, however, one wants to be able to talk about the elements of the model as well as its theory in the given language. Thus one naturally considers the model as a structure for the language expanded by adding a constant ai, for each element ai of . Of course, one requires that the mapping from the constants to the corresponding elements of be effective (computable). We are thus lead to the following basic definition:

A structure or model is decidable if there is a computable enumeration ai of A, the domain of , such that Th(, ai,) is decidable. (Of course, ai, is interpreted as ai, for each i Є ω.)

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1999

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