Definable real number
   HOME

TheInfoList



OR:

Informally, a definable real number is 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 distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
that can be uniquely specified by its description. The description may be expressed as a construction or as a formula of a
formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symb ...
. For example, the positive square root of 2, \sqrt, can be defined as the unique positive solution to the equation x^2 = 2, and it can be constructed with a compass and straightedge. Different choices of a formal language or its interpretation give rise to different notions of definability. Specific varieties of definable numbers include the
constructible number In geometry and algebra, a real number r is constructible if and only if, given a line segment of unit length, a line segment of length , r, can be constructed with compass and straightedge in a finite number of steps. Equivalently, r is con ...
s of geometry, the
algebraic numbers An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio, (1 + \sqrt)/2, is an algebraic number, because it is a root of the po ...
, and the
computable number In mathematics, computable numbers are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. They are also known as the recursive numbers, effective numbers or the computable reals or recursive ...
s. Because formal languages can have only
countably many 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 number ...
formulas, every notion of definable numbers has at most countably many definable real numbers. However, by
Cantor's diagonal argument In set theory, Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument, the anti-diagonal argument, the diagonal method, and Cantor's diagonalization proof, was published in 1891 by Georg Cantor as a m ...
, there are uncountably many real numbers, so
almost every In measure theory (a branch of mathematical analysis), a property holds almost everywhere if, in a technical sense, the set for which the property holds takes up nearly all possibilities. The notion of "almost everywhere" is a companion notion to ...
real number is undefinable.


Constructible numbers

One way of specifying a real number uses geometric techniques. A real number r is a constructible number if there is a method to construct a line segment of length r using a compass and straightedge, beginning with a fixed line segment of length 1. Each positive integer, and each positive rational number, is constructible. The positive square root of 2 is constructible. However, the cube root of 2 is not constructible; this is related to the impossibility of
doubling the cube Doubling the cube, also known as the Delian problem, is an ancient geometric problem. Given the edge of a cube, the problem requires the construction of the edge of a second cube whose volume is double that of the first. As with the related pro ...
.


Real algebraic numbers

