Properties
No productive set A can be recursively enumerable, because whenever A contains every number in an r.e. set Wi it contains other numbers, and moreover there is an effective procedure to produce an example of such a number from the index i. Similarly, no creative set can be decidable, because this would imply that its complement, a productive set, is recursively enumerable.
Any productive set has a productive function that is injective and total.
The following theorems, due to Myhill (1955), show that in a sense all creative sets are like and all productive sets are like .
Theorem. Let P be a set of natural numbers. The following are equivalent:
- P is productive.
- is 1-reducible to P.
- is m-reducible to P.
Theorem. Let C be a set of natural numbers. The following are equivalent:
- C is creative.
- C is 1-complete
- C is recursively isomorphic to K, that is, there is a total computable bijection f on the natural numbers such that f(C) = K.
Read more about this topic: Creative And Productive Sets
Famous quotes containing the word properties:
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)
“A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
—Ralph Waldo Emerson (1803–1882)