Strong reducibility of partial numberings

A strong reducibility relation between partial numberings is introduced which is such that the reduction function transfers exactly the numbers which are indices under the numbering to be reduced into corresponding indices of the other numbering. The degrees of partial numberings of a given set with...

Full description

Saved in:
Bibliographic Details
Published in:Archive for mathematical logic 2005-02, Vol.44 (2), p.209-217
Main Author: Spreen, Dieter
Format: Article
Language:English
Subjects:
Logic
Mathematics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A strong reducibility relation between partial numberings is introduced which is such that the reduction function transfers exactly the numbers which are indices under the numbering to be reduced into corresponding indices of the other numbering. The degrees of partial numberings of a given set with respect to this relation form an upper semilattice. In addition, Ershov's completion construction for total numberings is extended to the partial case: every partially numbered set can be embedded in a set which results from the given set by adding one point and which is enumerated by a total and complete numbering. As is shown, the degrees of complete numberings of the extended set also form an upper semilattice. Moreover, both semilattices are isomorphic. This is not so in the case of the usual, weaker reducibility relation for partial numberings which allows the reduction function to transfer arbitrary numbers into indices. [PUBLICATION ABSTRACT]
ISSN:0933-5846
1432-0665
DOI:10.1007/s00153-004-0262-y