Definable real number: Difference between revisions

Revision as of 07:34, 5 July 2021

Latest revision as of 02:55, 9 April 2024

(12 intermediate revisions by 9 users not shown)

Line 1:

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

[[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 14 ⟶ 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> at 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>.

Line 26 ⟶ 27:

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 <math>\[[Pi|{{pi</math>}}]] and {{nowrapmvar|[[Euler'se number]](mathematical <math>constant)|e</math>.]]}}.

== Computable real numbers ==

Line 44 ⟶ 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.

Line 51 ⟶ 52:

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.{{r|kunen}} 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, one can prove from "outside" <math>M</math> that not every real number of <math>M</math> is definable over <math>M</math>.

Line 60 ⟶ 61:

* [[Berry's paradox]]

* [[Constructible universe]]

* ''[[Entscheidungsproblem]]''

* [[Ordinal definable set]]

* [[Richard's paradox]]

* [[Tarski's undefinability theorem]]

Line 71 ⟶ 73:

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

}}