کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426752 | 686259 | 2014 | 13 صفحه PDF | دانلود رایگان |
One says that a property P of sets of natural numbers can be made into itself iff there is a numbering α0,α1,…α0,α1,… of all left-r.e. sets such that the index set {e:αe satisfies P}{e:αe satisfies P} has the property P as well. For example, the property of being Martin-Löf random can be made into itself. Herein we characterize those singleton properties which can be made into themselves. A second direction of the present work is the investigation of the structure of left-r.e. sets under inclusion modulo a finite set. In contrast to the corresponding structure for r.e. sets, which has only maximal but no minimal members, both minimal and maximal left-r.e. sets exist. Moreover, our construction of minimal and maximal left-r.e. sets greatly differs from Friedberg's classical construction of maximal r.e. sets. Finally, we investigate whether the properties of minimal and maximal left-r.e. sets can be made into themselves.
Journal: Information and Computation - Volume 237, October 2014, Pages 174–186