be used to define all Diophantine sets.) There is a polynomial from the integers to the integers such that the set S contains exactly the non-negative numbers in its range. The equivalence of semidecidability and enumerability can be obtained by the technique of dovetailing. The Diophantine characterizations of a computably enumerable set, while not as straightforward or intuitive as the first definitions, were found by Yuri Matiyasevich as part of the negative solution to Hilbert's Tenth Problem. Diophantine sets predate recursion theory and are therefore historically the first way to describe these sets (although this equivalence was only remarked more than three decades after the introduction of computably enumerable sets). Examples Every computable set is computably enumerable, but it is not true that every computably enumerable set is computable. For computable sets, the algorithm must also say if an input is not in the set – this is not required of computably enumerable sets. A recursively enumerable language is a computably enumerable subset of a formal language. The set of all provable sentences in an effectively presented axiomatic system is a computably enumerable set. Matiyasevich's theorem states that every computably enumerable set is a Diophantine set (the converse is trivially true). The simple sets are computably enumerable but not computable. The creative sets are computably enumerable but not computable. Any productive set is not computably enumerable. Given a Gödel numbering of the computable functions, the set (where is the Cantor pairing function and indicates is defined) is computably enumerable (cf. picture for a fixed x). This set encodes the halting problem as it describes the input parameters for which each Turing machine halts. Given a Gödel numbering of the computable functions, the set is computably enumerable. This set encodes the problem of deciding a function value. Given a partial function f from the natural numbers into the natural numbers, f is a partial computable function if and only if the graph of f, that is, the set of all pairs such that f(x) is defined, is computably enumerable. Properties If A and B are computably enumerable sets then A ∩ B, A ∪ B and A × B (with the ordered pair of natural numbers mapped to a single natural number with the Cantor pairing function) are computably enumerable sets. The preimage of a computably enumerable set under a partial computable function is a computably enumerable set. A set is