- Arithmetical set
In
mathematical logic , an arithmetical set (or arithmetic set) is a set of natural numbers that can be defined by a formula of first-orderPeano arithmetic . The arithmetical sets are classified by thearithmetical hierarchy .A function f:subseteq mathbb{N}^k o mathbb{N} is called arithmetically definable if the graph of f is an arithmetical set.
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 relationR(n_1,ldots,n_k) is arithmetical if there is a formula psi(n_1,ldots,n_k) such that R(n_1,ldots,n_k) Leftrightarrow psi(n_1,ldots,n_k) holds for all "k"-tuples n_1,ldots,n_k) 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.
Examples
* Every
computable function is arithmetically definable.
* The set of allprime number s is arithmetical.
* Everyrecursively enumerable set is arithmetical.
* The set encoding theHalting 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.Properties
* The complement of an arithmetical set is an arithmetical set.
* TheTuring 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.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 heta(Z) in the language of Peano arithmetic with no free number variables and a new set parameter "Z" and set membership relation in such that "Y" is the unique set such that heta(Y) holds.
Every arithmetical set is implicitly arithmetical; if "X" is arithmetically defined by φ("n") then it is implicitly defined by the formula:forall n [n in Z Leftrightarrow phi(n)] .Not every implicitly arithmetical set is arithmetical, however. In particular, the truth set of first order arithmetic is implicitly arithmetical but not arithmetical.
See also
*
Arithmetical hierarchy
*Computable set
*Computable number References
Rogers, H. (1967). "Theory of recursive functions and effective computability." McGraw-Hill.
Wikimedia Foundation. 2010.