Definable real number: Difference between revisions

Revision as of 17:02, 25 November 2020

Latest revision as of 02:55, 9 April 2024

(33 intermediate revisions by 17 users not shown)

Line 1:

{{Short description|Real number uniquely specified by description}}

{{Format footnotes|date=September 2020|reason=Parenthetical referencing has been [[WP:PARREF|deprecated]]; convert to [[Help:Shortened footnotes|shortened footnotes]].}}

[[File:Square root of 2 triangle.svg|thumb|200px|The [[square root of 2]] is equal to the length of the [[hypotenuse]] of a [[right triangle]] with legs of length 1 and is therefore a '''constructible number''']]

Informally, a '''definable real number''' is a [[real number]] that can be uniquely specified by its description. The description may be expressed as a construction or as a formula of a [[formal language]]. For example, the positive square root of 2, <math>\sqrt{2}</math>, can be defined as the unique positive solution to the equation <math>x^2 = 2</math>, and it can be constructed with a compass and straightedge.

Different choices of a formal language or its interpretation can give rise to different notions of definability. Specific varieties of definable numbers include the [[constructible number]]s of geometry, the [[algebraic numbers]], and the [[computable number]]s. Because formal languages can have only [[countably many]] formulas, every notion of definable numbers has at most countably many definable real numbers. However, by [[Cantor's diagonal argument]], there are uncountably many real numbers, so [[almost everywhere|almost every]] real number is undefinable.

== Constructible numbers ==

{{main article|Constructible number}}

One way of specifying a real number uses geometric techniques. A real number ''<math>r''</math> is a constructible number if there is a method to construct a line segment of length ''<math>r''</math> 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]].

Line 15:

[[File:Algebraicszoom.png|thumb|Algebraic numbers on the [[complex plane]] colored by degree (red=1, green=2, blue=3, yellow=4)]]

A real number ''<math>r''</math> is called a real [[algebraic number]] if there is a [[polynomial]] ''<math>p''(''x'')</math>, with only integer coefficients, so that ''<math>r''</math> is a root of ''<math>p''</math>, that is, ''<math>p''(''r'')=0</math>.

Each real algebraic number can be defined individually using the order relation on the reals. For example, if a polynomial ''<math>q''(''x'')</math> has 5 real roots, the third one can be defined as the unique ''<math>r''</math> such that ''<math>q''(''r'') = 0</math> and such that there are two distinct numbers less than ''<math>r''</math> forat which ''<math>q''</math> is zero.

All rational numbers are algebraicconstructible, 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 [[field extension|subfield]] of the real numbers. This means that 0 and 1 are algebraic numbers and, moreover, if ''<math>a''</math> and ''<math>b''</math> are algebraic numbers, then so are ''<math>a''+''b''</math>, ''<math>a''−''-b''</math>, ''<math>ab''</math> and, if ''<math>b''</math> is nonzero, ''<math>a''/''b''</math>.

The real algebraic numbers also have the property, which goes beyond being a subfield of the reals, that for each positive integer ''<math>n''</math> and each real algebraic number ''<math>a''</math>, all of the ''<math>n''</math>th roots of ''<math>a''</math> that are real numbers are also algebraic.

There are only [[Countable set|countably many]] algebraic numbers, but there are uncountably many real numbers, so in the sense of [[cardinality]] most real numbers are not algebraic. This [[nonconstructive proof]] that not all real numbers are algebraic was first published by

Georg Cantor in his 1874 paper "[[Georg Cantor's first set theory article|On a Property of the Collection of All Real Algebraic Numbers]]".

