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].
- Theorem proving for and with Gröbner bases theory
- scientific article; zbMATH DE number 4112737
- Gröbner bases and systems theory
- Homotopy-initial algebras in type theory
- The theory of Gröbner bases
- Towards Constructive Homological Algebra in Type Theory
- Type theory and homotopy
- Homotopy type theory and Voevodsky's univalent foundations
- scientific article; zbMATH DE number 1302059
- Homotopy type theory
- A verified common lisp implementation of Buchberger's algorithm in ACL2
- Standard bases for general coefficient rings and a new constructive proof of Hilbert's basis theorem
- Strongly Noetherian rings and constructive ideal theory
- A universal Krull-Lindenbaum theorem
- Homotopy type theory and Voevodsky's univalent foundations
- Noetherian orders
- scientific article; zbMATH DE number 5994829 (Why is no real title available?)
- Galois Connections for Recursive Types
- Lindenbaum's lemma via open induction
- A formal proof of Dickson's lemma in ACL2
- scientific article; zbMATH DE number 1163435 (Why is no real title available?)
- Syntax for semantics: Krull's maximal ideal theorem
- Higher-Order Tarski Grothendieck as a Foundation for Formal Proof.
- Commutative algebra in the Mizar system
- Admissible ordering on monomials is well-founded: a constructive proof
- A constructive picture of Noetherian conditions and well quasi-orders
- A general constructive form of Higman's lemma
- An iterative constructive Hilbert basis theorem
- On the Weihrauch degree of the additive Ramsey theorem
- Hilbert's tenth problem for term algebras with a substitution operator
- Complemented subsets and Boolean-valued, partial functions
- Defining long words succinctly in FO and MSO
- On the first-order parts of problems in the Weihrauch degrees
- Algorithmically random series
- Ideal presentations and numberings of some classes of effective quasi-Polish spaces
- Lower bounds on () and other properties of -register machines
- Reifying dynamical algebra: maximal ideals in countable rings, constructively
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)