Finite computable dimension does not relativize

Abstract

 In many classes of structures, each computable structure has computable dimension 1 or $\omega$. Nevertheless, Goncharov showed that for each $n < \omega$, there exists a computable structure with computable dimension $n$. In this paper we show that, under one natural definition of relativized computable dimension, no computable structure has finite relativized computable dimension greater than 1.

Similar content being viewed by others

Structures Computable in Polynomial Time. I

Article 01 January 2017

Ash’s Theorem on Δ _α ⁰ -Categorical Structures and a Condition for Infinite Δ _α ⁰ -Dimension

Article 01 November 2015

Computable dimension for ordered fields

Article 10 March 2016

Author information

Authors and Affiliations

1. Department of Mathematics, University of Wisconsin at Madison, Madison, WI 53706, USA. e-mail: mccoy@math.wisc.edu, , , , , , US

   Charles F.D. McCoy

Authors

1. Charles F.D. McCoy
   View author publications

   You can also search for this author in PubMed Google Scholar

Additional information

Received: 27 July 1998/ Published online: 27 March 2002

Rights and permissions

Reprints and permissions

About this article

Cite this article

McCoy, C. Finite computable dimension does not relativize. Arch. Math. Logic 41, 309–320 (2002). https://doi.org/10.1007/s001530100113

Download citation

• Issue Date: April 2002

• DOI: https://doi.org/10.1007/s001530100113

Keywords

• Computable Structure
• Computable Dimension
• Natural Definition