2003 | OriginalPaper | Chapter
Isomorphism Types and Theories of Rogers Semilattices of Arithmetical Numberings
Authors : Serikzhan Badaev, Sergey Goncharov, Andrea Sorbi
Published in: Computability and Models
Publisher: Springer US
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We investigate differences in isomorphism types and elementary theories of Rogers semilattices of arithmetical numberings, depending on different levels of the arithmetical hierarchy. It is proved that new types of isomorphism appear as the arithmetical level increases. It is also proved the incompleteness of the theory of the class of all Rogers semilattices of any fixed level. Finally, no Rogers semilattice of any infinite family at arithmetical level n ≥ 2 is weakly distributive, whereas Rogers semilattices of finite families are always distributive.