In mathematics, a real closed field is a field F that has the same first-order properties as the field of real numbers. Some examples are the field of real numbers, the field of real algebraic numbers, and the field of hyperreal numbers.
A real closed field is a field F in which any of the following equivalent conditions are true:
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 [math]\displaystyle{ \mathbb{R}_\mathrm{alg} }[/math] 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 (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]\displaystyle{ \mathbb{Q}(\sqrt 2) }[/math] is the ring [math]\displaystyle{ \mathbb{R}_\mathrm{alg}\times \mathbb{R}_\mathrm{alg} }[/math] (the two copies correspond to the two orderings of [math]\displaystyle{ \mathbb{Q}(\sqrt 2) }[/math]). On the other hand, if [math]\displaystyle{ \mathbb{Q}(\sqrt 2) }[/math] is considered as an ordered subfield of [math]\displaystyle{ \mathbb{R} }[/math], its real closure is again the field [math]\displaystyle{ \mathbb{R}_\mathrm{alg} }[/math].
The first-order theory of real closed fields is the first-order theory whose primitive operations are addition and multiplication, primitive predicates are = and ≤, and axioms are those of a real closed field. More precisely, a first-order theory is roughly speaking, a theory where quantifiers apply only to elements (not to sets of elements). The axioms of a real closed field are those of an ordered field, plus the axiom asserting that every positive number has a square root, and the one asserting that all polynomials of odd degree have at least one root. Except for the latter, it is immediate to express them as first-order formulas. This is true also for the latter, if one consider it as an axiom schema, that is an infinite sequence of axioms, one for each (odd) degree.
Alfred Tarski proved (c. 1931) that the first-order theory of real closed fields is complete, and decidable. This means that there exists a general procedure that takes as input an assertion expressed in this theory and decides which of the assertion and its negation is true (complete means that either the assertion or its negation is true).
The Tarski–Seidenberg theorem extends this result to decidable quantifier elimination. That is, there is an algorithm that, given a formula of the first-order logic that 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. 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 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
where x and y represent respectively the set of eliminated variables, and the set of kept variables.
Tarski's original algorithm for quantifier elimination has nonelementary computational complexity, meaning that no tower
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
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 the 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 [math]\displaystyle{ 2^{2^{\Omega(n)}} }[/math] and length [math]\displaystyle{ 2^{2^{\Omega(n)}} }[/math], where [math]\displaystyle{ \Omega(n) }[/math] is the big Ω notation.
This shows that both the time complexity and the space complexity of quantifier elimination are intrinsically double exponential. However, better complexities are known for the decision problem: Ben-Or, Kozen, and Reif (1986) proved that the theory of real closed fields is decidable in exponential space, and therefore in double exponential time. Moreover, the parameter that appears in the second exponent is not the size of the formula, nor the number of variables (as with cylindrical algebraic decomposition), but the number of the quantifier changes (from [math]\displaystyle{ \exists }[/math] to [math]\displaystyle{ \forall }[/math] and vice versa) in the prenex normal form of the input formula.
For purely existential formulas, that is for formulas of the form
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 exstential formula with complexity of sk+1dO(k) arithmetic operations and polynomial space.
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.
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 fields. For example, any field of hyperreal numbers 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 size 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 [math]\displaystyle{ \aleph_0 }[/math].
We have therefore the following invariants defining the nature of a real closed field F:
To this we may add
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:
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 the continuum and having the η1 property are order isomorphic. This unique field Ϝ can be defined by means of an ultrapower, as [math]\displaystyle{ \mathbb{R}^{\mathbb{N}}/{\mathbf M} }[/math], where M is a maximal ideal not leading to a field order-isomorphic to [math]\displaystyle{ \mathbb{R} }[/math]. This is the most commonly used hyperreal number field in non-standard 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]\displaystyle{ \aleph_\beta }[/math] 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 [math]\displaystyle{ \mathbb{R}((G)) }[/math] of formal power series on a totally ordered abelian divisible group G that is an η1 group of cardinality [math]\displaystyle{ \aleph_1 }[/math] (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]\displaystyle{ \aleph_1 }[/math], Κ has cardinality [math]\displaystyle{ \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]\displaystyle{ \aleph_2 }[/math] instead of [math]\displaystyle{ \aleph_1 }[/math], cofinality [math]\displaystyle{ \aleph_1 }[/math] instead of [math]\displaystyle{ \aleph_0 }[/math], and weight [math]\displaystyle{ \aleph_1 }[/math] instead of [math]\displaystyle{ \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).
|1=
(help)
Original source: https://en.wikipedia.org/wiki/Real closed field.
Read more |