Namespaces
Variants
Actions

Enumeration operator

From Encyclopedia of Mathematics
Revision as of 17:08, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

A mapping of the set of all sets of natural numbers into itself (i.e. a mapping of into , where is the set of natural numbers), defined as follows. Let be a recursively-enumerable set having Gödel number , let be a finite set of natural numbers with canonical index (i.e. , where and ) and let be the number of the ordered pair consisting of the numbers and for a certain specified one-to-one recursive encoding of the pairs. Each recursively-enumerable set yields a procedure that transforms any given set of natural numbers into the set of natural numbers with the property that for some with , i.e. belongs to and if the finite set is contained in , then is related to . In other words,

This procedure enables one to obtain effectively from any enumeration on an enumeration on . It is called an enumeration operator and is denoted by . If for some enumeration operator , one says that is reducible in enumerability to ().

If and are enumeration operators, their composite is also an enumeration operator. If is an enumeration operator and , then . If , then for some finite set . Each enumeration operator has a least fixed point, i.e. there exists a recursively-enumerable set such that , and if , then .

References

[1] H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967)
How to Cite This Entry:
Enumeration operator. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Enumeration_operator&oldid=46831
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article