Manidh: 1 revision imported

2023-07-27T05:03:43Z

1 revision imported

← Older revision	Revision as of 10:33, 27 July 2023
(No difference)

131.220.184.222: According to the above paragraph, \aleph_\beta saturated real closed fields of cardinality \aleph_\beta are isomorphic; Size \eta_\beta does not really make sense.

2023-05-10T09:55:17Z

According to the above paragraph, \aleph_\beta saturated real closed fields of cardinality \aleph_\beta are isomorphic; Size \eta_\beta does not really make sense.

New page

{{short description|Non algebraically closed field whose extension by sqrt(–1) is algebraically closed}}
{{hatnote|"Artin–Schreier theorem" redirects here. For the branch of Galois theory, see [[Artin–Schreier theory]].}}

In [[mathematics]], a '''real closed field''' is a [[field (mathematics)|field]] ''F'' that has the same [[first-order logic|first-order]] properties as the field of [[real number]]s. Some examples are the field of real numbers, the field of real [[algebraic number]]s, and the field of [[hyperreal number]]s.

==Definitions==
A real closed field is a field ''F'' in which any of the following equivalent conditions is true:

#''F'' is [[elementarily equivalent]] to the real numbers. In other words, it has the same first-order properties as the reals: any [[sentence (mathematical logic)|sentence]] in the first-order language of fields is true in ''F'' [[if and only if]] it is true in the reals.
#There is a [[total order]] on ''F'' making it an [[ordered field]] such that, in this ordering, every positive element of ''F'' has a [[Square root#In integral domains, including fields|square root]] in ''F'' and any [[polynomial]] of [[parity (mathematics)|odd]] [[degree of a polynomial|degree]] with [[coefficient]]s in ''F'' has at least one [[Root of a function|root]] in ''F''.
#''F'' is a [[formally real field]] such that every polynomial of odd degree with coefficients in ''F'' has at least one root in ''F'', and for every element ''a'' of ''F'' there is ''b'' in ''F'' such that ''a'' = ''b''2 or ''a'' = −''b''2.
#''F'' is not [[algebraically closed]], but its [[algebraic closure]] is a [[finite extension]].
#''F'' is not algebraically closed but the [[field extension]] <math>F(\sqrt{-1}\,)</math> is algebraically closed.
#There is an ordering on ''F'' that does not extend to an ordering on any proper [[algebraic extension]] of ''F''.
#''F'' is a formally real field such that no proper algebraic extension of ''F'' is formally real. (In other words, the field is maximal in an algebraic closure with respect to the property of being formally real.)
#There is an ordering on ''F'' making it an ordered field such that, in this ordering, the [[intermediate value theorem]] holds for all polynomials over ''F'' with degree ''≥'' 0.
# ''F'' is a [[weakly o-minimal structure|weakly o-minimal]] ordered field.<ref>D. Macpherson ''et al.'' (1998)</ref>

If ''F'' is an ordered field, the '''Artin–Schreier theorem''' states that ''F'' has an algebraic extension, called the '''real closure''' ''K'' of ''F'', such that ''K'' is a real closed field whose ordering is an extension of the given ordering on ''F'', and is unique [[up to]] a unique [[isomorphism]] of fields identical on ''F''<ref>Rajwade (1993) pp. 222–223</ref> (note that every [[ring homomorphism]] between real closed fields automatically is [[order isomorphism|order preserving]], because ''x'' ≤ ''y'' if and only if ∃''z'' : ''y'' = ''x'' + ''z''2). For example, the real closure of the ordered field of [[rational number]]s is the field <math>\mathbb{R}_\mathrm{alg}</math> of real algebraic numbers. The [[theorem]] is named for [[Emil Artin]] and [[Otto Schreier]], who [[mathematical proof|proved]] it in 1926.

