Definable real number: Difference between revisions

Revision as of 22:30, 2 July 2021

Revision as of 00:58, 3 July 2021

Line 29:

== Computable real numbers ==

A real number is a [[computable number]] 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]] in 1936.{{sfnr|Turing|1937turing}}

The computable numbers include the algebraic numbers along with many transcendental numbers including π and ''e''. Like the algebraic numbers, the computable numbers also form a subfield of the real numbers, and the positive computable numbers are closed under taking ''n''th roots for each positive ''n''.

Line 49:

== 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 ''φ'' in the language of [[set theory]], with one [[free variable]], such that ''a'' is the unique real number such that ''φ''(''a'') holds.{{sfnr|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|π]], [[E (mathematical constant)|''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 [[Zermelo–Fraenkel set theory|ZFC]] form a field.

Line 55:

Each set [[Model theory|model]] ''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, we 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 (set theory)|class]] models of ZFC, such as the [[von Neumann universe]]. The assertion "the real number ''x'' is definable over the ''class'' model ''N''" cannot be expressed as a formula of ZFC.{{sfnr|Hamkinshlr|Linetsky|Reitz|2013tsirelson}}{{sfn|Tsirelson|2020}} 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.{{sfn|Hamkins|Linetsky|Reitz|2013}}{{sfnr|Tsirelsonhlr|2020tsirelson}}

== See also ==

Line 65:

==References==

{{reflist}}|refs=

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

* {{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}}.

*<ref name=kunen>{{Citation | last1=TsirelsonKunen | first1=BorisKenneth | author1-link=BorisKenneth TsirelsonKunen | year=20201980 | title=Can[[Set eachTheory: numberAn beIntroduction specifiedto byIndependence a finite text?Proofs]] | periodicalpublisher=WikiJournal of ScienceNorth-Holland | volume___location=3Amsterdam | issueisbn=1978-0-444-85401-8 | doipage=10.15347/WJS/2020.008 153}}</ref>

* {{Citation | last1=Turing | first1=A.M. | author1-link=Alan Turing | year=1937 | 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 | doi=10.1112/plms/s2-42.1.230 | url=http://www.abelard.org/turpap2/tp2-ie.asp }}

<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 | doi=10.15347/WJS/2020.008 }}</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 | periodicaljournal=[[Proceedings of the London Mathematical Society]] | series=2 | volume=42 | issue=1 | pages=230–65 | doi=10.1112/plms/s2-42.1.230 | url=http://www.abelard.org/turpap2/tp2-ie.asp }}</ref>

}}

{{Number systems}}