Degrees of categoricity for prime and homogeneous models

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

3 Citations (Scopus)

Abstract

We study effective categoricity for homogeneous and prime models of a complete theory. For a computable structure S, the degree of categoricity of S is the least Turing degree which can compute isomorphisms among arbitrary computable copies of S. We build new examples of degrees of categoricity for homogeneous models and for prime Heyting algebras, i.e. prime models of a complete extension of the theory of Heyting algebras. We show that 0(ω+1) is the degree of categoricity for a homogeneous model. We prove that any Turing degree which is d.c.e. in and above 0(n), where 3 ≤ n < ω, is the degree of categoricity for a prime Heyting algebra.

Original languageEnglish
Title of host publicationSailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings
EditorsF Manea, RG Miller, D Nowotka
PublisherSpringer-Verlag GmbH and Co. KG
Pages40-49
Number of pages10
ISBN (Print)9783319944173
DOIs
Publication statusPublished - 1 Jan 2018
Event14th Conference on Computability in Europe, CiE 2018 - Kiel, Germany
Duration: 30 Jul 20183 Aug 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10936 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th Conference on Computability in Europe, CiE 2018
CountryGermany
CityKiel
Period30.07.201803.08.2018

Keywords

  • Autostability spectrum
  • Categoricity spectrum
  • Computable categoricity
  • Computable structure
  • Degree of categoricity
  • Heyting algebra
  • Homogeneous model
  • Prime model
  • COMPUTABLE CATEGORICITY
  • SPECTRA
  • AUTOSTABILITY

Fingerprint

Dive into the research topics of 'Degrees of categoricity for prime and homogeneous models'. Together they form a unique fingerprint.

Cite this