- 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-orderPeano arithmetic . The arithmetical sets are classified by thearithmetical hierarchy .A function $f:subseteq\; mathbb\{N\}^k\; o\; mathbb\{N\}$ is called

**arithmetically definable**if the graph of $f$ is an arithmetical set.**Formal definition**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*** Every

computable function is arithmetically definable.

* The set of allprime number s is arithmetical.

* Everyrecursively enumerable set is arithmetical.

* The set encoding theHalting problem is arithmetical.

*Chaitin's constant Ω is encoded by an arithmetical set.

*Tarski's indefinability theorem shows that the set of Gödel numbers of true formulas of first order arithmetic is not arithmetically definable.**Properties*** The complement of an arithmetical set is an arithmetical set.

* TheTuring 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.**Implicitly arithmetical sets**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 $heta(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 such that $heta(Y)$ 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***

Arithmetical hierarchy

*Computable set

*Computable number **References**Rogers, H. (1967). "Theory of recursive functions and effective computability." McGraw-Hill.

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**arithmetical set**— noun A set of natural numbers that can be defined by a formula of first order Peano arithmetic. Syn: arithmetic set … Wiktionary**Arithmetical hierarchy**— In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene hierarchy classifies certain sets based on the complexity of formulas that define them. Any set that receives a classification is called arithmetical. The… … Wikipedia**Arithmetical complement of a number**— Complement Com ple*ment, n. [L. complementun: cf. F. compl[ e]ment. See {Complete}, v. t., and cf. {Compliment}.] 1. That which fills up or completes; the quantity or number required to fill a thing or make it complete. [1913 Webster] 2. That… … The Collaborative International Dictionary of English**Arithmetical compliment of a logarithm**— Complement Com ple*ment, n. [L. complementun: cf. F. compl[ e]ment. See {Complete}, v. t., and cf. {Compliment}.] 1. That which fills up or completes; the quantity or number required to fill a thing or make it complete. [1913 Webster] 2. That… … The Collaborative International Dictionary of English**Set-theoretic definition of natural numbers**— Several ways have been proposed to define the natural numbers using set theory.The contemporary standardIn standard (ZF) set theory the natural numbersare defined recursively by 0 = {} (the empty set) and n +1 = n ∪ { n }. Then n = {0,1,..., n… … Wikipedia**Definable set**— In mathematical logic, a definable set is an n ary relation on the domain of a structure whose elements are precisely those elements satisfying some formula in the language of that structure. A set can be defined with or without parameters, which … Wikipedia**Recursively enumerable set**— In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing recognizable if: There is an algorithm such that the set of… … Wikipedia**Zermelo–Fraenkel set theory**— Zermelo–Fraenkel set theory, with the axiom of choice, commonly abbreviated ZFC, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics.ZFC consists of a single primitive ontological notion, that of… … Wikipedia**Recursive set**— In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set. A more… … Wikipedia**Kripke–Platek set theory**— The Kripke–Platek axioms of set theory (KP) (IPAEng|ˈkrɪpki ˈplɑːtɛk) are a system of axioms of axiomatic set theory, developed by Saul Kripke and Richard Platek. The axiom system is written in first order logic; it has an infinite number of… … Wikipedia