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 f : A ⊆ N k → N {\displaystyle f:A\subseteq \mathbb {N} ^{k}\to \mathbb {N} } is called arithmetically definable if the graph of f {\displaystyle f} 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 R ( n 1 , … , n k ) {\displaystyle R(n_{1},\ldots ,n_{k})} is arithmetical if there is a formula ψ ( n 1 , … , n k ) {\displaystyle \psi (n_{1},\ldots ,n_{k})} such that R ( n 1 , … , n k ) ⟺ ψ ( n 1 , … , n k ) {\displaystyle R(n_{1},\ldots ,n_{k})\iff \psi (n_{1},\ldots ,n_{k})} holds for all k-tuples ( n 1 , … , n k ) {\displaystyle (n_{1},\ldots ,n_{k})} of natural numbers.
A function f :⊆ N k → N {\displaystyle f:\subseteq \mathbb {N} ^{k}\to \mathbb {N} } 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.
Each arithmetical set has an arithmetical formula that says whether particular numbers are in the set. An alternative notion of definability allows for a formula that does not say whether particular numbers are in the set but says 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 ) {\displaystyle \theta (Z)} in the language of Peano arithmetic with no free number variables and a new set parameter Z and set membership relation ∈ {\displaystyle \in } such that Y is the unique set Z such that θ ( Z ) {\displaystyle \theta (Z)} 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.