A New Decision Method for Elementary Algebra
A. Seidenberg
STOR
The Annals of Mathematics, Second Series, Volume 60, Issue 2 (Sep., 1954), 365-374.
Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available at
http://uk.jstor.org/about/terms.html. JSTOR's Terms and Conditions of Use provides, in part, that unless you have
obtained prior permission, you may not download an entire issue of a journal or multiple copies of articles, and you
may use content in the JSTOR archive only for your personal, non-commercial use.
Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or
printed page of such transmission.
The Annals of Mathematics is published by The Annals of Mathematics. Please contact the publisher for further
permissions regarding the use of this work. Publisher contact information may be obtained at
http://uk.jstor.org/joumals/annals.html.
The Annals of Mathematics
©1954 The Annals of Mathematics
JSTOR and the JSTOR logo are trademarks of JSTOR, and are Registered in the U.S. Patent and Trademark Office.
For more information on JSTOR contactjstor@mimas.ac.uk.
©2001 JSTOR
http://uk.j stor.org/
SatNov 3 18:08:20 2001

Алнльв of Mathematics
VoL. 60, No. 1, September, 185$
Printed in U.S.A.
A NEW DECISION METHOD FOR ELEMENTARY ALGEBRA
By A. SEIDENBERa
(Received December 29, 1952}
Introduction
A. Tarski [4] has given a decision method for elementary algebra. In essence
this comes to giving an algorithm for deciding whether a given finite set of
polynomial inequalities has a solution. Below we offer another proof of this
result of Tarski. The main point of our proof is accomplished upon showing
how to decide whether a given polynomial f(z, y) in two variables, defined over
the field R of rational numbers, has a zero in a real-closed field К containing R.1
This is done in §2, but for purposes of induction it is necessary to consider also
the case that the coefficients of f(x, y) involve parameters; the remarks in §3
will be found sufficient for this point. In §1, the problem is reduced to a decision
for equalities, but an induction (on the number of unknowns) could not possibly
be carried out on equalities alone; we consider a simultaneous system consisting
of one equality f(x, y) = 0 and one inequality F(x) ^ 0. Once the decision for
this case is achieved, at least as in §3, the induction is immediate.
Entering into our considerations are the field R of rational numbers and an
arbitrary real-closed field К: the argument proceeds uniformly for all K. Because
of this, one gets for real-closed fields a principle analogous to the so-called
"PrineipLe of Lefschetz." This principle asserts that results of a certain kind—
the kind occurring, for example, in A. Weil's Foundations of Algebraic Geometry
(see [6; pp. 242-245])—which are true for the field of eompLex numbers auto-
automatically hold also for an arbitrary algebraicaLly closed field of characteristic 0.
The corresponding principle for real-closed fields, which we may call the "Prin-
"Principle of Tarski," says that any sentence of elementary algebra which holds in
one real-closed fieLd also holds in every real-closed field. In particular it is true
that any polynomiaL f(x\, • ¦ ¦ , xn) * K[xi, ¦ • ¦ , xn], К a real-closed fieLd, has
on any /i-dimensional closed interval a maximum and a minimum. In §6(b) we
illustrate the principle by showing that if an algebraic variety defined over a
real-closed field carries any points with coordinates in K, then it also carries
one such point which is nearest to the origin.
Our proof may have some bearing on the actual construction of a decision
machine. Some remarks on this point are made in §S(e).
Thanks are due to Professor Tarski for valuable comments on the paper.
1. Reduction to equalities
By a set of inequalities of the first kind we shall mean a set of (simultaneous)
polynomial inequalities of the form:
/l(.El , ¦ - - , Xn) > 0, • ¦ ¦ , MXi , ¦ • ¦ , 1.) > 0,
fr+i(xi, ¦ • • , жл) = 0 , ¦ • ¦ , fs(xi, ¦¦¦ , хл) = 0,
1 For the definition and basic properties of real-closed fields see [1] or [S].
365

