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:
“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)
“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)