Polynomial Reduction

Christoph Schwarzweller

University of Tuebingen

Summary.

We continue the formalization of [8] towards Gr\"obner Bases. In this article we introduce reduction of polynomials and prove its termination, its adequateness for ideal congruence as well as the translation lemma used later to show confluence of reduction.

MML Identifier: POLYRED

Contents (PDF format)

1. Preliminaries
2. More on Polynomials and Monomials
3. Multiplication of Polynomials with Bags
4. Orders on Polynomials
5. Polynomial Reduction
6. Polynomial Reduction Relation

Bibliography

[1] Jonathan Backer, Piotr Rudnicki, and Christoph Schwarzweller. Ring ideals. Journal of Formalized Mathematics, 12, 2000.

[2] Grzegorz Bancerek. Cardinal numbers. Journal of Formalized Mathematics, 1, 1989.

[3] Grzegorz Bancerek. The fundamental properties of natural numbers. Journal of Formalized Mathematics, 1, 1989.

[4] Grzegorz Bancerek. The ordinal numbers. Journal of Formalized Mathematics, 1, 1989.

[5] Grzegorz Bancerek. Reduction relations. Journal of Formalized Mathematics, 7, 1995.

[6] Grzegorz Bancerek. Directed sets, nets, ideals, filters, and maps. Journal of Formalized Mathematics, 8, 1996.

[7] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Journal of Formalized Mathematics, 1, 1989.

[8] Thomas Becker and Volker Weispfenning. \em Gr\"obner Bases: A Computational Approach to Commutative Algebra. Springer-Verlag, New York, Berlin, 1993.

[9] Jozef Bialas. Group and field definitions. Journal of Formalized Mathematics, 1, 1989.

[10] Czeslaw Bylinski. Functions and their basic properties. Journal of Formalized Mathematics, 1, 1989.

[11] Czeslaw Bylinski. Functions from a set to a set. Journal of Formalized Mathematics, 1, 1989.

[12] Czeslaw Bylinski. Some basic properties of sets. Journal of Formalized Mathematics, 1, 1989.

[13] Agata Darmochwal. Finite sets. Journal of Formalized Mathematics, 1, 1989.

[14] Eugeniusz Kusak, Wojciech Leonczuk, and Michal Muzalewski. Abelian groups, fields and vector spaces. Journal of Formalized Mathematics, 1, 1989.

[15] Gilbert Lee and Piotr Rudnicki. On ordering of bags. Journal of Formalized Mathematics, 14, 2002.

[16] Michal Muzalewski. Construction of rings and left-, right-, and bi-modules over a ring. Journal of Formalized Mathematics, 2, 1990.

[17] Michal Muzalewski and Wojciech Skaba. From loops to abelian multiplicative groups with zero. Journal of Formalized Mathematics, 2, 1990.

[18] Piotr Rudnicki and Andrzej Trybulec. Multivariate polynomials with arbitrary number of variables. Journal of Formalized Mathematics, 11, 1999.

[19] Christoph Schwarzweller. More on multivariate polynomials: Monomials and constant polynomials. Journal of Formalized Mathematics, 13, 2001.

[20] Christoph Schwarzweller. Term orders. Journal of Formalized Mathematics, 14, 2002.

[21] Andrzej Trybulec. Tarski Grothendieck set theory. Journal of Formalized Mathematics, Axiomatics, 1989.

[22] Andrzej Trybulec. Subsets of real numbers. Journal of Formalized Mathematics, Addenda, 2003.

[23] Andrzej Trybulec and Agata Darmochwal. Boolean domains. Journal of Formalized Mathematics, 1, 1989.

[24] Wojciech A. Trybulec. Partially ordered sets. Journal of Formalized Mathematics, 1, 1989.

[25] Wojciech A. Trybulec. Vectors in real linear space. Journal of Formalized Mathematics, 1, 1989.

[26] Wojciech A. Trybulec. Pigeon hole principle. Journal of Formalized Mathematics, 2, 1990.

[27] Zinaida Trybulec. Properties of subsets. Journal of Formalized Mathematics, 1, 1989.

[28] Edmund Woronowicz. Relations and their basic properties. Journal of Formalized Mathematics, 1, 1989.

[29] Edmund Woronowicz. Relations defined on sets. Journal of Formalized Mathematics, 1, 1989.

[30] Edmund Woronowicz and Anna Zalewska. Properties of binary relations. Journal of Formalized Mathematics, 1, 1989.