366 Л. SEIDENBERO
where the /, are elements of the polynomial ring K[xi, ¦ ¦ ¦ , xn] and К is a, real-
closed field. Any given set of inequalities, written also with the signs ^ 0, < 0,
й 0, ё 0, can clearly be rewritten with these signs eliminated in favor of the
signs > 0 and = 0. Thus the question whether a given finite set of polynomial
inequalities has a solution (in K) can be transformed into the question whether
at least one of a finite number of sets of inequalities of the first kind has a solu-
solution. Moreover the sign > 0 can also be eliminated, as the condition / > 0 is
equivalent with the condition zj — 1 for some z. We thus need deal only with
equalities. The set of equalities gy = 0, ¦ ¦ ¦ , g,, = 0 can be replaced by the
¦single equality ^g\ — 0; and the disjunction of a finite number of sets of the
first kind, equivalent respectively to hy — 0, ¦ • ¦ , ht - 0, can be replaced by
irki = 0.
2. The decision for a plane curve
The problem then is to decide whether a given hypersurface f(xi, • ¦ ¦ , xn) = 0
has on it a point with coordinates in K. Consider first the case of a plane curve
j(x, y) — 0. The polynomial f(x, y), which we are assuming is not a constant,
may have multiple factors, but if so this can be detected by Euclid's algorithm,
and we may compute a polynomial g(x, y) having no multiple factors and such
that g(x, y) = 0 if and only if f(x, y) =0: in short, we may assume f(x, y) to be
free of multiple factors. If now there is any real point, i.e., point with coordinates
in K, on f(x, y) = 0, then there is also on it a real point which is nearest the
point (a, 0), a «K. This is immediate for К = the field of real numbers, and we
will prove it in a moment, in Lemma 1, for an arbitrary real-closed field K.
If P is some such nearest point, if P is not the point (a, 0), and if P is simple
for f(x, y) = 0, then the tangent at P bof(z, y) = 0 coincides with the tangent
at P to the circle through P having (a, 0) as center: this follows immediately
from Lemma 2 below. Thus P lies on (x — a) df/dy - ydf/дх = 0; and the
same conclusion holds if P is singular on f(x, y) - 0 or is the point (a, 0). Thus
there are real points on f(x, y) — 0 if and only if there is a real point in the
intersection of the curves f(x, y) = 0 and gjx, y) = 0, where ga —
(x — a)df/dy — ydj/дх. The intersection of the curves / = 0 and ga = 0, con-
considered as sets of points with coordinates in K(\/— l), will be finite unless
1 By a "computation" we mean one involving only the operations of addition, multiplica-
multiplication, subtraction, and division. Whenever we speak of a computation, we refer strictly
speaking to one over the rational number field R. If we assume in an informal way that we
know how to compute with elements of a formally-real field, then we could take for R more
generally an arbitrary formally-real field (and for К an arbitrary real-closed field con-
containing R). But such an assumption does not correspond to the facts, and to be exact one
would have to reformulate our statements, giving up the idea of decision, and merely
assert existence. Whenever in §2 (and similarly elsewhere) it is definitely a question of
decision, we suppose/(z, y) t R[x, y], R = the field of rational numbers, and we take for
a, tn, c, etc., rational values. We need the results, however, more generally, and then only
suppose/(x, y) t K[r., у], К — a real-closed field, and a, m, c, etc., may range over K.

