Gröbner bases in type theory

From MaRDI portal





This paper describes a development of the basic theory of Gröbner bases within the framework of constructive type theory with inductive definitions. Apart from a pleasant to read elementary introduction to Gröbner bases the main scientific contribution consists of constructive proofs of termination of the completion process leading to a Gröbner basis and of Hilbert's basis theorem (polynomial rings over Noetherian coefficient rings are Noetherian). These constructive proofs which of course crucially rely on inductive definitions are surprisingly natural and one gets the impression that the wide-spread use of nonconstructive methods might be more a matter of education than of actual mathematical necessity. The core of the work is a constructive proof of Dickson's lemma: a relation \(R\) on some set \(A\) is ``well if for any infinite sequence \((a_i)_i\) there exist \(i<j\) with \(a_i Ra_j\). Dickson's lemma asserts that the relation \(\leq^m\) on \({\mathbf N}^m\) defined by \(\vec x \leq^m\vec y\iff x_i\leq y_i\) for \(i=1,\dots, m\) is well. Equivalently, in any infinite sequence of monomials eventually a monomial will be a multiple of an earlier one. The usual direct proof of this by induction on \(m\) requires the use of excluded middle and the axiom of dependent choices in the form of a minimal bad sequence argument. In the present work the use of nonconstructive methods is elegantly circumvented by replacing the definition of well-ness with the following classically equivalent, but constructively stronger version: a finite sequence \((a_1,\dots,a_n)\) is \(R\)-good if \(a_iRa_j\) for some \(i<j\leq n\). A predicate \(P\) bars a finite sequence \(w\in A^*\) if either \(P(w)\) obtains or, inductively, if \(P\) bars all sequences \(wa\) for \(a\in A\). The relation \(R\) is constructively well if \(R\)-goodness bars the empty sequence. It follows (even constructively) that a constructively well sequence is well in the usual sense (induction on the definition of ``bars shows that if \(R\)-goodness bars \(w\) then every infinite sequence starting with \(w\) contains an upward comparison). The converse also holds but requires excluded middle and dependent choice. Now it is possible to prove in constructive logic by induction on \(m\) that the relations \(\leq^{m}\) are constructively well. Of course, this entails that \(\leq^m\) is well in the usual sense and hence the existence of Gröbner bases. The crux is that the constructive formulation of wellness provides for a stronger induction hypothesis which makes the argument go through constructively. The second part of the paper gives a constructive proof of Hilbert's basis theorem: if ring \(R\) is Noetherian (has no infinite properly ascending sequence of ideals) so is \(R[X]\). Again, a constructive proof becomes possible by replacing the usual definition of Noetherian with the following constructively stronger one. One defines a finite sequence of elements \(a_1,\dots,a_n\) of a ring \(R\) to be ``good if \(a_n\) is contained in the ideal generated by \(a_1,\dots,a_{n-1}\). A ring \(R\) is constructively Noetherian if the goodness predicate bars the empty sequence. Now one has a constructive proof that if \(R\) is constructively Noetherian so is \(R[X]\). Since any field \(k\) is trivially constructively Noetherian one obtains a constructive proof that \(k[X_1,\dots,X_n]\) is constructively Noetherian, hence Noetherian in the usual sense. All this is worked out in the necessary detail along with the required background. The paper concludes with formalisations of these proofs in Agda, a theorem prover based on constructive type theory with inductive definitions and pattern matching. For the entire collection see [Zbl 0929.00065].




Cited in
(27)


Describes a project that uses

Uses Software






This page was built for publication: Gröbner bases in type theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4944848)