[FOM] Groebner bases

[Stephen G Simpson]

Timothy Y. Chow writes:
 > What really is needed to prove that, say, Buchberger's algorithm for 
 > computing a Groebner basis always terminates, for rings of the kind that 
 > software packages like Magma or Macaulay know about?

The essential theorem on the existence of bases for ideals in
polynomial rings is the Hilbert Basis Theorem.  Because of its
somewhat nonconstructive nature, the Hilbert Basis Theorem has played
a considerable role in the development of f.o.m.  My paper

  Stephen G. Simpson, Ordinal numbers and the Hilbert Basis Theorem,
  Journal of Symbolic Logic, 53, 1988, pp. 961-974
    
includes a reverse mathematics study of the Hilbert Basis Theorem,
showing that it is equivalent over RCA_0 to the statement that
omega^omega is well ordered.  My proof of the Hilbert Basis Theorem
from this assumption involves the construction of a Groebner basis.

----

Name: Stephen G. Simpson

Professional Affiliation: Professor of Mathematics,
    Pennsylvania State University

Research Interests: foundations of mathematics, mathematical logic

Web: http://www.math.psu.edu/simpson/