Premium
Jumps of nontrivial splittings of recursively enumerable sets
Author(s) -
Ingrassia Michael A.,
Lempp Steffen
Publication year - 1990
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19900360403
Subject(s) - recursively enumerable language , citation , state (computer science) , mathematics , computer science , algorithm , discrete mathematics , library science , combinatorics
A pair of recursively enumerable (r.e.) sets A. and A l is said to split an r.e. set A if A = A. u A, (i.e., A = A. u Al and 0 = A. n Al). FRIEDBERG [5] was the first to prove that any nonrecursive r.e. set can be split into two nonrecursive r.e. sets. SACKS [15] improved this result by showing that the two halves can be made of low incomparable degrees. Other wellknown splitting results were obtained by OWINGS [13], R. W. ROBINSON [14], MORLEY and SOARE [12], and LACHLAN [8].