In
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...
, productive sets and creative sets are types of sets of
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s that have important applications in
mathematical logic
Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
. They are a standard topic in mathematical logic textbooks such as and .
Definition and example
For the remainder of this article, assume that
is an
admissible numbering In computability theory, admissible numberings are enumerations (Numbering (computability theory), numberings) of the set of partial computable functions that can be converted ''to and from'' the standard numbering. These numberings are also called ...
of the
computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
s and ''W''
''i'' the corresponding numbering of the
recursively enumerable
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that the ...
sets.
A set ''A'' of natural numbers is called productive if there exists a
total recursive (computable) function
so that for all
, if
then
The function
is called the productive function for
A set ''A'' of natural numbers is called creative if ''A'' is recursively enumerable and its complement
is productive. Not every productive set has a recursively enumerable complement, however, as illustrated below.
The archetypal creative set is
, the set representing the
halting problem
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a g ...
. Its complement
is productive with productive function ''f''(''i'') = ''i'' (the identity function).
To see this, we apply the definition of a productive function and show separately that
and
:
*
: suppose
, then
, now given that
we have
, this leads to a contradiction. So
.
*
: in fact if
, then it would be true that
, but we have demonstrated the contrary in the previous point. So
.
Properties
No productive set ''A'' can be recursively enumerable, because whenever ''A'' contains every number in an r.e. set ''W''
''i'' 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
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
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
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
''f'' on the natural numbers such that ''f''(''C'') = ''K''.
Applications in mathematical logic
The set of all provable sentences in an effective
axiomatic system
In mathematics and logic, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. A theory is a consistent, relatively-self-contained body of knowledge which usually contai ...
is always a
recursively enumerable set
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that the ...
. If the system is suitably complex, like
first-order arithmetic
In first-order logic, a first-order theory is given by a set of axioms in some
language. This entry lists some of the more common examples used in model theory and some of their properties.
Preliminaries
For every natural mathematical structure ...
, 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.
History
The seminal paper of defined the concept he called a Creative set. Reiterating, the set
referenced above and defined as the domain of the function
that takes the diagonal of all enumerated 1-place computable partial functions and adds 1 to them is an example of a creative set.
[, pp. 79, 80, 120.] Post gave a version of Gödel's Incompleteness Theorem using his creative sets, where originally Gödel had in some sense constructed a sentence that could be freely translated as saying "I am unprovable in this axiomatic theory." However, Gödel's proof did not work from the concept of true sentences, and rather used the concept of a consistent theory, which led to the
second incompleteness theorem
The second (symbol: s) is the unit of time in the International System of Units (SI), historically defined as of a day – this factor derived from the division of the day first into 24 hours, then to 60 minutes and finally to 60 seconds e ...
. After Post completed his version of incompleteness he then added the following:
"The conclusion is unescapable that even for such a fixed, well defined body of mathematical propositions, mathematical thinking is, and must remain, essentially creative."
The usual creative set
defined using the diagonal function
has its own historical development.
Alan Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical com ...
in a 1936 article on the
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
showed the existence of a universal computer that computes the
function. The function
is defined such that
(''the result of applying the instructions coded by''
''to the input''
), and is universal in the sense that any calculable partial function
is given by
for all
where
codes the instructions for
. Using the above notation
, and the diagonal function arises quite naturally as
. Ultimately, these ideas are connected to
Church's thesis
Church's is a high-end footwear manufacturer that was founded in 1873, by Thomas Church, in Northampton, England. In 1999 the company came under the control of Italian luxury fashion house Prada in a US$170 million deal.
History
Between the ...
that says the mathematical notion of computable partial functions is the ''correct'' formalization of an effectively calculable partial function, which can neither be proved or disproved. Church used
lambda calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation ...
, Turing an idealized computer, and later Emil Post in his approach, all of which are equivalent.
formulated an analogous concept,
polynomial creativity In computational complexity theory, polynomial creativity is a theory analogous to the theory of creative sets in recursion theory and mathematical logic. The are a family of formal languages in the complexity class NP whose complements certifiabl ...
, in
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
, and used it to provide potential counterexamples to the
Berman–Hartmanis conjecture
In structural complexity theory, the Berman–Hartmanis conjecture is an unsolved conjecture named after Leonard C. Berman and Juris Hartmanis that states that all NP-complete languages look alike, in the sense that they can be related to each othe ...
on isomorphism of
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
sets.
Notes
References
*. Reprinted in 1982 by Dover Publications.
*.
*
*. Reprint of the 1967 original, Wiley, .
*.
*
*.
*{{citation
, last = Soare , first = Robert I. , author-link = Robert I. Soare
, isbn = 3-540-15299-7
, location = Berlin
, mr = 882921
, publisher = Springer-Verlag
, series = Perspectives in Mathematical Logic
, title = Recursively enumerable sets and degrees: A study of computable functions and computably generated sets
, year = 1987.
Computability theory