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 De (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 Arithme...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of symbolic logic 2007-03, Vol.72 (1), p.305-323
Main Authors: Csima, Barbara F., Harizanov, Valentina S., Hirschfeldt, Denis R., Soare, Robert I.
Format: Article
Language:English
Subjects:
Arithmetic
Atomic theory
Mathematical logic
Mathematical models
Mathematical theorems
Model theory
Nonstandard models
Peano axioms
Predicates
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 De (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.
ISSN:0022-4812
1943-5886
DOI:10.2178/jsl/1174668397