In
mathematics, a real closed field is a
field ''F'' that has the same
first-order properties as the field of
real number
In mathematics, a real number is a number that can be used to measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...
s. Some examples are the field of real numbers, the field of real
algebraic numbers, and the field of
hyperreal numbers.
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 in the first-order language of fields is true in ''F''
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bi ...
it is true in the reals.
#There is a
total order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexiv ...
on ''F'' making it an
ordered field such that, in this ordering, every positive element of ''F'' has a
square root in ''F'' and any
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An ex ...
of
odd degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathemati ...
with
coefficient
In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves ...
s in ''F'' has at least one
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 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 ordered field.
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''
[Rajwade (1993) pp. 222–223] (note that every
ring homomorphism between real closed fields automatically is
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
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...
s is the field
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.
[Efrat (2006) p. 177]
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 In mathematics, a real closed ring (RCR) is a commutative ring ''A'' that is a subring of a product of real closed fields, which is closed under continuous semi-algebraic functions defined over the integers.
Examples of real closed rings
Since t ...
. For example, the real closure of the field
is the
ring (the two copies correspond to the two orderings of
). On the other hand, if
is considered as an ordered subfield
of
, its real closure is again the field
.
Decidability and quantifier elimination
The
language
Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of ...
of real closed fields
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,
, consists of the following:
* the
axiom
An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy o ...
s of
ordered fields;
* the axiom asserting that every positive number has a square root;
* for every odd number
, the axiom asserting that all polynomials of degree
have at least one root.
All of the above axioms can be expressed in
first-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quanti ...
(i.e.
quantification ranges only over elements of the field).
Tarski proved () that
is
complete, meaning that for any
-sentence, it can be proven either true or false from the above axioms. Furthermore,
is
decidable, meaning that there is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
to decide the truth or falsity of any such sentence.
The
Tarski–Seidenberg theorem extends this result to decidable
quantifier elimination. That is, there is an algorithm that, given any
-
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. 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 is a real closed field, a formula with free variables defines a subset of , the set of the points that satisfy the formula. Such a subset is called a
semialgebraic set. Given a subset of variables, the ''projection'' from to is the
function that maps every -tuple to the -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 is defined by
:
where and 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
The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, ...
, can provide undecidable theories; see
Richardson's theorem and
Decidability of first-order theories of the real numbers
In mathematical logic, a first-order language of the real numbers is the set of all well-formed sentences of first-order logic that involve universal and existential quantifiers and logical combinations of equalities and inequalities of expressi ...
.
Complexity of deciding 𝘛rcf
Tarski's original algorithm for
quantifier elimination has
nonelementary In computational complexity theory, a nonelementary problem is a problem that is not a member of the class ELEMENTARY. As a class it is sometimes denoted as NONELEMENTARY.
Examples of nonelementary problems that are nevertheless decidable include: ...
computational complexity, meaning that no tower
:
can bound the execution time of the algorithm if 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 is the total number of variables (free and bound), is the product of the degrees of the polynomials occurring in the formula, and is
big O notation.
Davenport and Heintz (1988) proved that this
worst-case complexity is nearly optimal for quantifier elimination by producing a family of formulas of length , with quantifiers, and involving polynomials of constant degree, such that any quantifier-free formula equivalent to must involve polynomials of degree
and length
, where
is
big Ω 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
Reif is a surname and given name. Notable people with the name include:
Surname
*Alberto Reif (1946–2012), Italian football player
*Arnold E. Reif (born 1924), American cancer researcher
*Chris Reif, American soccer player
*Christian Reif (bor ...
(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
:
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 arithmetic operations and
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
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
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
cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
of the smallest cofinal set, which is to say, the size of the smallest cardinality giving an unbounded sequence. For example,
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called '' cardinal ...
s are cofinal in the reals, and the cofinality of the reals is therefore
.
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
In the mathematical field of order theory, an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets (posets). Whenever two posets are order isomorphic, they can be cons ...
.
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
In set theory, the cardinality of the continuum is the cardinality or "size" of the set of real numbers \mathbb R, sometimes called the continuum. It is an infinite cardinal number and is denoted by \mathfrak c (lowercase fraktur "c") or , \ma ...
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
of
formal power series on a
totally ordered abelian
Abelian may refer to:
Mathematics Group theory
* Abelian group, a group in which the binary operation is commutative
** Category of abelian groups (Ab), has abelian groups as objects and group homomorphisms as morphisms
* Metabelian group, a grou ...
divisible group ''G'' that is an
''η''1 group of cardinality
.
''Ϝ'' 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
, ''Κ'' has cardinality
, 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
instead of
, cofinality
instead of
, and weight
instead of
, 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 numbers
* the
definable numbers
* the
real number
In mathematics, a real number is a number that can be used to measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...
s
*
superreal numbers
*
hyperreal numbers
* the
Puiseux series with real coefficients
* the
surreal numbers
Notes
References
*
* Basu, Saugata,
Richard Pollack, and
Marie-Françoise Roy (2003) "Algorithms in real algebraic geometry" in ''Algorithms and computation in mathematics''. Springer.
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.
*
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.
*
*
* 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.
*
*
*
*
Alfred Tarski
Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician ...
(1951) ''A Decision Method for Elementary Algebra and Geometry''. Univ. of California Press.
*
External links
{{Commons category
''Real Algebraic and Analytic Geometry Preprint Server''''Model Theory preprint server''
Field (mathematics)
Real algebraic geometry