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

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.

Formal definition

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.