Index sets and Scott sentences

Archive for Mathematical Logic 53 (5-6):519-524 (2014)
  Copy   BIBTEX

Abstract

For a computable structure A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{A}}$$\end{document}, there may not be a computable infinitary Scott sentence. When there is a computable infinitary Scott sentence φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varphi}$$\end{document}, then the complexity of the index set I\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${I}$$\end{document} is bounded by that of φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varphi}$$\end{document}. There are results giving “optimal” Scott sentences for structures of various familiar kinds. These results have been driven by the thesis that the complexity of the index set should match that of an optimal Scott sentence. In this note, it is shown that the thesis does not always hold. For a certain subgroup of Q\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{Q}}$$\end{document}, there is no computable d-Σ2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma_2}$$\end{document} Scott sentence, even though the index set is d-Σ20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^0_2}$$\end{document}.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,202

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Scott's problem for Proper Scott sets.Victoria Gitman - 2008 - Journal of Symbolic Logic 73 (3):845-860.
Index sets and parametric reductions.Rod G. Downey & Michael R. Fellows - 2001 - Archive for Mathematical Logic 40 (5):329-348.
Kleene index sets and functional m-degrees.Jeanleah Mohrherr - 1983 - Journal of Symbolic Logic 48 (3):829-840.
Polish group actions and effectivity.Barbara Majcher-Iwanow - 2012 - Archive for Mathematical Logic 51 (5-6):563-573.
Immunity and Hyperimmunity for Sets of Minimal Indices.Frank Stephan & Jason Teutsch - 2008 - Notre Dame Journal of Formal Logic 49 (2):107-125.
Bounded Scott Set Saturation.Alex M. McAllister - 2002 - Mathematical Logic Quarterly 48 (2):245-259.
The 3-Stratifiable Theorems of.Marcel Crabbé - 1999 - Notre Dame Journal of Formal Logic 40 (2):174-182.
A formalisation of the "step forward - step backward" reasoning.Piotr Lukowski - 2001 - Anales Del Seminario de Historia de la Filosofía 18:109.
Index sets for ω‐languages.Douglas Czenzer & Jeffrey B. Remmel - 2003 - Mathematical Logic Quarterly 49 (1):22-33.

Analytics

Added to PP
2014-03-05

Downloads
20 (#720,454)

6 months
5 (#526,961)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Scott sentences for certain groups.Julia F. Knight & Vikram Saraph - 2018 - Archive for Mathematical Logic 57 (3-4):453-472.
Scott sentences for equivalence structures.Sara B. Quinn - 2020 - Archive for Mathematical Logic 59 (3-4):453-460.

Add more citations

References found in this work

Computable structures and the hyperarithmetical hierarchy.C. J. Ash - 2000 - New York: Elsevier. Edited by J. Knight.

Add more references