Imagen de Portada
Código QR

BOUNDING HOMOGENEOUS MODELS.

A Turing degree d is homogeneous bounding if every complete decidable (CD) theory has a d-decidable homogeneous model A, i.e., the elementary diagram D(A) has degree d. It follows from results of Macintyre and Marker that every PA degree (i.e., every degree of a complete extension of Peano Arithmeti...

Descripción completa

Publicado en:Journal of Symbolic Logic Vol. 72; no. 1; pp. 305 - 324
Autores principales: Csima, Barbara F., Harizanov, Valentina S., Hirschfeldt, Denis R., Soare, Robert I.
Formato: Artículo
Publicado: Cambridge University Press Mar2007
Materias:
Turing (Computer program language)
Computable functions
Combinatorics
Mathematical models
Mathematical logic
Recursive sequences (Mathematics)
Recursion theory
Abstract algebra
Acceso en línea:Ver este registro en EBSCOhost
Sumario:A Turing degree d is homogeneous bounding if every complete decidable (CD) theory has a d-decidable homogeneous model A, i.e., the elementary diagram D(A) has degree d. It follows from results of Macintyre and Marker that every PA degree (i.e., every degree of a complete extension of Peano Arithmetic) is homogeneous bounding. We prove that in fact a degree is homogeneous bounding if and only if it is a PA degree. We do this by showing that there is a single CD theory T such that every homogeneous model of T has a PA degree.