Arithmetical set


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.

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 relationR(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 all prime numbers is arithmetical.
* Every recursively enumerable set is arithmetical.
* The set encoding the Halting 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.
* 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.

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