Definable real number: Difference between revisions

Revision as of 12:50, 1 July 2021

Revision as of 22:27, 2 July 2021

Line 1:

{{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''']]

Line 34 ⟶ 33:

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''.

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 Ω numbers]].

== Definability in arithmetic ==

Line 56 ⟶ 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]].{{cn|date=May 2021}} The argument that applies to set models cannot be directly generalized to class models in ZFC because the propertyassertion "the real number ''x'' is definable over the ''class'' model ''N''" cannot be expressed as a formula of ZFC.{{sfn|Hamkins|Linetsky|Reitz|2013}}{{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}}{{sfn|Tsirelson|2020}}

== See also ==

Line 67 ⟶ 66:

==References==

{{reflist}}

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

* {{Citation | last1=KunenHamkins | first1=KennethJoel David | author1-linklast2=KennethLinetsky Kunen| first2=David | last3=Reitz | first3=Jonas | year=2013 | title=[[Pointwise Definable Models of Set Theory: An| Introductionjournal=Journal toof IndependenceSymbolic Proofs]]Logic | publishervolume=North-Holland78 | ___locationissue=Amsterdam1 | isbnpages=978-0-444-85401-8139–156 | yeararxiv=1105.4597 | doi=10.2178/jsl.7801090 | s2cid=198043689192}}.

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

*{{Citation | last= Turing | first= A.M. | 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 | url = http://www.abelard.org/turpap2/tp2-ie.asp | doi= 10.1112/plms/s2-42.1.230 }}

** {{Citation | last last1=Tsirelson Turing| first1=Boris | first author1-link=Boris A.M.Tsirelson | title year=2020 On| Computabletitle=Can Numbers,each withnumber anbe Applicationspecified toby thea Entscheidungsproblem:finite A correctiontext? | periodical = ProceedingsWikiJournal of the London Mathematical Society | series = 2Science | volume = 433 | issue = 6 | pages = 544–61 | doi = 10.111215347/plmsWJS/s2-432020.6.544 | year = 1938008 }}

* {{Citation | lastlast1= Turing | firstfirst1= A.M. | year 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 | urldoi=10.1112/plms/s2-42.1.230 =| url=http://www.abelard.org/turpap2/tp2-ie.asp | doi= 10.1112/plms/s2-42.1.230 }}

==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]]