Premium
The Index Set of Injectively Enumerable Classes of Recursively Enumerable Sets in ∑ 5 ‐Complete
Author(s) -
Wehner Stephan
Publication year - 1994
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.19940400112
Subject(s) - recursively enumerable language , recursively enumerable set , enumeration , mathematics , maximal set , set (abstract data type) , index (typography) , hierarchy , discrete mathematics , arithmetic function , combinatorics , computer science , world wide web , economics , market economy , programming language
I introduce an effective enumeration of all effective enumerations of classes of r. e. sets and define with this the index set IE of injectively enumerable classes. It is easy to see that this set is ∑ 5 in the Arithmetical Hierarchy and I describe a proof for the ∑ 5 ‐hardness of IE . Mathematics Subject Classification: 03D25, 03D45.