Effective dimension

J. N. Crossley, Anil Nerode

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)


We prove there is a well-defined notion of effective dimension for a certain class of recursively presented models. This subsumes the Dekker and Hamilton theory of effective dimension for countable vector spaces over recursive fields. The principal interesting new case is effective dimension for countable fields. The case of fields is a natural follow-up to Fröhlich and Shepherdson on explicit fields. The model-theoretic context is a countable infinite model with a minimal formula satisfied by all nonalgebraic elements. Marsh showed that the algebraically closed subsets have a well-defined classical dimension. Suppose an infinite dimensional such model is given satisfying the obvious effectivity conditions satisfied by the standard examples of vector spaces and algebraically closed fields; namely, recursive presentability, having a recursive base, having an algorithm for determining independence of n-tuples, having an algorithm for determining the atoms expressing dependence. We then prove the effective uniqueness of dimension for algebraically closed sets with basis extendable to a recursively enumerable independent set.

Original languageEnglish
Pages (from-to)398-412
Number of pages15
JournalJournal of Algebra
Issue number2
Publication statusPublished - 1 Jan 1976
Externally publishedYes

Cite this