Go home now Header Background Image
Search
Submission Procedure
share: |
 
Follow us
 
 
 
 
Volume 22 / Issue 7

available in:   PDF (140 kB) PS (312 kB)
 
get:  
Similar Docs BibTeX   Write a comment
  
get:  
Links into Future
 
DOI:   10.3217/jucs-022-07-0943

 

The Enumeration Spectrum Hierarchy of α-families and Lowα Degrees

Marat Faizrahmanov (Kazan (Volga Region) Federal University, Russia)

Iskander Kalimullin (Kazan (Volga Region) Federal University, Russia)

Abstract: In this paper we introduce a hierarchy of families which can be derived from the integers using countable collections. This hierarchy coincides with the von Neumann hierarchy of hereditary countable sets in the ZFC-theory with urelements from ℕ. The families from the hierarchy can be coded into countable algebraic structures preserving their algorithmic properties. We prove that there is no maximal level of the hierarchy and that the collection of non-lowα degrees for every computable ordinal ff is the enumeration spectrum of a family from the hierarchy. In particular, we show that the collection of non-lowα degrees for every computable limit ordinal α is a degree spectrum of some algebraic structure.

Keywords: class of families, countable family, degree spectra of structure, enumeration of family, lowα degree

Categories: F.1.1, F.1.2, F.4.1