Arithmetic set

Arithmetic set - a set of natural numbers $S$ ${\ displaystyle S}$ $S$ , which can be defined by a formula in the first-order arithmetic language, that is, if such a formula exists $\phi (x)$ ${\ displaystyle \ phi (x)}$ $\ phi (x)$ with one free variable $x,$ ${\ displaystyle x,}$ $x$ what $\forall x(x\in S\leftrightarrow \phi (x))$ ${\ displaystyle \ forall x (x \ in S \ leftrightarrow \ phi (x))}$ $\ forall x (x \ in S \ leftrightarrow \ phi (x))$ . You can also talk about arithmetic sets of tuples of natural numbers, finite sequences of natural numbers, formulas (for any fixed Gödel numbering ) and, in general, about arithmetic sets of any constructive objects encoded by natural numbers.

Content

1 Related Definitions
2 Properties
3 Examples
4 See also
5 Literature

Related Definitions

Function $\mathbb {N} \to \mathbb {N}$ ${\ displaystyle \ mathbb {N} \ to \ mathbb {N}}$ is called arithmetic if its graph is an arithmetic set. Similarly, we can talk about the arithmetic functions $\mathbb {N} ^{n}\to \mathbb {N}$ {\ displaystyle \ mathbb {N} ^ {n} \ to \ mathbb {N}} and, in general, functions defined on the sets of any constructive objects.

A real number is called arithmetic if the set of rational numbers smaller than it is arithmetic (or, equivalently, if the set of rational numbers larger than it is arithmetic). A complex number is called arithmetic if both its real and imaginary parts are arithmetic.

Properties

A subset of an arithmetic set is not necessarily arithmetic.
The collection of all arithmetic sets of natural numbers is a countable set , and the collection of all non-arithmetic sets is uncountable .
The set of complex arithmetic numbers forms an algebraically closed field .
Any computable number is arithmetic.
The set of arithmetic numbers (as well as its complement) is dense in $\mathbb {R}$ ${\ displaystyle \ mathbb {R}}$ and in $\mathbb {C} .$ ${\ displaystyle \ mathbb {C}.}$
The order on the set of real arithmetic numbers is isomorphic to the order on the set of rational numbers.

Examples

An empty set is arithmetic.
Any enumerable set (in particular, any decidable set and any finite set ) are arithmetic.
The complement and projection of any arithmetic set are arithmetic.
The union and intersection of a finite number of arithmetic sets are also arithmetic.
The set of numbers, starting with which the sequence defined in the Collatz hypothesis , ends with a unit - arithmetically, and if this hypothesis is true - even decidable in a trivial way (the whole set of natural numbers).
The set of rational numbers greater than the Haitin constant Ω is arithmetic, but not enumerable.
Many Turing machine numbers that do not stop at an empty entrance are arithmetic (although not enumerable ).
But the set of numbers of Turing machines that implement the operation of comparing natural numbers, which completely ordering the set in some way $\mathbb {N} ,$ ${\ displaystyle \ mathbb {N},}$ not arithmetic.
Many statements that are unprovable in ZFC are arithmetic, but, given ZFC's consistency, are non-enumerable.
But the set of true statements in first-order arithmetic is not arithmetic (which is the statement of Tarski's theorem on the inexpressible truth in arithmetic), although the set of provable statements is arithmetic and even enumerable.

Literature

N.K. Vereshchagin, A. Shen. Part 2. Languages and calculus // Lectures on mathematical logic and theory of algorithms. - 2nd ed .. - M .: ICMMO , 2002.