Arithmetical set
From Wikipedia, the free encyclopedia
In mathematical logic, an arithmetical set (or arithmetic set) is a set of natural numbers that can be defined by a formula of first-order Peano arithmetic. The arithmetical sets are classified by the arithmetical hierarchy.
A function is called arithmetically definable if the graph of f is an arithmetical set.
Contents |
[edit] Formal definition
A set X of natural numbers is arithmetical or arithmetically definable if there is a formula φ(n) in the language of Peano arithmetic such that each number n is in X if and only if φ(n) holds in the standard model of arithmetic. Similarly, a k-ary relation is arithmetical if there is a formula such that holds for all k-tuples of natural numbers.
A finitary function on the natural numbers is called arithmetical if its graph is an arithmetical binary relation.
A set A is said to be arithmetical in a set B if A is definable by an arithmetical formula which has B as a set parameter.
[edit] Examples
- Every computable function is arithmetically definable.
- The set of all prime numbers is arithmetical.
- Every recursively enumerable set is arithmetical.
- The set encoding the Halting problem is arithmetical.
- Chaitin's constant Ω is encoded by an arithmetical set.
- Tarski's indefinability theorem shows that the set of Gödel numbers of true formulas of first order arithmetic is not arithmetically definable.
[edit] Properties
- The complement of an arithmetical set is an arithmetical set.
- The Turing jump of an arithmetical set is an arithmetical set.
- The collection of arithmetical sets is countable, but there is no arithmetically definable sequence that enumerates all arithmetical sets.
[edit] Implicitly arithmetical sets
Each arithmetical set has an arithmetical formula which tells whether particular numbers are in the set. An alternative notion of definability allows for a formula that does not tell whether particular numbers are in the set but tells whether the set itself satisfies some arithmetical property.
A set Y of natural numbers is implicitly arithmetical or implicitly arithmetically definable if it is definable with an arithmetical formula that is able to use Y as a parameter. That is, if there is a formula θ(Z) in the language of Peano arithmetic with no free number variables and a new set parameter Z and set membership relation such that Y is the unique set such that θ(Y) holds.
Every arithmetical set is implicitly arithmetical; if X is arithmetically defined by φ(n) then it is implicitly defined by the formula
- .
Not every implicitly arithmetical set is arithmetical, however. In particular, the truth set of first order arithmetic is implicitly arithmetical but not arithmetical.
[edit] See also
[edit] References
Rogers, H. (1967). Theory of recursive functions and effective computability. McGraw-Hill.