Creative and productive sets

Creative and productive sets

In computability theory, productive sets and creative sets are types of sets of natural numbers that have important applications in mathematical logic. They are a standard topic in mathematical logic textbooks such as Soare (1987) and Rogers (1987).

Contents

Definition and example

For the remainder of this article, assume that φi is an acceptable numbering of the computable functions and Wi the corresponding numbering of the recursively enumerable sets.

A set A of natural numbers is called productive if there exists a partial computable function f so that for all i \in \mathbb{N}, if W_i \subseteq A then f(i) \in A \setminus W_i. The function f is called the productive function for A.

A set A of natural numbers is called creative if A is recursively enumerable and its complement \mathbb{N}\setminus A is productive. Not every productive set has a recursively enumerable complement, however, as illustrated below.

The archetypal creative set is K = \{ i \mid i \in W_i \}, the set representing the halting problem. Its complement \bar{K} = \{ i \mid i \not \in W_i \} is productive with productive function f(i) = i. To see this, assume W_i \subseteq \bar{K}. If i were in Wi then  i \in K and thus  i \not \in \bar{K}. This would mean W_i \not \subseteq \bar{K}, so we can conclude i \not \in W_i, which means i \in \bar{K}.

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 K and all productive sets are like \bar{K} (see Soare (1987) and Rogers (1987)).

Theorem. Let P be a set of natural numbers. The following are equivalent:

Theorem. Let C be a set of natural numbers. The following are equivalent:

Applications in mathematical logic

The set of all provable sentences in an effective axiomatic system is always a recursively enumerable set. If the system is suitably complex, like first-order arithmetic, then the set T of Gödel numbers of true sentences in the system will be a productive set, which means that whenever W is a recursively enumerable set of true sentences, there is at least one true sentence that is not in W. This can be used to give a rigorous proof of Gödel's first incompleteness theorem, because no recursively enumerable set is productive. The complement of the set T will not be recursively enumerable, and thus T is an example of a productive set whose complement is not creative.

References

  • Davis, M., 1982. Computability and Unsolvability. New York: Dover.
  • Kleene, S. C.,2002. Mathematical Logic. New York: Dover.
  • Myhill, J., 1955. "Creative sets," Z. Math. Logik Grundlag. Math., v. 1, pp. 97–108.
  • Rogers, H., 1987. Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press.
  • Soare, R., 1987. Recursively Enumerable Sets and Degrees. Berlin: Springer.

Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Art, Antiques, and Collections — ▪ 2003 Introduction       In 2002 major exhibitions such as Documenta 11 reflected the diverse nature of contemporary art: artists from a variety of cultures received widespread recognition for work ranging from installation to video to painting …   Universalium

  • Letters Written in Sweden, Norway, and Denmark — Letters Written During a Short Residence in Sweden, Norway, and Denmark (1796) is a deeply personal travel narrative by the eighteenth century British feminist Mary Wollstonecraft. The twenty five letters cover a wide range of topics, from… …   Wikipedia

  • Anthropology and Archaeology — ▪ 2009 Introduction Anthropology       Among the key developments in 2008 in the field of physical anthropology was the discovery by a large interdisciplinary team of Spanish and American scientists in northern Spain of a partial mandible (lower… …   Universalium

  • Fichte and Schilling: the Jena period — Daniel Breazeale FROM KANT TO FICHTE An observer of the German philosophical landscape of the 1790s would have surveyed a complex and confusing scene, in which individuals tended to align themselves with particular factions or “schools,”… …   History of philosophy

  • Deconstruction and Derrida — Simon Critchley and Timothy Mooney DERRIDIAN DECONSTRUCTION1 In the last twenty five years or so, particularly in the English speaking world, no philosopher has attracted more notoriety, controversy and misunderstanding than Jacques Derrida.… …   History of philosophy

  • Ockham’s world and future — Arthur Gibson PHILOSOPHICAL BIOGRAPHY Ockham was born in about 1285, certainly before 1290, probably in the village of Ockham, Surrey, near London. If his epitaph is accurate, he died on 10 April 1347. Yet Conrad of Megenberg, when writing to… …   History of philosophy

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • Glossary of language teaching terms and ideas — Like every other course of study, language teaching requires specialized vocabulary and word use. This list is a glossary for English language learning and teaching using the increasingly popular communicative approach. Accuracy Burnout •… …   Wikipedia

  • United Kingdom of Great Britain and Northern Ireland — Royaume Uni  Ne doit pas être confondu avec l Angleterre ou la Grande Bretagne. 52° N 1° W …   Wikipédia en Français

  • ART — This article is arranged according to the following outline: Antiquity to 1800 INTRODUCTION: JEWISH ATTITUDE TO ART biblical period the sanctuary and first temple period second temple period after the fall of jerusalem relation to early christian …   Encyclopedia of Judaism

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”