Difference between revisions of "Enumeration operator"
From Encyclopedia of Mathematics
(Importing text file) |
Ulf Rehmann (talk | contribs) m (tex encoded by computer) |
||
| Line 1: | Line 1: | ||
| − | + | <!-- | |
| + | e0358101.png | ||
| + | $#A+1 = 49 n = 0 | ||
| + | $#C+1 = 49 : ~/encyclopedia/old_files/data/E035/E.0305810 Enumeration operator | ||
| + | Automatically converted into TeX, above some diagnostics. | ||
| + | Please remove this comment and the {{TEX|auto}} line below, | ||
| + | if TeX found to be correct. | ||
| + | --> | ||
| − | + | {{TEX|auto}} | |
| + | {{TEX|done}} | ||
| − | + | A mapping of the set of all sets of natural numbers into itself (i.e. a mapping of $ 2 ^ {\mathbf N} $ | |
| + | into $ 2 ^ {\mathbf N} $, | ||
| + | where $ \mathbf N $ | ||
| + | is the set of natural numbers), defined as follows. Let $ W _ {z} $ | ||
| + | be a recursively-enumerable set having Gödel number $ z $, | ||
| + | let $ D _ {u} $ | ||
| + | be a finite set of natural numbers with canonical index $ u $( | ||
| + | i.e. $ D _ {u} = \{ x _ {1} \dots x _ {n} \} $, | ||
| + | where $ x _ {1} < \dots < x _ {n} $ | ||
| + | and $ 2 ^ {x _ {1} } + \dots + 2 ^ {x _ {n} } = u $) | ||
| + | and let $ \langle x, u \rangle $ | ||
| + | be the number of the ordered pair consisting of the numbers $ x $ | ||
| + | and $ u $ | ||
| + | for a certain specified one-to-one recursive encoding of the pairs. Each recursively-enumerable set $ W _ {z} $ | ||
| + | yields a procedure that transforms any given set of natural numbers $ B $ | ||
| + | into the set $ A $ | ||
| + | of natural numbers $ x $ | ||
| + | with the property that $ \langle x , u \rangle \in W _ {z} $ | ||
| + | for some $ u $ | ||
| + | with $ D _ {u} \subset B $, | ||
| + | i.e. $ \langle x, u\rangle $ | ||
| + | belongs to $ W _ {z} $ | ||
| + | and if the finite set $ D _ {u} $ | ||
| + | is contained in $ B $, | ||
| + | then $ x $ | ||
| + | is related to $ A $. | ||
| + | In other words, | ||
| − | + | $$ | |
| + | A = \{ {x } : {( \exists u)(\langle x, u\rangle \in W _ {z} \wedge D _ {u} \subseteq B) } \} | ||
| + | . | ||
| + | $$ | ||
| + | |||
| + | This procedure enables one to obtain effectively from any enumeration on $ B $ | ||
| + | an enumeration on $ A $. | ||
| + | It is called an enumeration operator and is denoted by $ \Phi _ {z} $. | ||
| + | If $ \Psi ( B) = A $ | ||
| + | for some enumeration operator $ \Psi $, | ||
| + | one says that $ A $ | ||
| + | is reducible in enumerability to $ B $( | ||
| + | $ A \leq _ {e} B $). | ||
| + | |||
| + | If $ \Phi $ | ||
| + | and $ \Psi $ | ||
| + | are enumeration operators, their composite $ \Phi \Psi $ | ||
| + | is also an enumeration operator. If $ \Psi $ | ||
| + | is an enumeration operator and $ B _ {1} \subseteq B $, | ||
| + | then $ \Psi ( B _ {1} ) \subseteq \Psi ( B) $. | ||
| + | If $ x \in \Psi ( B _ {1} ) $, | ||
| + | then $ x \in \Psi ( D) $ | ||
| + | for some finite set $ D \subseteq B _ {1} $. | ||
| + | Each enumeration operator $ \Psi $ | ||
| + | has a least fixed point, i.e. there exists a recursively-enumerable set $ A $ | ||
| + | such that $ \Psi ( A) = A $, | ||
| + | and if $ \Psi ( B) = B $, | ||
| + | then $ A \subseteq B $. | ||
====References==== | ====References==== | ||
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967)</TD></TR></table> | <table><TR><TD valign="top">[1]</TD> <TD valign="top"> H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967)</TD></TR></table> | ||
Latest revision as of 19:37, 5 June 2020
A mapping of the set of all sets of natural numbers into itself (i.e. a mapping of $ 2 ^ {\mathbf N} $
into $ 2 ^ {\mathbf N} $,
where $ \mathbf N $
is the set of natural numbers), defined as follows. Let $ W _ {z} $
be a recursively-enumerable set having Gödel number $ z $,
let $ D _ {u} $
be a finite set of natural numbers with canonical index $ u $(
i.e. $ D _ {u} = \{ x _ {1} \dots x _ {n} \} $,
where $ x _ {1} < \dots < x _ {n} $
and $ 2 ^ {x _ {1} } + \dots + 2 ^ {x _ {n} } = u $)
and let $ \langle x, u \rangle $
be the number of the ordered pair consisting of the numbers $ x $
and $ u $
for a certain specified one-to-one recursive encoding of the pairs. Each recursively-enumerable set $ W _ {z} $
yields a procedure that transforms any given set of natural numbers $ B $
into the set $ A $
of natural numbers $ x $
with the property that $ \langle x , u \rangle \in W _ {z} $
for some $ u $
with $ D _ {u} \subset B $,
i.e. $ \langle x, u\rangle $
belongs to $ W _ {z} $
and if the finite set $ D _ {u} $
is contained in $ B $,
then $ x $
is related to $ A $.
In other words,
$$ A = \{ {x } : {( \exists u)(\langle x, u\rangle \in W _ {z} \wedge D _ {u} \subseteq B) } \} . $$
This procedure enables one to obtain effectively from any enumeration on $ B $ an enumeration on $ A $. It is called an enumeration operator and is denoted by $ \Phi _ {z} $. If $ \Psi ( B) = A $ for some enumeration operator $ \Psi $, one says that $ A $ is reducible in enumerability to $ B $( $ A \leq _ {e} B $).
If $ \Phi $ and $ \Psi $ are enumeration operators, their composite $ \Phi \Psi $ is also an enumeration operator. If $ \Psi $ is an enumeration operator and $ B _ {1} \subseteq B $, then $ \Psi ( B _ {1} ) \subseteq \Psi ( B) $. If $ x \in \Psi ( B _ {1} ) $, then $ x \in \Psi ( D) $ for some finite set $ D \subseteq B _ {1} $. Each enumeration operator $ \Psi $ has a least fixed point, i.e. there exists a recursively-enumerable set $ A $ such that $ \Psi ( A) = A $, and if $ \Psi ( B) = B $, then $ A \subseteq B $.
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=14496
Enumeration operator. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Enumeration_operator&oldid=14496
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article