A decidable Ehrenfeucht theory with exactly two hyperarithmetic models
type: Item
instance of: scholarly article
title: A decidable Ehrenfeucht theory with exactly two hyperarithmetic models
zbMATH Open document ID: 0733.03021
DOI: 10.1016/0168-0072(91)90053-O
author: Robert C. Reed
published in: Annals of Pure and Applied Logic
publication date: 1991-01-01T00:00:00Z
review text: T is an Ehrenfeucht theory if it has finitely many countable models up to isomorphism and is not \(\omega\)-categorical. T is persistently Ehrenfeucht if for every n-type \(\Gamma\) (x) of T, the theory \(\Gamma\) (c) in the language of T with a new constant c added is Ehrenfeucht. This lengthy paper is devoted to a proof of the following theorem. For each \(n<\omega\) there is a complete, decidable, persistently Ehrenfeucht theory T having exactly five non-isomorphic countable models: three decidable models and two models decidable exactly in the hyperarithmetic set H(n). By a theorem of Millar this is the best that can be achieved if a decidable Ehrenfeucht theory has a countable model which is not \(0''\)- decidable. The T exhibited is a theory of trees which is inspired by earlier examples of Millar and Peretyat'kin.
Mathematics Subject Classification ID: 03C15
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 4212016
zbMATH Keywords: Ehrenfeucht theory
zbMATH Keywords: countable models
zbMATH Keywords: persistently Ehrenfeucht
zbMATH Keywords: decidable models
zbMATH Keywords: hyperarithmetic set
zbMATH Keywords: theory of trees
reviewed by: J. M. Plotkin
MaRDI profile type: Publication
cites work: Model theory
cites work: Foundations of recursive model theory
cites work: Persistently Finite Theories with Hyperarithmetic Models
cites work: Q3690795
cites work: On complete theories with a finite number of denumerable models
cites work: Q5573961
description: scientific article; zbMATH DE number 4212016