Real closed field

Short description: Field in mathematics similar to the real numbers

"Artin–Schreier theorem" redirects here. For the branch of Galois theory, see Artin–Schreier theory.

In mathematics, a real closed field is a field F that has the same first-order properties as the field of real numbers. (First-order properties are those properties that can be expressed with the logic symbols ∀,∃,∨,∧,¬,-> and the arithmetic symbols 0,1,+,−,×,÷,=, where the domain of all quantifiers is the set F; it is hence not allowed to quantify over natural numbers, subsets of F, sequences in F, functions F->F etc.) Some examples of real closed fields are the field of real numbers itself, the field of real algebraic numbers, and fields of hyperreal numbers that include infinitesimals. In algebra, most theorems that involve the real numbers remain true when formulated for arbitrary real closed fields.

## Contents

* 1 Equivalent definitions
* 2 Examples of real closed fields
* 3 Real closure
* 4 Decidability and quantifier elimination
* 4.1 Complexity of deciding 𝘛rcf
* 5 Order properties
* 6 The generalized continuum hypothesis
* 7 Elementary Euclidean geometry
* 8 See also
* 9 Notes
* 10 References
* 11 External links

## Equivalent definitions

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

1. F is elementarily equivalent to the field of real numbers. In other words, it has the same first-order properties as the reals: any sentence in the first-order language of fields is true in F if and only if it is true in the reals.
2. There is a total order on F turning F into an ordered field such that, in this ordering, every positive element of F has a square root in F and any polynomial of odd degree with coefficients in F has at least one root in F.
3. There is a total order on F turning F into an ordered field such that, in this ordering, the intermediate value theorem holds for all polynomials with coefficients in F.
4. F is a formally real field (meaning there exists a total order on F turning F into an ordered 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 = b2 or a = −b2.
5. F is not algebraically closed, but its algebraic closure is a finite extension of F.
6. F is not algebraically closed but the field extension F(−1) is algebraically closed.
7. There is an ordering on F that does not extend to an ordering on any proper algebraic extension of F.
8. 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.)
9. F is a weakly o-minimal ordered field.[1]

## Examples of real closed fields

The following fields are real closed, which can be shown by verifying property 2 above:

* the field of real algebraic numbers;
* the field of computable real numbers;
* the field of definable real numbers;
* the field of real numbers;
* the field of Puiseux series with real coefficients;
* the Levi-Civita field;
* the hyperreal number fields;
* the superreal number fields;
* the field of surreal numbers (this is a proper class, not a set).

## Real closure

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[2] (note that every ring homomorphism between real closed fields automatically is order preserving, because x ≤ y if and only if ∃z : y = x + z2). For example, the real closure of the ordered field of rational numbers is the field ℝalg of real algebraic numbers. The theorem is named for Emil Artin and Otto Schreier, who 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 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.[3]

If F is a field (not ordered or even 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 ℚ(2) is the ring ℝalg×ℝalg (the two copies correspond to the two orderings of ℚ(2)). On the other hand, if ℚ(2) is considered as an ordered subfield of ℝ, its real closure is again the field ℝalg.

## Decidability and quantifier elimination

The language of real closed fields ℒrcf includes symbols for the operations of addition and multiplication, the constants 0 and 1, and the order relation ≤ (as well as equality, if this is not considered a logical symbol). In this language, the (first-order) theory of real closed fields, 𝒯rcf, consists of all sentences that follow from the following axioms:

* the axioms of ordered fields;
* the axiom asserting that every positive number has a square root;
* for every odd number d, the axiom asserting that all polynomials of degree d have at least one root.

All of these axioms can be expressed in first-order logic (i.e. quantification ranges only over elements of the field). Note that 𝒯rcf is just the set of all first-order sentences that are true about the field of real numbers.

Tarski showed that 𝒯rcf is complete, meaning that any ℒrcf-sentence can be proven either true or false from the above axioms. Furthermore, 𝒯rcf is decidable, meaning that there is an algorithm to determine the truth or falsity of any such sentence. This was done by showing quantifier elimination: there is an algorithm that, given any ℒrcf-formula, which may contain free variables, 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. Tarski's proof uses a generalization of Sturm's theorem. Since the truth of quantifier-free formulas without free variables can be easily checked, this yields the desired decision procedure. These results were obtained c. 1930 and published in 1948.[4]

The Tarski–Seidenberg theorem extends this result to the following projection theorem. If R is a real closed field, a formula with n free variables defines a subset of Rn, the set of the points that satisfy the formula. Such a subset is called a semialgebraic set. Given a subset of k variables, the projection from Rn to Rk is the function that maps every n-tuple to the 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 p(x, y) is defined by

(∃x)P(x,y),

where x and 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.

Furthermore, the completeness and decidability of the first-order theory of the real numbers (using addition and multiplication) contrasts sharply with Gödel's and Turing's results about the incompleteness and undecidability of the first-order theory of the natural numbers (using addition and multiplication). There is no contradiction, since the statement "x is an integer" cannot be formulated as a first-order formula in the language ℒrcf.

### Complexity of deciding 𝘛rcf

Tarski's original algorithm for quantifier elimination has nonelementary computational complexity, meaning that no tower

22⋅⋅⋅n

can bound the execution time of the algorithm if 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

d2O(n)

where n is the total number of variables (free and bound), d is the product of the degrees of the polynomials occurring in the formula, and 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 Φn of formulas of length O(n), with n quantifiers, and involving polynomials of constant degree, such that any quantifier-free formula equivalent to Φn must involve polynomials of degree 22Ω(n) and length 22Ω(n), where Ω(n) is big Omega notation. This shows that both the time complexity and the space complexity of quantifier elimination are intrinsically double exponential.

For the decision problem, Ben-Or, Kozen, and Reif (1986) claimed to have proved that the theory of real closed fields is decidable in 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

∃x1, ..., ∃xk P1(x1, ..., xk) ⋈ 0 ∧ ... ∧ Ps(x1, ..., xk) ⋈ 0,

where ⋈ stands for either <, > or =, the complexity is lower. Basu and Roy (1996) provided a well-behaved algorithm to decide the truth of such an existential formula with complexity of sk+1dO(k) arithmetic operations and polynomial space.

## Order properties

Any real closed field can be turned into an ordered field in just one way: the positive elements are precisely the squares of non-zero elements.

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. Note that this statement is not expressible in the first-order language of ordered fields, since it is not possible to quantify over integers in that language.

There are real-closed fields that are non-Archimedean; for example, any field of hyperreal numbers is real-closed and non-Archimedean. These fields contain infinitely large (larger than any integer) and infinitesimal (positive but smaller than any positive rational) elements.

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 numbers are cofinal in the reals, and the cofinality of the reals is therefore ℵ0.

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 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 sequences indexed by κ are 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 ℵα 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 ℵα-saturated, and moreover two ηα real closed fields both of cardinality ℵα are order isomorphic.

## The generalized continuum hypothesis

The characteristics of real closed fields become much simpler if we are willing to assume the 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 ultrapower, as ℝℕ/𝐌, where M is a maximal ideal not leading to a field order-isomorphic to ℝ. This is the most commonly used 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 ℵβ then we have a unique ηβ field of size ℵβ.)