NEW DECISION METHOD FOR ELEMENTARY ALGEBRA 367
/ = 0 and <]& = 0 have a common component; or, in other words, unless f(z, y)
and дл(х, у) have a common factor (of positive degree). Such a factor would in
any event also have to be of positive degree in y, for a factor p(x) of f(z, y) in
also a factor of df/dy but not of ydf/dx. Moreover / and ga can have a common
factor for at most n values of a, where n = degree of f(x, y). In fact, if this
happened more than n times, then for two of the values of л, say av, a^, the
polynomials /, gai , ga^ would have a common factor. This leads at once to the
conclusion that /, df/dy and ydf/dx have a common factor, and this is a contra-
contradiction. The polynomials/ and </a have a common factor of positive degree in у
if and only if Ra(x), the resultant of/ and ga with respect to y, is zero. We com-
compute Ra(x) for a = 0, 1, ¦••,«¦, and find that at least once RJ^z) is riot zero.
Thus we may assume that the intersection S of / = 0 and go — 0 contains only
a finite number of points, and it remains to see whether one of these is real.
To do this, we project jS onto the ж-axis. Arranging the axes so that degree
f(z, y) In у is n, the resultant Ra(z) gives the abscissae of these points. Some
of these may be real even if there are no real points in S; in fact, through every
non-real point goes one and only one real line. We therefore project S onto the
x-axis by parallel projections in nx + 1 different (real) directions—there are at
most n2 points in S—and S contains a real point if and only if each of the pro-
projected sets contains a real point. Whether a given collinear set of points, given
by a polynomial equation P(x) - 0, contains a real point can be decided by
Sturm's Theorem.3 Thus it is always possible to decide in a finite number of
steps, whether/(x, у) = О carries a real point.
3. Further remarks for the case of a plane curve
Instead of projecting n2 + 1 times, we can proceed as follows. Let Ra(x) by
the resultant of fix, y) and g<,(x, y) with respect to у and let Q(y) be the resultant
with respect to x. The polynomiaL йо(х) may have multiple factors, but we can
compute a polynomial R(z) having the roots of йо(х), but only simply. Let
(a,/3) be a non-real point of S, a. — a + a'\/~ 1,0 — b + b'\/~l,a,a',b, h' t K.
The real line through (a,fl) must also pass through (a, 0), where a = a — a'\/ — l,
fi = b — b'\/~l. If a — a, then the line is vertical; otherwise it has slope
(fi — 0)/(ot — a). Form, then, all linear polynomials m. — @i — /33)/(ai — on)
for all pairs of roots on , <*3 of Й and & , 0г of Q, and take their product. This
gives a monic polynomial p(m) = m' + Cims~y + ¦ ¦ - + cs«K[m], which we
can compute, and which will have (J3 — $)/(а — 5>) as a root (m the case a y± a).
We can also compute a monic polynomial giving the slopes m of lines у — mx
meeting/(ж, у) = 0 at infinity. (If f(x, у) = /»(ж, у) + fn-y(z, у) + • ¦ ¦ , then
/n(l, »i), though not necessarily monic, gives these slopes.) To save notation,
we suppose this polynomial incorporated into p(m) as a factor. We now project S
onto the ж-axis by a parallel projection of slope differing from the slopes of the
real lines through the non-real points of S and the slopes of lines meeting
1 For Sturm's Theorem see [5].

368
A. SEIDENBERG
f(x, y) = 0 at Infinity. No real root of p(m) is as great or greater than 1 + X)l c* [,
so we may project at the slope 1 + Yi\ c« I- We note for later purposes that
1- + с? > \d \, so that we could also project at the slope m = 1 + ^A + cj).
If P{x) = 0 gives the points of the projected set, then S contains a real point if
and only if P(x) = 0 has a real root.
Let Fix) tK[x], F(x) ^ 0, and consider now the question of deciding whether
there is on f(x, y) = 0 a real point subject to the condition Fix) И 0. To decide
this, we first free fix, у) = О of any component it may have in common with
F{x) = 0, namely by dividing f(x, y) by the greatest common divisor of F(x)
and the coefficients of fix, y) regarded as a polynomial in y. We may assume,
then, that fix, y) = 0 and Fix) = 0 have no common component. We want
now to assume that Fix) = 0 and fix, y) = 0 do not meet on у = 0; this can
be done by taking as new z-axis the line у — с, where с is greater than any real
root of the resultant of F(x) and f(x, y) with respect to x. (Also here, as in the
last paragraph, we can take for с an expression rational in the coefficients of
Fix) and fix, у).)' We may assume, then, that Fix) = 0 and fix, у) = О do
not meet on у = 0. Let now ДО, у') = /{ж, у'Fix)). Then ^(ж, у') = 0 has no
point in common with F(x) = 0. Any point (x, y) an fix, y) = 0 not on F(x) = 0
yields a point (x, y/F(x)) onfiix, y') = 0; and conversely, any point (x, y') on
/ife y') = 0 yields a point (x, y'Fix)) on/(x, j/) = 0. It thus remains to decide
whether f^x, y') = 0 has a real solution.
4. The general case
By a set of inequalities of the. second kind we shall mean a set of (simultaneous)
polynomial inequalities of the form:
Afe , ¦ - ¦ , хл) ^ 0, ¦ • ¦ , ft(xy, ¦ ¦ ¦ , xn) ^ 0,
fr+iixy, - ¦ - , xn) = 0, • ¦ ¦ , f.ixi, - • ¦ , xn) = 0.
Theorem I. Lei /(aL, - • • , am ; x, y) be an element of the polynomial ring
R{a.\., ¦•• , am ; ж, у], «Жеге Д is the field, of rational numbers; and let
Fia-i, ¦ ¦ • , am ; x) t R{ai, ¦ ¦ ¦ , am ; x]. Then there exist a finite number of poly-
polynomials Gi(a-i ,•¦•¦, o-n) * R[a-i , ¦ ' ¦ , a-m], i = I) - ¦ ' , s, and an equal number
of polynomials дг(ау, ¦ ¦ ¦ , am, ; x) t R[ai, ¦ ¦ ¦ , am ; x] such thai for any real-
closed field К and any values a,- of the a, in K, the equation f(di, ¦•¦ ,am\x,y) — 0
has a solution in К subject to the condition Fidi, ¦ ¦ ¦ , am ; x) И 0 if and only
if for at least one i, i = 1, • ¦ • , s, (?;(di, ¦ ¦ ¦ , d™) И 0 and ^(dt, - ¦ ¦ , dm ; x) = 0
has a solution in K. One can compute ike G, and gi within a finite number N of
steps, where N depends only on the degrees off and F in x and. y.
Proof. We proceed as above in the case without the parameters a, , except
4 Likewise, instead of computing Д„(ж) for n + 1. values of a, we can compute directly
an appropriate value of * as a rational expression in the coefficients of /Or, y). Namely,
fta(i) can be computed with a indeterminate, and then a value of a computed for which at
least one of the coefficients will not be zero. Below, in Theorem 1, we suppose m. and с
computed as above. Although it is not strictly necessary, we also suppose, for convenience
of exposition, that a is computed as here indicated.

