In
mathematical logic
Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
, an arithmetical set (or arithmetic set) is a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of
natural number
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s that can be defined by a
formula
In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwe ...
of
first-order Peano arithmetic
In mathematical logic, the Peano axioms (, ), also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th-century Italian mathematician Giuseppe Peano. These axioms have been used nea ...
. The arithmetical sets are classified by the
arithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain sets based on the complexity of formulas that define th ...
.
The definition can be extended to an arbitrary
countable set
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbe ...
''A'' (e.g. the set of ''n''-
tuple
In mathematics, a tuple is a finite sequence or ''ordered list'' of numbers or, more generally, mathematical objects, which are called the ''elements'' of the tuple. An -tuple is a tuple of elements, where is a non-negative integer. There is o ...
s of
integers
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
, the set of
rational numbers
In mathematics, a rational number is a number that can be expressed as the quotient or fraction (mathematics), fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (for examp ...
, the set of formulas in some
formal language
In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet".
The alphabet of a formal language consists of symbols that concatenate into strings (also c ...
, etc.) by using
Gödel numbers to represent elements of the set and declaring a
subset
In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...
of ''A'' to be arithmetical if the set of corresponding Gödel numbers is arithmetical.
A
function is called arithmetically definable if the
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discret ...
of
is an arithmetical set.
A
real number
In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
is called arithmetical if the set of all smaller rational numbers is arithmetical. A
complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the for ...
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
Relation or relations may refer to:
General uses
* International relations, the study of interconnection of politics, economics, and law on a global level
* Interpersonal relationship, association or acquaintance between two or more people
* ...
is arithmetical if there is a formula
such that
holds for all ''k''-tuples
of natural numbers.
A
function 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.
Examples
* The set of all
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
s is arithmetical.
* Every
recursively enumerable set
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that the ...
is arithmetical.
* Every
computable function
Computable functions are the basic objects of study in computability theory. Informally, a function is ''computable'' if there is an algorithm that computes the value of the function for every value of its argument. Because of the lack of a precis ...
is arithmetically definable.
* The set encoding the
halting problem
In computability theory (computer science), computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run for ...
is arithmetical.
*
Chaitin's constant Ω is an arithmetical real number.
*
Tarski's indefinability theorem
Tarski's undefinability theorem, stated and proved by Alfred Tarski in 1933, is an important limitative result in mathematical logic, the foundations of mathematics, and in formal semantics. Informally, the theorem states that "arithmetical truth ...
shows that the (Gödel numbers of the) set of true formulas of first-order arithmetic is not arithmetically definable.
Properties
* The
complement of an arithmetical set is an arithmetical set.
* The
Turing jump
In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine ...
of an arithmetical set is an arithmetical set.
* The collection of arithmetical sets is countable, but the
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...
of arithmetical sets is not arithmetically definable. Thus, there is no arithmetical formula φ(''n'',''m'') that is true if and only if ''m'' is a member of the ''n''th arithmetical predicate.
:In fact, such a formula would describe a decision problem for all finite
Turing jump
In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine ...
s, and hence belongs to 0
(ω), which cannot be formalized in
first-order arithmetic, as
it does not belong to the first-order arithmetical hierarchy.
* The set of real arithmetical numbers is
countable
In mathematics, a Set (mathematics), set is countable if either it is finite set, finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function fro ...
,
dense
Density (volumetric mass density or specific mass) is the ratio of a substance's mass to its volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' (or ''d'') can also be use ...
and
order-isomorphic to the set of rational numbers.
Implicitly arithmetical sets
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
in the language of Peano arithmetic with no free number variables and a new set parameter ''Z'' and set membership relation
such that ''Y'' is the unique set ''Z'' such that
holds.
Every arithmetical set is implicitly arithmetical; if ''X'' is arithmetically defined by φ(''n'') then it is implicitly defined by the formula
: