COMPUTABLE STRUCTURES OF RANK omega(CK)(1)

摘要

For countable structure, "Scott rank" provides a measure of internal, model-theoretic complexity. For a computable structure, the Scott rank is at most omega(CK)(1) + 1. There are familiar examples of computable structures of various computable ranks, and there is an old example of rank omega(CK)(1) + 1. In the present paper, we show that there is a computable structure of Scott rank omega(CK)(1). We give two different constructions. The first starts with an arithmetical example due to Makkai, and codes it into a computable structure. The second re- works Makkai's construction, incorporating an idea of Sacks.