Arithmetical set

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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:\subseteq \mathbb{N}^k \to \mathbb{N} is called arithmetically definable if the graph of 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[edit]

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 relation R(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[edit]

Properties[edit]

  • 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 there is no arithmetically definable sequence that enumerates all arithmetical sets.
  • The set of real arithmetical numbers is denumerable, dense and order-isomorphic to the set of rational numbers.

Implicitly arithmetical sets[edit]

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 \theta(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 Z such that \theta(Z) 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[edit]

Further reading[edit]

  • Rogers, H. (1967). Theory of recursive functions and effective computability. McGraw-Hill. [ISBN missing]