If (''F'', ''P'') is an ordered field, and ''E'' is a [[Galois extension]] of ''F'', then by [[Zorn's lemma]] there is a maximal ordered field extension (''M'', ''Q'') with ''M'' a [[field extension|subfield]] of ''E'' containing ''F'' and the order on ''M'' extending ''P''. This ''M'', together with its ordering ''Q'', is called the '''relative real closure''' of (''F'', ''P'') in ''E''. We call (''F'', ''P'') ''' real closed relative to''' ''E'' if ''M'' is just ''F''. When ''E'' is the algebraic closure of ''F'' the relative real closure of ''F'' in ''E'' is actually the '''real closure''' of ''F'' described earlier.<ref name=Efr177>Efrat (2006) p. 177</ref>

If ''F'' is a field (no ordering compatible with the field operations is assumed, nor is it assumed that ''F'' is orderable) then ''F'' still has a real closure, which may not be a field anymore, but just a
[[real closed ring]]. For example, the real closure of the field <math>\mathbb{Q}(\sqrt 2)</math> is the [[ring (mathematics)|ring]] <math>\mathbb{R}_\mathrm{alg} \!\times \mathbb{R}_\mathrm{alg}</math> (the two copies correspond to the two orderings of <math>\mathbb{Q}(\sqrt 2)</math>). On the other hand, if <math>\mathbb{Q}(\sqrt 2)</math> is considered as an ordered subfield
of <math>\mathbb{R}</math>, its real closure is again the field <math>\mathbb{R}_\mathrm{alg}</math>.

==Decidability and quantifier elimination==
The [[Formal language|language]] of real closed fields <math>\mathcal{L}_\text{rcf}</math> includes symbols for the operations of addition and multiplication, the constants 0 and 1, and the order relation {{math|≤}} (as well as equality, if this is not considered a logical symbol). In this language, the (first-order) theory of real closed fields, <math>\mathcal{T}_\text{rcf}</math>, consists of the following:

* the [[axiom]]s of [[ordered field]]s;
* the axiom asserting that every positive number has a square root;
* for every odd number <math>d</math>, the axiom asserting that all polynomials of degree <math>d</math> have at least one root.

All of the above axioms can be expressed in [[first-order logic]] (i.e. [[quantifier (logic)|quantification]] ranges only over elements of the field).

[[Alfred Tarski|Tarski]] proved ({{circa|1931}}) that <math>\mathcal{T}_\text{rcf}</math> is [[Complete theory|complete]], meaning that for any <math>\mathcal{L}_\text{rcf}</math>-sentence, it can be proven either true or false from the above axioms. Furthermore, <math>\mathcal{T}_\text{rcf}</math> is [[decidability (logic)|decidable]], meaning that there is an [[algorithm]] to decide the truth or falsity of any such sentence.{{Citation needed|date=April 2020}}

The [[Tarski–Seidenberg theorem]] extends this result to decidable [[quantifier elimination]]. That is, there is an algorithm that, given any <math>\mathcal{L}_\text{rcf}</math>-[[well-formed formula|formula]], which may contain [[free variable]]s, produces an equivalent quantifier-free formula in the same free variables, where ''equivalent'' means that the two formulas are true for exactly the same values of the variables. The Tarski–Seidenberg theorem is an extension of the decidability theorem, as it can be easily checked whether a quantifier-free formula without free variables is ''true'' or ''false''.

This theorem can be further extended to the following ''projection theorem''. If {{math|'''R'''}} is a real closed field, a formula with {{mvar|n}} free variables defines a subset of {{math|'''R'''{{sup|''n''}}}}, the set of the points that satisfy the formula. Such a subset is called a [[semialgebraic set]]. Given a subset of {{mvar|k}} variables, the ''projection'' from {{math|'''R'''{{sup|''n''}}}} to {{math|'''R'''{{sup|''k''}}}} is the [[function (mathematics)|function]] that maps every {{mvar|n}}-tuple to the {{mvar|k}}-tuple of the components corresponding to the subset of variables. The projection theorem asserts that a projection of a semialgebraic set is a semialgebraic set, and that there is an algorithm that, given a quantifier-free formula defining a semialgebraic set, produces a quantifier-free formula for its projection.

In fact, the projection theorem is equivalent to quantifier elimination, as the projection of a semialgebraic set defined by the formula {{math|''p''(''x'', ''y'')}} is defined by
:<math>(\exists x) P(x,y),</math>
where {{mvar|x}} and {{mvar|y}} represent respectively the set of eliminated variables, and the set of kept variables.

The decidability of a first-order theory of the real numbers depends dramatically on the primitive operations and functions that are considered (here addition and multiplication). Adding other functions symbols, for example, the [[sine]] or the [[exponential function]], can provide undecidable theories; see [[Richardson's theorem]] and [[Decidability of first-order theories of the real numbers]].

=== Complexity of deciding 𝘛rcf ===
Tarski's original algorithm for [[quantifier elimination]] has [[nonelementary problem|nonelementary]] [[computational complexity]], meaning that no tower

:<math>2^{2^{\cdot^{\cdot^{\cdot^n}}}}</math>

can bound the execution time of the algorithm if {{mvar|n}} is the size of the input formula. The [[cylindrical algebraic decomposition]], introduced by [[George E. Collins]], provides a much more practicable algorithm of complexity
:<math>d^{2^{O(n)}}</math>
where {{mvar|n}} is the total number of variables (free and bound), {{mvar|d}} is the product of the degrees of the polynomials occurring in the formula, and {{math|''O''(''n'')}} is [[big O notation]].

Davenport and Heintz (1988) proved that this [[worst-case complexity]] is nearly optimal for quantifier elimination by producing a family {{math|Φ''n''}} of formulas of length {{math|''O''(''n'')}}, with {{mvar|n}} quantifiers, and involving polynomials of constant degree, such that any quantifier-free formula equivalent to {{math|Φ''n''}} must involve polynomials of degree <math>2^{2^{\Omega(n)}}</math> and length <math>2^{2^{\Omega(n)}},</math> where <math>\Omega(n)</math> is [[big Omega notation]]. This shows that both the time complexity and the space complexity of quantifier elimination are intrinsically [[double exponential time|double exponential]].

For the decision problem, Ben-Or, [[Dexter Kozen|Kozen]], and [[John Reif|Reif]] (1986) claimed to have proved that the theory of real closed fields is decidable in [[EXPSPACE|exponential space]], and therefore in double exponential time, but their argument (in the case of more than one variable) is generally held as flawed; see Renegar (1992) for a discussion.

For purely existential formulas, that is for formulas of the form
:{{math|∃''x''1, ..., ∃''x''''k'' ''P''1(''x''1, ..., ''x''''k'') ⋈ 0 ∧ ... ∧ ''P''''s''(''x''1, ..., ''x''''k'') ⋈ 0,}}
where {{math|⋈}} stands for either {{math|<, >}} or {{math|1==}}, the complexity is lower. Basu and [[Marie-Françoise Roy|Roy]] (1996) provided a well-behaved algorithm to decide the truth of such an existential formula with complexity of {{math|''s''''k''+1''d''''O''(''k'')}} arithmetic operations and [[PSPACE|polynomial space]].

== Order properties ==

A crucially important property of the real numbers is that it is an [[Archimedean field]], meaning it has the Archimedean property that for any real number, there is an [[integer]] larger than it in [[absolute value]]. An equivalent statement is that for any real number, there are integers both larger and smaller. Such real closed fields that are not Archimedean, are [[non-Archimedean ordered field]]s. For example, any field of [[hyperreal number]]s is real closed and non-Archimedean.

The Archimedean property is related to the concept of [[cofinality]]. A set ''X'' contained in an ordered set ''F'' is cofinal in ''F'' if for every ''y'' in ''F'' there is an ''x'' in ''X'' such that ''y'' < ''x''. In other words, ''X'' is an unbounded sequence in ''F''. The cofinality of ''F'' is the [[cardinality]] of the smallest cofinal set, which is to say, the size of the smallest cardinality giving an unbounded sequence. For example, [[natural number]]s are cofinal in the reals, and the cofinality of the reals is therefore <math>\aleph_0</math>.

We have therefore the following invariants defining the nature of a real closed field ''F'':

* The cardinality of ''F''.
* The cofinality of ''F''.

To this we may add

* The weight of ''F'', which is the minimum size of a dense subset of ''F''.

These three cardinal numbers tell us much about the order properties of any real closed field, though it may be difficult to discover what they are, especially if we are not willing to invoke the [[continuum hypothesis|generalized continuum hypothesis]]. There are also particular properties that may or may not hold:

* A field ''F'' is '''complete''' if there is no ordered field ''K'' properly containing ''F'' such that ''F'' is dense in ''K''. If the cofinality of ''F'' is ''κ'', this is equivalent to saying [[Cauchy sequence]]s indexed by ''κ'' are [[convergent sequence|convergent]] in ''F''.
* An ordered field ''F'' has the [[eta set]] property η''α'', for the [[ordinal number]] ''α'', if for any two subsets ''L'' and ''U'' of ''F'' of cardinality less than <math>\aleph_\alpha</math> such that every element of ''L'' is less than every element of ''U'', there is an element ''x'' in ''F'' with ''x'' larger than every element of ''L'' and smaller than every element of ''U''. This is closely related to the [[model-theoretic]] property of being a [[saturated model]]; any two real closed fields are η''α'' if and only if they are <math>\aleph_\alpha</math>-saturated, and moreover two η''α'' real closed fields both of cardinality <math>\aleph_\alpha</math> are [[order isomorphic]].

== The generalized continuum hypothesis ==

The characteristics of real closed fields become much simpler if we are willing to assume the [[continuum hypothesis|generalized continuum hypothesis]]. If the continuum hypothesis holds, all real closed fields with [[cardinality of the continuum]] and having the ''η''1 property are order isomorphic. This unique field ''Ϝ'' can be defined by means of an [[ultraproduct|ultrapower]], as <math>\mathbb{R}^{\mathbb{N}}/\mathbf{M}</math>, where '''M''' is a maximal ideal not leading to a field order-isomorphic to <math>\mathbb{R}</math>. This is the most commonly used [[hyperreal number|hyperreal number field]] in [[nonstandard analysis]], and its uniqueness is equivalent to the continuum hypothesis. (Even without the continuum hypothesis we have that if the cardinality of the continuum is
<math>\aleph_\beta</math> then we have a unique [[eta set|''η''''β'' field]] of size <math>\aleph_\beta</math>.)

Moreover, we do not need ultrapowers to construct ''Ϝ'', we can do so much more constructively as the subfield of series with a [[countably infinite|countable]] number of nonzero terms of the field <math>\mathbb{R}[[G]]</math> of [[formal power series]] on a [[totally ordered group|totally ordered]] [[abelian group|abelian]] [[divisible group]] ''G'' that is an [[eta set|''η''1 group]] of cardinality <math>\aleph_1</math> {{harv|Alling|1962}}.

''Ϝ'' however is not a complete field; if we take its completion, we end up with a field ''Κ'' of larger cardinality. ''Ϝ'' has the cardinality of the continuum, which by hypothesis is <math>\aleph_1</math>, ''Κ'' has cardinality <math>\aleph_2</math>, and contains ''Ϝ'' as a dense subfield. It is not an ultrapower but it ''is'' a hyperreal field, and hence a suitable field for the usages of nonstandard analysis. It can be seen to be the higher-dimensional analogue of the real numbers; with cardinality <math>\aleph_2</math> instead of <math>\aleph_1</math>, cofinality <math>\aleph_1</math> instead of <math>\aleph_0</math>, and weight <math>\aleph_1</math> instead of <math>\aleph_0</math>, and with the ''η''1 property in place of the ''η''0 property (which merely means between any two real numbers we can find another).

== Examples of real closed fields ==

* the real [[algebraic numbers]]
* the [[computable number]]s
* the [[definable number]]s
* the [[real number]]s
* [[superreal number]]s
* [[hyperreal number]]s
* the [[Puiseux series]] with real coefficients
* the [[surreal number]]s

==Notes==
{{reflist}}

== References ==

*{{citation|title=On the existence of real-closed fields that are ηα-sets of power ℵα.
|first= Norman L.|last= Alling
|journal= Trans. Amer. Math. Soc.|volume= 103 |year=1962|pages= 341–352
|mr= 0146089|doi=10.1090/S0002-9947-1962-0146089-X|doi-access= free}}
* Basu, Saugata, [[Richard M. Pollack|Richard Pollack]], and [[Marie-Françoise Roy]] (2003) "Algorithms in real algebraic geometry" in ''Algorithms and computation in mathematics''. Springer. {{isbn|3-540-33098-4}} ([http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted1.html online version])
* Michael Ben-Or, Dexter Kozen, and John Reif, ''[http://www.cs.duke.edu/~reif/paper/benor/realclosed.pdf The complexity of elementary algebra and geometry]'', Journal of Computer and Systems Sciences 32 (1986), no. 2, pp. 251–264.
* Caviness, B F, and Jeremy R. Johnson, eds. (1998) ''Quantifier elimination and cylindrical algebraic decomposition''. Springer. {{isbn|3-211-82794-3}}
* [[Chen Chung Chang]] and [[Howard Jerome Keisler]] (1989) ''Model Theory''. North-Holland.
* Dales, H. G., and [[W. Hugh Woodin]] (1996) ''Super-Real Fields''. Oxford Univ. Press.
* {{cite journal | last1=Davenport | first1=James H. | author1-link=James H. Davenport | last2=Heintz | first2=Joos | title=Real quantifier elimination is doubly exponential | journal=J. Symb. Comput. | volume=5 | number=1–2 | pages= 29–35 | year=1988 | zbl=0663.03015 | doi=10.1016/s0747-7171(88)80004-x| doi-access=free }}
* {{cite book | last=Efrat | first=Ido | title=Valuations, orderings, and Milnor ''K''-theory | series=Mathematical Surveys and Monographs | volume=124 | location=Providence, RI | publisher=[[American Mathematical Society]] | year=2006 | isbn=0-8218-4041-X | zbl=1103.12002 }}
* Macpherson, D., Marker, D. and Steinhorn, C., ''Weakly o-minimal structures and real closed fields'', Trans. of the American Math. Soc., Vol. 352, No. 12, 1998.
* Mishra, Bhubaneswar (1997) "[http://www.cs.nyu.edu/mishra/PUBLICATIONS/97.real-alg.ps Computational Real Algebraic Geometry]," in ''Handbook of Discrete and Computational Geometry''. CRC Press. 2004 edition, p. 743. {{isbn|1-58488-301-4}}
* {{cite book | title=Squares | volume=171 | series=London Mathematical Society Lecture Note Series | first=A. R. | last=Rajwade | publisher=[[Cambridge University Press]] | year=1993 | isbn=0-521-42668-5 | zbl=0785.11022 }}
* {{cite journal|last=Renegar|first=James|title=On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals|journal=Journal of Symbolic Computation|volume=13|number=3|year=1992|pages=255–299|doi=10.1016/S0747-7171(10)80003-3|doi-access=free}}
* {{cite thesis | type=PhD | title=Combined Decision Procedures for Nonlinear Arithmetics, Real and Complex | first=Grant | last=Passmore | publisher=[[University of Edinburgh]] | year=2011 | url=https://www.cl.cam.ac.uk/~gp351/passmore-phd-thesis.pdf | author-link=Grant Olney }}
*[[Alfred Tarski]] (1951) ''A Decision Method for Elementary Algebra and Geometry''. Univ. of California Press.
*{{citation|first= P.|last= Erdös|first2= L.|last2= Gillman|first3= M. |last3=Henriksen|title= An isomorphism theorem for real-closed fields|journal= Ann. of Math. |series= 2|volume= 61 |issue= 3|pages= 542–554|mr= 0069161|year=1955 |doi=10.2307/1969812|url= https://scholarship.claremont.edu/cgi/viewcontent.cgi?article=2016&context=hmc_fac_pub|jstor= 1969812}}

==External links==
{{Commons category}}
*[http://www.maths.manchester.ac.uk/raag/ ''Real Algebraic and Analytic Geometry Preprint Server'']
*[http://www.logique.jussieu.fr/modnet/Publications/Preprint%20server/ ''Model Theory preprint server'']

[[Category:Real closed field| ]]
[[Category:Field (mathematics)]]
[[Category:Real algebraic geometry]]

Real closed field - Revision history

Manidh: 1 revision imported

131.220.184.222: According to the above paragraph, \aleph_\beta saturated real closed fields of cardinality \aleph_\beta are isomorphic; Size \eta_\beta does not really make sense.