Arithmetical set

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Arithmetical set" – news · newspapers · books · scholar · JSTOR (August 2011) (Learn how and when to remove this message)

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 ${\displaystyle f:A\subseteq \mathbb {N} ^{k}\to \mathbb {N} }$ is called arithmetically definable if the graph of ${\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.