Moreover, we do not need ultrapowers to construct Ϝ, we can do so much more constructively as the subfield of series with a countable number of nonzero terms of the field ℝG of formal power series on a totally ordered abelian divisible group G that is an η1 group of cardinality ℵ1 (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 ℵ1, Κ has cardinality ℵ2, 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 ℵ2 instead of ℵ1, cofinality ℵ1 instead of ℵ0, and weight ℵ1 instead of ℵ0, and with the η1 property in place of the η0 property (which merely means between any two real numbers we can find another).

## Elementary Euclidean geometry

Tarski's axioms are an axiom system for the first-order ("elementary") portion of Euclidean geometry. Using those axioms, one can show that the points on a line form a real closed field R, and one can introduce coordinates so that the Euclidean plane is identified with R2. Employing the decidability of the theory of real closed fields, Tarski then proved that the elementary theory of Euclidean geometry is complete and decidable.[4]

## See also

* Euclidean ordered field
* p-adically closed field
* real-closed ring

## Notes

1. ↑ D. Macpherson et al. (1998)
2. ↑ Rajwade (1993) pp. 222–223
3. ↑ Efrat (2006) p. 177
4. ↑ 4.0 4.1 McNaughton, Robert (1953). "Review: A decision method for elementary algebra and geometry by A. Tarski". Bull. Amer. Math. Soc. 59 (1): 91–93. doi:10.1090/s0002-9904-1953-09664-1. https://www.ams.org/journals/bull/1953-59-01/S0002-9904-1953-09664-1/S0002-9904-1953-09664-1.pdf.

## References

* Alling, Norman L. (1962), "On the existence of real-closed fields that are ηα-sets of power ℵα.", Trans. Amer. Math. Soc. 103: 341–352, doi:10.1090/S0002-9947-1962-0146089-X
* Basu, Saugata, 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 (online version )
* Michael Ben-Or, Dexter Kozen, and John Reif, 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.
* Davenport, James H.; Heintz, Joos (1988). "Real quantifier elimination is doubly exponential". J. Symb. Comput. 5 (1–2): 29–35. doi:10.1016/s0747-7171(88)80004-x.
* Efrat, Ido (2006). Valuations, orderings, and Milnor K-theory. Mathematical Surveys and Monographs. 124. Providence, RI: American Mathematical Society. ISBN 0-8218-4041-X.
* 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) "Computational Real Algebraic Geometry," in Handbook of Discrete and Computational Geometry. CRC Press. 2004 edition, p. 743\. ISBN 1-58488-301-4
* Rajwade, A. R. (1993). Squares. London Mathematical Society Lecture Note Series. 171. Cambridge University Press. ISBN 0-521-42668-5.
* Renegar, James (1992). "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 of Symbolic Computation 13 (3): 255–299. doi:10.1016/S0747-7171(10)80003-3.
* Passmore, Grant (2011). Combined Decision Procedures for Nonlinear Arithmetics, Real and Complex (PDF) (PhD). University of Edinburgh. `{{cite thesis}}`: Cite has empty unknown parameter: `|1=` (help)
* Alfred Tarski (1951) A Decision Method for Elementary Algebra and Geometry. Univ. of California Press.
* Erdös, P.; Gillman, L.; Henriksen, M. (1955), "An isomorphism theorem for real-closed fields", Ann. of Math., 2 61 (3): 542–554, doi:10.2307/1969812, https://scholarship.claremont.edu/cgi/viewcontent.cgi?article=2016&context=hmc_fac_pub

## External links

* Real Algebraic and Analytic Geometry Preprint Server
* Model Theory preprint server

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Real closed field. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Real_closed_field&oldid=4349526"
*[c.]: circa