NEW DECISION METHOD FOR ELEMENTARY ALGEBRA 369
that here the algorithm splits into cases according to whether certain polynomials
are, for special values of the at, zero or not. For example, in dividing a polynomial
P (o-i, ¦¦¦ , o-n ; x, y), regarded as a polynomial in y, by a polynomial
Q(a,i, ¦ • ¦ , am ; x, y) similarly regarded, the algorithm varies according to
whether, for special values of the aL, the leading coefficient Qu(at, ¦ ¦ ¦ , am ; x)
of Q is zero or not, i.e., according to whether the sum of the squares of the co-
coefficients of Qa(x) is zero or not. Moreover this (i.e., the vanishing of a leading
coefficient) is the only type of variation that occurs (see footnote*), and since
with the vanishing of a leading coefficient the degree of the polynomial involved
became reduced, it is clear that altogether there are only a finite number of
alternatives. In this way we obtain a finite number of sets of inequalities of the
second kind such that for any di e K, f(di, ¦ ¦ ¦ , dm ; x, y) = 0 has a solution in
К subject to the condition F(dt, ¦ - ¦ , dm ; x) j? 0 if and only if at least one of
the sets of inequalities has, for the given a,,, a solution in K: the inequalities
here are all of the form G(ai, ¦ - ¦ , am) j*- 0—and the simultaneous inequalities
G И О, Я И 0 can be replaced by GH ^ 0; the equalities are all of the form
g(ay, ¦ ¦ • , am ; x) = 0, where g may be of degree 0 in x—and here the simul-
simultaneous equalities g = 0, h = 0 (at most one of which is of positive degree in x)
can be replaced by g~ + k~ = 0. This completes the proof.—The remark in the
previous section about projecting S only once instead of nl + 1 times is here of
importance, as each set of inequalities is to contain only one polynomial gt in x.
Theorem 2. Let /(a, , • ¦ • , am ; Xi, ¦ ¦ ¦ , хл) t R[a.i, ¦ ¦ ¦ , a» ; xy , • ¦ • , хя\,
where R is the field of rational numbers. Then there exist a finite number of poly-
polynomials Gi(ay, ¦ ¦ ¦ , am) e R[a,i, ¦ ¦ ¦ , a,], i — 1, ¦ • - , s, and. an equal number
of polynomials gc(ai, ¦ - ¦ , am ; x) t R[ay, ¦ • • , am ; x] such that for any real-
closed field К and any values di of the ai in К, the equation
f(d!, ¦ ¦ ¦ , dm ; X! , ¦ ¦ ¦ , xn) = 0
has a solution in К if and only if for at least one i,i = 1, • ¦ • , s, Gi(di, ¦ - - , <?„) ^ 0
and дг(а,1, • • • , dm ; x) — 0 has a solution in K. One can compute the Gi and gi
within a finite number N of steps, where N depends only on n and the degree of f
in the Xi .
Proof. The theorem is trivial for n — 0 and n = 1; and for n = 2 is a special
case of Theorem 1. Suppose, then, n > 2 and the theorem known for n — 1
variables xt. We regard xt &s & parameter and conclude the existence of poly-
polynomials Fi(oi, • ¦ ¦ ,a» ;xi),/i(ai, - ¦ ¦ , am ; Xi, y), i = 1, • ¦ - , s, with coefficients
in R, such that for any й, е К and Xi t K, f(dy, ¦ ¦ ¦ , dm ; xv, x-L, ¦ ¦ ¦ , xn) = 0
has a solution in К if and only if for some i, i - 1, • ¦ • , s, f\(di, ¦ ¦ ¦ , ая ; *i) ^ 0
and fi(di, ¦ - ¦ , dm ; Xi, y) = 0 has a solution in K. It follows that for any
<u e K, f(di, - ¦ - , dm ; Xi, ¦ ¦ • , xn) — 0 has a solution in К if and only if for
some i, i = 1, ¦ ¦ - , s, /;(<Ji, ¦ • ¦ , dm ; xx, y) =0 has a solution in К subject
to the condition Fi(di, ¦ - - , dm ; xi) ^ 0. Theorem 1, in turn, yields polynomials
Ga(ai, • ¦ ¦ , am), вц(а.1, ¦ • ¦ , am ; x) such that for any di t K,
fi(di, ¦ ¦ ¦ , am ; xr, y) = 0

370 A. SEIDENBERG
has a solution in К subject to the condition Fi(di, ¦ ¦ ¦ , dm ; xi) И 0 if and only
if for some j, О„(ал , ¦ ¦ ¦ , dm) И 0 and ?;j(di, ¦ ¦ ¦ , dm ; x) =0 has a solution
in K. Thus the polynomials Gij, дц are polynomials of the type required by the
theorem. The F,- and /i can be computed, by induction, and then the Gij and g*;,-
can be computed, by Theorem I. This completes the proof.
Applying Sturm's Theorem to the polynomials g,j, we get the following
(the generalized Sturm's Theorem).
Theorem 3. Let F be any finite set of (simultaneous) polynomial equations and
inequalities with the unknowns Xi, ¦ • ¦ , хл and the parameters a,i, ¦ ¦ ¦ , am, where
all the polynomials in question are in R[ai, ¦ ¦ ¦ , am ; X\, - ¦ ¦ , xn[, R = the field
of rational numbers. One can then construct (in a finite number of st-eps) sets
*n , • ¦ ¦ , Gs of polynomial equations and inequalities, involving only the parameters
a\, ¦ • ¦ , dm,, such that for any real-dosed field К and any values di of the at in K,
the following two statements are equivalent:
(a) F has at least one solution with Xi € K,
(b) for at least one i, i = 1, • • • , s, all the equations and inequalities of Gi are
satisfied (by di, ¦ - • , dm).
We will briefly indicate how to get Tarski's full result on elementary algebra
from the above. By an atomic formula we mean an expression of the form / > 0
or / = 0, where / is a polynomial with rational coefficients. By a formula we
mean an expression built up in a finite number of steps from atomic formulae
by means of conjunction, disjunction, negation, and quantifiers of the form (Ex),
"there exists an x suck that" where x ranges over a real-closed field. (We could
allow all the signs of inequality and other logical notations such as implication,
and the quantifier "for all x" to enter into the definitions, but we suppose these
eliminated in terms of the others for present purposes.) An elementary sentence
is a formula involving no parameters (free variables). One sees easily that any
formula involving no quantifiers can be rewritten equivalently as a disjunction
of conjunctions of atomic formulae. If such a formula is prefixed by a quantifier
(Ex), then we have shown how to eliminate that quantifier. More generally,
in any formula involving quantifiers, there occurs a formula (Вх)ф(х), where
ф(х) is a formula involving no quantifiers. Eliminating the quantifier here and
applying induction on the number of quantifiers, we can eliminate all the
quantifiers from any formula. In particular, the decision for any sentence can be
reduced to the verification of equations and inequalities involving only rational
numbers (and no variables).
6. The two lemmas
There remain two lemmas to be proved. Both may be regarded as well-known,
in fact, they follow immediately, as we shall indicate, from the decision method
itself; but, of course, we cannot take advantage of that fact at this point.
Lemma 1. Let f(x, y) t K[x, y], where К is a real-closed field. If f(x, у) = О has
any solutions (x, y) in K, then it also has one such solution with rJ -\- y1 minimum.
Proof. We intersect f(x, y) = 0 with the circle x2 + i/ = <?, ct K, and ask

NEW DECISION METHOD FOR ELEMENTARY ALGEBRA 371
for which с, с S 0, there is a real intersection. Let g{x, c) be the resultant of
fix, y) and ж2 + \f — c2, so that the roots of g(x, с) = О give the abscissae of
the intersection of the two curves (as point-sets with coordinates mK(^\/— l)).
The real intersections correspond to the real solutions x of g(x, c) — 0 such that
— с ^ x ? c. We apply Sturm's Theorem to decide whether there is a real
solution x to g(x, c) = 0 with — с ? ? ? e; Sturm's Theorem gives us the result
that the set of inequalities \g(x, c) = 0, — с ? z ^ c\ is equivalent with the
disjunction of a finite number of sets of inequalities of the first kind in which
the polynomials involved are all in К [с] (we are here thinking of с as a parameter).
As a consequence, the desired с fill up a finite number of intervals on the c-axis,
open, closed, half-open, possibly extending to +=°, or possibly consisting of a
single point. We claim further that these intervals are all closed. To prove this
we show that if g(x, y) does not vanish on the segment у — c, — с ^ x ^ c,
then there exists a rectangle, with sides parallel to the axes and containing the
segment, on which g(x, y) does not vanish. Let
g(x, y) = ай(х) + а^х)(у — с) + ¦ • • + am(x)(y — c)m.
Since ct<i(x) does not vanish for — с ^ x ^ c, it also does not vanish for some
interval — с' й х ^ с', where с < с'. It is known that | oq(x) j, under such
circumstances, has a positive lower bound; Let b be such a bound. It is also
known that the | а,-(ж) | are bounded above in — c' ^ x ^ c'; and let В be such
a bound, for all the а,-(ж). Then
g(x, y)
^ Ь- \<ъ(х)(у-с) + ••¦ +а„(х)(ц -с)л\*Ъ-2В-\у-с\> b/2,
it \ у — с | < j, \ у — c\ < b/iB and —c' ? x ? c'.
Lemma 2. Let f(x, y) t K[x, y\, where К is a real-closed field, let P be a simple
point of fix, if) = 0, and let (x — a'f ¦+¦ (y — &)' = r~, a, b, r e K, be a circle
passing through P. If the tangent to f(x, y) = 0 at P enters the circle, then so does
the curve f(x, y) — 0 itself. {All the. points invobed in this statement are understood
to have coordinates in K.)
Proof. We may take P as origin of coordinates and the tangent at P to
fix, y) = 0 as ж-axis: we then have a ^ 0. Within a constant factor we may
write fix, y) = 2/A + hix, y)) + xk(c + g(x)), where g(x), hix, y) t K[x, y\,
g@) = 0, h@, 0) = 0, к i 2, and except in trivial cases, с И 0. In a sufficiently
small rectangle — s g x й s, — t й у ^ t, the function 1 + h(x, y) will lie be-
between \ and I and с + ^(ж) will lie between c/2 and Zc/2. For sufficiently small
ж*, then,/(a:ii, t) and f(xn, —t) will have opposite signs, so f(xt, , y) will vanish
somewhere on — ( % у ^ t, say at y$ ; we take х$ such that — ^ = ^d = s. Then
a'~ + b1 — 2ax0 + xt(l + 6 | Ьсхъ~2 \ + 9c1 xf^), which is less than a1 + b5 for
all sufficiently small xa for which axo > 0. This completes the proof.

372 A. SEIDENBEEG
6. Additional remarks
(а) Originally we had an idea for a proof which is practically immediate if К
is the field of real numbers and which in any event makes the reason for the
truth of the decision method especially clear. Instead of asking whether a
hypersurface f(xi, ¦ ¦ ¦ , xn) = 0 carries a real point, we ask whether a variety V
given by /iOi, ¦•¦ , xn) = 0, • ¦ ¦ , ft(xi, ¦¦ ¦ , xn) = 0 carries one. It does,
obviously in the case К is the field of real numbers, if and only if there is on V
a real point nearest the origin. Arranging matters so that the origin is not the
center of any sphere containing a component of V of positive dimension, the
minimum condition stated determines a subvariety Va of V, of dimension
less than the dimension of V if V is of positive dimension, such that V carries a
real point if and only if Va does. In this way it comes to deciding whether a
0-dimensional variety contains a real point: after appropriate projections one
has that the ambient space is 1-dimensional, and then Sturm's Theorem is
applicable.
(б) Also for an arbitrary real-closed field К one could carry out a proof along
the above lines, after proving generalizations of Lemmas 1 and 2. The technical
difficulties may make some other proof preferable, but there is no doubt that the
appropriate generalizations are true. As Professor Tarski has several times
emphasized, one consequence of a decision method based solely on the axioms
for real-closed fields is that any statement of elementary algebra which is true for
one real-closed field is true for all real-closed fields. In applications, one has to
consider whether the statement is, or can be converted into, an elementary one,
and whether the statement is true for some real-closed field, say the real field.
As an illustration, let us consider the generalization of Lemma 1, that if there
is on a variety V defined over a real-closed field К any point with coordinates in K,
then there is also one such point nearest to the origin. If the variety is given by
h = 0, • ¦ ¦ , fr = 0, we may deal simply with the hypersurface / = 0, where
/ = S/i ¦ The coefficients of / are in K, but we replace them by parameters
a,, so that we have a polynomial
f(at , ¦ • ¦ , an ; Xi , ¦ ¦ - , х„) t R[a,i , - ¦ - , am ; xi , ¦ ¦ ¦ , ?„],
where R is the field of rational numbers. We are now asserting that for any a<_ e
K, either f(at, • ¦ • , am ; Xi, ¦ - ¦ , xn) ^ Q for all хг t К or there exist Xi t К
such that /(ui , - • • , am ; Xi, ¦ - ¦ , xa) = 0 and if z% t К and /(aL, ¦ ¦ - , am ;
3i! ¦ ¦' i 2Л) =0 then ~^,z\ ^ X^i ¦ This is an elementary sentence. It is not
difficult to reformulate this statement as an assertion that a certain polynomial
h(a\, • ¦ • , am , am+i, ¦ • ¦ , an+s)
has no zero in K. Using this remark and Theorem 3 or the remarks directly
following Theorem 3, one sees that the statement is either true for all real-
closed fields or false for all such fields. Since the theorem is true over the real
numbers, it is true for any real-closed field. —The generalization of Lemma 1 is
trivial for the real field, the generalization of Lemma 2 not so trivial, even for

NEW DECISION METHOD FOB ELEMENTARY ALGEBRA 373
the real field. Supposing it well-known however, for the real field, it follows at
once for an arbitrary real-closed field.
(c) The decision problem for algebraically closed fields (of given characteristic p)
is concerned, of course, only with sets of inequalities of the second kind. Con-
Consider a finite set of polynomial equalities and Inequalities In a single variable:
Л = 0, ¦¦• ,/r = О, Л+1 ^0, •¦-,/. ?*0.
We may suppose, trivially, that 0 < r < s and that the/, are of positive degree.
The Inequalities may be replaced by a single inequality, namely by taking the
product. Also the equalities can be replaced by a single equality, namely by
taking the greatest common divisor. We may suppose, then, that r = 1, s =2;
also that /l and /г are of positive degree. It Is then a question of seeing whether
/2ей/' is divisible by /i. The general case is now taken care of by considering
all the unknowns but one as parameters.6
(d) There is a close relation between the decision problem for algebraically
closed fields of given characteristic, Hilbert's Nullstellanaatz, and an algorithm
for deciding whether the element 1 is in the polynomial ideal with given basis
Л , ¦' ¦ , /. —such an algorithm has been given by G. Hermann [3]. In the de-
decision problem, given a simultaneous set of polynomial equalities and inequalities
of the form / = 0 and g ^ 0, we can eliminate the inequalities, as the condition
g ^ 0 is equivalent with the condition zg — 1 for some z: the question whether
the original set has a solution is thus reduced to the question whether a certain
set /l , ¦ • ¦ , /s of polynomials has a common zero, and this in view of Hilbert's
Nullstellensatz is equivalent with the condition 1 e (fy, • ¦ ¦ , /,). Thus Her-
Hermann's algorithm (or resultant theory) may be used to dispose of the decision
problem (in a less trivial way than already indicated). Second, if we have a
decision method for algebraically closed fields of given characteristic, then the
question whether 1 * (/i, - ¦ ¦ , Л) can be decided by deciding whether Л ,¦¦•,/,
have a common zero. Third, without making use of Hilbert's Nullstellensatz,
Hermann has shown how to compute an integer JV in terms of s, the degrees of
the/;, and the number of variables, such that if 1 t (/t, - ¦ ¦ , fs), then there exist
polynomials A,- of degree at most N such that 1 = Ai/i + - ¦ ¦ + AJC. Using this
result, Hilbert's Nullstellensatz (applied to polynomials of given limited degree)
can be rewritten as an elementary sentence, so that its truth for one algebraically
closed field of characteristic p implies its truth for all others. (I see no way of
applying Lefschetz' principle to Hilbert's Nullstellensatz directly, without the
intervention of some other result, such as Hermann's algorithm; but the Null-
Nullstellensatz itself can be proved very simply using the above ideas. In fact, after
a simple and well-known reformulation, the Nullstellensatz reads: If (Ji, • ¦ • , /,)
has any zeros, then it has an algebraic zero. In defining elementary sentence,
we take as coefficient field any subfield Д of К which contains the coefficients of
5 This practically trivial decision method for algebraically closed fields of given char-
characteristic was pointed out to me by Professor Tarski.

374 A. SKIDENBEHG
the fi, and let the variables range over any algebraically closed field K* con-
containing R. The question of decision is out, but it is still clear that any elementary
sentence which is true for one K* is true for all others. The Nullstellensatz
follows immediately.)
(e) Tarski's original decision method is somewhat different from ours in that
he considers first equations and inequalities in a single variable, coming to a
decision in this ease by generalizing the argument used in proving Sturm's
Theorem. The case of several variables then follows by considering all but one
of the variables as parameters.* One objective advantage of our proof over
Tarski's is that the main points are theorems concerning sets of inequalities of
the second kind only, those of the first kind entering explicitly only at the very
end. One might say that in our method Sturm's Theorem is used only to eliminate
the last variable, whereas in Tarski's, Sturm's Theorem is used to eliminate each
variable. This fact might well have some bearing on the construction of a de-
decision machine. Whether such a machine could, from the engineer's standpoint,
actually be built would depend on the efficiency of the decision method pro-
proposed, of which the number of steps involved would be some measure. A machine,
however, might in some circumstances compress into a single step what in other
circumstances might have to be regarded as several steps. In particular this
might be the case for deciding whether a given polynomial with rational coef-
coefficients in a single variable has a real root. With my method, any way of de-
deciding this, Sturm's method or any other, could be used, whereas that is not the
case with Tarski's method, as the argumentation of Sturm's Theorem permeates
the whole method. As neither Tarski nor I have computed numbers of steps
involved, nothing very definite can be asserted, but the actual construction of
a decision machine might well have to await improvements in theory of a type
occurring in this paper.
University of California
REFERENCES
1. E. Artin and 0, ScHRBrER, Algebraiscke Konstruzlion reeler Korper, Ahh. Math. Sem.
Hamburgischen Univ., vol. 5 A926) pp. 83-115.
2. G. Hehmann, Die Frage der endlich uielen Schritte in der Theorie der PolynamideaU,
Math. Ann., vol. 95 A926) pp. 736-788.
3. В, E. Meserve, Inequalities of higher degree in. one unknown, Amer. J. Math., vol. 49
A947) pp. 357-370.
4. A. Tarski:, A decision method for elementary algebra, and geometry, Prepared for publioa-
cation by J. С. С. McKinsey. Berkeley, 1951.
5. B. L. van deb Waerden, Modern Algebra, vol. 1, New York, 1949.
6. A. Weil, Foundations of Algebraic Geometry, Amer. Math. Soc. Colloquium Publica-
Publications, Volume XXIX, New York, 1946.
< В. Е. Meserve [31 lias given a decision method for systems of inequalities in a single
variable of the form/i > 0, ¦ • ¦ ,/, > 0. On the basis of what he has done, it is also possible,
with a few additional remarks, to give a decision method for systems of the form/a = 0,
/i > 0, ¦ - ¦ , /, > 0, and thus get still another decision method for elementary algebra.