21 - The Buchberger Algorithm as a Tool for Ideal Theory of Polynomial Rings in Constructive Mathematics

Summary

Introduction

One of the aims of Constructive Mathematics is to provide effective methods (algorithms) to compute objects whose existence is asserted by Classical Mathematics. Moreover, all proofs should be constructive, i.e., have an underlying effective content. E.g. the classical proof of the correctness of Buchberger algorithm, based on noetherianity, is non constructive : the closest consequence is that we know that the algorithm ends, but we don't know when.

In this paper we explain how the Buchberger algorithm can be used in order to give a constructive approach to the Hilbert basis theorem and more generally to the constructive content of ideal theory in polynomial rings over “discrete” fields.

Mines, Richman and Ruitenburg in 1988 ([5]) (following Richman [6] and Seidenberg [7]) attained this aim without using Buchberger algorithm and Gröbner bases, through a general theory of “coherent noetherian rings” with a constructive meaning of these words (see [5], chap. VIII, th. 1.5). Moreover, the results in [5] are more general than in our paper and the Seidenberg version gives a slightly different result. Here, we get the Richman version when dealing with a discrete field as coefficient ring (“discrete” means the equality is decidable in k).