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-order Peano arithmetic. The arithmetical sets are classified by the arithmetical hierarchy. The definition can be extended to an arbitrary countable set A (e.g. the set of n-tuples of integers, the set of rational numbers, the set of formulas in some formal language, etc.) by using Gödel numbers to represent elements of the set and declaring a subset of A to be arithmetical if the set of corresponding Gödel numbers is arithmetical. A function is called arithmetically definable if the graph of is an arithmetical set. A real number is called arithmetical if the set of all smaller rational numbers is arithmetical. A complex number is called arithmetical if its real and imaginary parts are both arithmetical. A set X of natural numbers is arithmetical or arithmetically definable if there is a first-order 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 function is called arithmetical if its graph is an arithmetical (k+1)-ary relation. A set A is said to be arithmetical in a set B if A is definable by an arithmetical formula that has B as a set parameter. The set of all prime numbers is arithmetical. Every recursively enumerable set is arithmetical. Every computable function is arithmetically definable. The set encoding the halting problem is arithmetical. Chaitin's constant Ω is an arithmetical real number. Tarski's indefinability theorem shows that the (Gödel numbers of the) set of true formulas of first-order arithmetic is not arithmetically definable. 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 the sequence of arithmetical sets is not arithmetically definable.