Non-algebraic numbers are called [[transcendental numbers]]. SpecificThe examplesbest ofknown transcendental numbers includeare &[[Pi|{{pi;}}]] and {{mvar|[[Euler'se number]](mathematical ''constant)|e'']]}}.

== Computable real numbers ==

A real number is a [[computable number]] if there is an algorithm that, given a natural number ''<math>n''</math>, produces a decimal expansion for the number accurate to ''<math>n''</math> decimal places. This notion was introduced by [[Alan Turing]] in 1936.{{r|turing}}

The computable numbers include the algebraic numbers along with many transcendental numbers including &<math>\pi;</math> {{nowrap|and&nbsp;'' <math>e''</math>.}} Like the algebraic numbers, the computable numbers also form a subfield of the real numbers, and the positive computable numbers are closed under taking ''<math>n''</math>th roots for each {{nowrap|positive&nbsp;'' <math>n''</math>.}}

Not all real numbers are computable. The entire set of computable numbers is countable, so most reals are not computable. Specific examples of noncomputable real numbers include the limits of [[Specker sequence]]s, and [[algorithmically random sequence|algorithmically random real numbers]] such as [[Chaitin's constant|Chaitin's &Omega; numbers]].

== Definability in arithmetic ==

Another notion of definability comes from the formal theories of arithmetic, such as [[Peano arithmetic]]. The [[Peano arithmetic|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]]s. Because no variables of this language range over the [[real number]]s, a different sort of definability is needed to refer to real numbers. A real number ''<math>a''</math> is ''definable in the language of arithmetic'' (or ''[[arithmetical hierarchy|arithmetical]]'') if its [[Dedekind cut]] can be defined as a [[Predicate (logic)|predicate]] in that language; that is, if there is a first-order formula ''φ''<math>\varphi</math> in the language of arithmetic, with three free variables, such that

:<math display=block>\forall m \, \forall n \, \forall p \left (\varphi(n,m,p)\iff\frac{(-1)^p\cdot n}{m+1}<a \right ).</math>

Here ''m'', ''n'', and ''p'' range over nonnegative integers.

Line 45:

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]] is an arithmetical number that is not computable.

The definitions of arithmetical and analytical reals can be stratified into the [[arithmetical hierarchy]] and [[analytical hierarchy]]. In general, a real is computable if and only if its Dedekind cut is at level <math>\Delta^0_1</math> 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 ''<math>a''</math> is '''first-order definable in the language of set theory, without parameters''', if there is a formula ''φ''<math>\varphi</math> in the language of [[set theory]], with one [[free variable]], such that ''<math>a''</math> is the unique real number such that ''φ''<math>\varphi(''a'')</math> holds (see .{{harvnbr|Kunen|1980|p=153kunen}}). 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 [[Zero|0]], [[One|1]], [[Pi|&<math>\pi;]]</math>, [[E (mathematical constant)|''<math>e'']]</math>, 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 [[Zermelo–Fraenkel set theory|ZFC]] form a field.

Each set [[Model theory|model]] ''<math>M''</math> of ZFC set theory that contains uncountably many real numbers must contain real numbers that are not definable within ''<math>M''</math> (without parameters). This follows from the fact that there are only countably many formulas, and so only countably many elements of ''<math>M''</math> can be definable over ''<math>M''</math>. Thus, if ''<math>M''</math> has uncountably many real numbers, weone can prove from "outside" ''<math>M''</math> that not every real number of ''<math>M''</math> is definable over ''<math>M''</math>.

This argument becomes more problematic if it is applied to [[class (set theory)|class]] models of ZFC, such as the [[von Neumann universe]] {{harv|Hamkins|2010}}. The argument that applies to set models cannot be directly generalized to class models in ZFC because the propertyassertion "the real number ''<math>x''</math> is definable over the ''class'' model ''<math>N''</math>" cannot be expressed as a formula of ZFC.{{r|hlr|tsirelson}} 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 .{{harvr|Hamkinshlr|Linetsky|Reitz|2013tsirelson}}.

== See also ==

* [[Berry's paradox]]

* [[Constructible universe]]

* ''[[Entscheidungsproblem]]''

* [[Ordinal definable set]]

* [[Richard's paradox]]

* [[Tarski's undefinability theorem]]

==References==

{{reflist|refs=

* {{Citation|last=Hamkins|first= Joel David|url=https://mathoverflow.net/q/44129 |title=Is the analysis as taught in universities in fact the analysis of definable numbers?|journal=MathOverflow|date=October 2010|accessdate=2016-03-05|authorlink=Joel David Hamkins}}.

* {{Citation|last1=Hamkins|first1=Joel David|last2=Linetsky|first2=David|last3=Reitz|first3=Jonas|title=Pointwise Definable Models of Set Theory|arxiv=1105.4597|journal=Journal of Symbolic Logic|volume=78|issue=1|pages=139–156|year=2013|doi=10.2178/jsl.7801090|s2cid=43689192}}.

*<ref name=hlr>{{Citation | last1=KunenHamkins | first1=KennethJoel David | author1-link =Kenneth KunenJoel David Hamkins | last2=Linetsky | first2=David | last3=Reitz | first3=Jonas | year=2013 | title=[[Pointwise Definable Models of Set Theory: An| Introductionjournal=[[Journal toof IndependenceSymbolic ProofsLogic]] | publishervolume=North-Holland78 | ___locationissue=Amsterdam1 | isbnpages=978-0-444-85401-8139–156 | yeararxiv=19801105.4597 | doi=10.2178/jsl.7801090 | s2cid=43689192}}.</ref>

*{{Citation | last= Turing | first= A.M. | publication-date = 1937 | year = 1936 | title = On Computable Numbers, with an Application to the Entscheidungsproblem | periodical = Proceedings of the London Mathematical Society | series = 2 | volume = 42 | issue= 1 | pages = 230–65 | url = http://www.abelard.org/turpap2/tp2-ie.asp | doi= 10.1112/plms/s2-42.1.230 }} (and {{Citation | last = Turing | first = A.M. | publication-date = 1937 | title = On Computable Numbers, with an Application to the Entscheidungsproblem: A correction | periodical = Proceedings of the London Mathematical Society | series = 2 | volume = 43 | issue = 6 | pages = 544–6 | doi = 10.1112/plms/s2-43.6.544 | year = 1938 }}). Computable numbers (and Turing's a-machines) were introduced in this paper; the definition of computable numbers uses infinite decimal sequences.

<ref name=kunen>{{Citation | last1=Kunen | first1=Kenneth | author1-link=Kenneth Kunen | year=1980 | title=[[Set Theory: An Introduction to Independence Proofs]] | publisher=North-Holland | ___location=Amsterdam | isbn=978-0-444-85401-8 | page=153}}</ref>

<ref name=tsirelson>{{Citation | last1=Tsirelson | first1=Boris | author1-link=Boris Tsirelson | year=2020 | title=Can each number be specified by a finite text? | periodical=WikiJournal of Science | volume=3 | issue=1 | page=8 | doi=10.15347/WJS/2020.008 | doi-access=free | arxiv=1909.11149 | s2cid=202749952 }}</ref>

<ref name=turing>{{Citation | last1=Turing | first1=A. M. | author1-link=Alan Turing | year=1937 | title=On Computable Numbers, with an Application to the Entscheidungsproblem | journal=[[Proceedings of the London Mathematical Society]] | series=2 | volume=42 | issue=1 | pages=230–65 | doi=10.1112/plms/s2-42.1.230 | s2cid=73712 | url=http://www.abelard.org/turpap2/tp2-ie.asp }}</ref>

}}

==External links==

* [[v:WikiJournal_Preprints/Can each number be specified by a finite text?|Can each number be specified by a finite text?]]

{{Number systems}}

[[Category:Set theory]]