A real number r is called a real
algebraic number An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio, (1 + \sqrt)/2, is an algebraic number, because it is a root of the po ...
if there is a
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
p(x), with only integer coefficients, so that r is a root of p, that is, p(r)=0. Each real algebraic number can be defined individually using the order relation on the reals. For example, if a polynomial q(x) has 5 real roots, the third one can be defined as the unique r such that q(r)=0 and such that there are two distinct numbers less than r at which q is zero. All rational numbers are algebraic, and all constructible numbers are algebraic. There are numbers such as the cube root of 2 which are algebraic but not constructible. The real algebraic numbers form a subfield of the real numbers. This means that 0 and 1 are algebraic numbers and, moreover, if a and b are algebraic numbers, then so are a+b, a-b, ab and, if b is nonzero, a/b. The real algebraic numbers also have the property, which goes beyond being a subfield of the reals, that for each positive integer n and each real algebraic number a, all of the nth roots of a that are real numbers are also algebraic. There are only
countably many 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 number ...
algebraic numbers, but there are uncountably many real numbers, so in the sense of
cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
most real numbers are not algebraic. This
nonconstructive proof In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object. This is in contrast to a non-constructive proof (also known as an existen ...
that not all real numbers are algebraic was first published by Georg Cantor in his 1874 paper "
On a Property of the Collection of All Real Algebraic Numbers Cantor's first set theory article contains Georg Cantor's first theorems of transfinite set theory, which studies infinite sets and their properties. One of these theorems is his "revolutionary discovery" that the set of all real numbers is uncou ...
". Non-algebraic numbers are called
transcendental numbers In mathematics, a transcendental number is a number that is not algebraic—that is, not the root of a non-zero polynomial of finite degree with rational coefficients. The best known transcendental numbers are and . Though only a few classes ...
. The best known transcendental numbers are and .


Computable real numbers

A real number is a
computable number In mathematics, computable numbers are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. They are also known as the recursive numbers, effective numbers or the computable reals or recursive ...
if there is an algorithm that, given a natural number n, produces a decimal expansion for the number accurate to n decimal places. This notion was introduced by
Alan Turing Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical com ...
in 1936. The computable numbers include the algebraic numbers along with many transcendental numbers including \pi Like the algebraic numbers, the computable numbers also form a subfield of the real numbers, and the positive computable numbers are closed under taking nth roots for each Not all real numbers are computable. Specific examples of noncomputable real numbers include the limits of
Specker sequence In computability theory, a Specker sequence is a computable, monotonically increasing, bounded sequence of rational numbers whose supremum is not a computable real number. The first example of such a sequence was constructed by Ernst Specker (1949 ...
s, and algorithmically random real numbers such as Chaitin's Ω numbers.


Definability in arithmetic

Another notion of definability comes from the formal theories of arithmetic, such as
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 nearly u ...
. The language of arithmetic has symbols for 0, 1, the successor operation, addition, and multiplication, intended to be interpreted in the usual way over the
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...
s. Because no variables of this language range over the
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s, a different sort of definability is needed to refer to real numbers. A real number a is ''definable in the language of arithmetic'' (or '' arithmetical'') if its
Dedekind cut In mathematics, Dedekind cuts, named after German mathematician Richard Dedekind but previously considered by Joseph Bertrand, are а method of construction of the real numbers from the rational numbers. A Dedekind cut is a partition of the rat ...
can be defined as a
predicate Predicate or predication may refer to: * Predicate (grammar), in linguistics * Predication (philosophy) * several closely related uses in mathematics and formal logic: **Predicate (mathematical logic) **Propositional function **Finitary relation, o ...
in that language; that is, if there is a first-order formula \varphi in the language of arithmetic, with three free variables, such that \forall m \, \forall n \, \forall p \left (\varphi(n,m,p)\iff\frac Here ''m'', ''n'', and ''p'' range over nonnegative integers. The second-order language of arithmetic is the same as the first-order language, except that variables and quantifiers are allowed to range over sets of naturals. A real that is second-order definable in the language of arithmetic is called '' analytical''. Every computable real number is arithmetical, and the arithmetical numbers form a subfield of the reals, as do the analytical numbers. Every arithmetical number is analytical, but not every analytical number is arithmetical. Because there are only countably many analytical numbers, most real numbers are not analytical, and thus also not arithmetical. Every computable number is arithmetical, but not every arithmetical number is computable. For example, the limit of a
Specker sequence In computability theory, a Specker sequence is a computable, monotonically increasing, bounded sequence of rational numbers whose supremum is not a computable real number. The first example of such a sequence was constructed by Ernst Specker (1949 ...
is an arithmetical number that is not computable. The definitions of arithmetical and analytical reals can be stratified into 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 ...
and
analytical hierarchy In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy. The analytical hierarchy of formulas includes formulas in the language of second-order arithmetic, which can have quantifiers ...
. In general, a real is computable if and only if its Dedekind cut is at level \Delta^0_1 of the arithmetical hierarchy, one of the lowest levels. Similarly, the reals with arithmetical Dedekind cuts form the lowest level of the analytical hierarchy.


Definability in models of ZFC

A real number a is first-order definable in the language of set theory, without parameters, if there is a formula \varphi in the language of
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
, with one
free variable In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation (symbol) that specifies places in an expression where substitution may take place and is not ...
, such that a is the unique real number such that \varphi(a) holds. This notion cannot be expressed as a formula in the language of set theory. All analytical numbers, and in particular all computable numbers, are definable in the language of set theory. Thus the real numbers definable in the language of set theory include all familiar real numbers such as 0, 1, \pi, e, et cetera, along with all algebraic numbers. Assuming that they form a set in the model, the real numbers definable in the language of set theory over a particular model of ZFC form a field. Each set
model A model is an informative representation of an object, person or system. The term originally denoted the Plan_(drawing), plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a mea ...
M of ZFC set theory that contains uncountably many real numbers must contain real numbers that are not definable within M (without parameters). This follows from the fact that there are only countably many formulas, and so only countably many elements of M can be definable over M. Thus, if M has uncountably many real numbers, one can prove from "outside" M that not every real number of M is definable over M. This argument becomes more problematic if it is applied to
class Class or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used differentl ...
models of ZFC, such as the
von Neumann universe In set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted by ''V'', is the class of hereditary well-founded sets. This collection, which is formalized by Zermelo–Fraenkel set theory (Z ...
. The assertion "the real number x is definable over the ''class'' model N" cannot be expressed as a formula of ZFC. Similarly, the question of whether the von Neumann universe contains real numbers that it cannot define cannot be expressed as a sentence in the language of ZFC. Moreover, there are countable models of ZFC in which all real numbers, all sets of real numbers, functions on the reals, etc. are definable.


See also

*
Berry's paradox The Berry paradox is a self-referential paradox arising from an expression like "The smallest positive integer not definable in under sixty letters" (a phrase with fifty-seven letters). Bertrand Russell, the first to discuss the paradox in print, ...
*
Constructible universe In mathematics, in set theory, the constructible universe (or Gödel's constructible universe), denoted by , is a particular class of sets that can be described entirely in terms of simpler sets. is the union of the constructible hierarchy . It w ...
* ''
Entscheidungsproblem In mathematics and computer science, the ' (, ) is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. The problem asks for an algorithm that considers, as input, a statement and answers "Yes" or "No" according to whether the statem ...
'' *
Ordinal definable set In mathematical set theory, a set ''S'' is said to be ordinal definable if, informally, it can be defined in terms of a finite number of ordinals by a first-order formula. Ordinal definable sets were introduced by . A drawback to this informal de ...
*
Tarski's undefinability 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 ...


References

{{Number systems Set theory