Monomordnung

Es sind auch andere äquivalente Definitionen üblich. So ist es etwa möglich die Bedingung (2) durch eine andere Bedingung auszutauschen. In der Literatur[1] finden sich zum Beispiel:

(2') Die Ordnung ${\displaystyle \leq }$ ist eine Wohlordnung

oder auch äquivalenten dazu

(2*) Bezüglich der Ordnung ${\displaystyle \leq }$ gibt es keine unendlichen absteigenden Ketten ${\displaystyle x^{\alpha _{1}}>x^{\alpha _{2}}>x^{\alpha _{3}}>\cdots }$ von Monomen.

Die Eigenschaft (2*) ist Grundlage vieler Terminierungsbeweise für Algorithmen im Zusammenhang mit Gröbnerbasen.

Falls wir nur eine Variable haben, also ${\displaystyle n=1}$ gilt, gibt es nur eine Monomordnung ${\displaystyle \leq }$. Aus der Definition einer Monomordnung folgt nämlich direkt, dass in diesem Fall ${\displaystyle 1=x^{0}\leq x^{1}\leq x^{2}\leq \dotsc }$ sein muss.

Bezüglich der lexikalischen oder lexikographischen Ordnung ${\displaystyle \leq _{\mathrm {lex} }}$ gilt ${\displaystyle x^{\alpha }\leq _{\mathrm {lex} }x^{\beta }}$ genau dann, wenn der am weitesten links stehende, von Null verschiedene Eintrag von ${\displaystyle \alpha -\beta }$ negativ ist. Das heißt, es kann rekursiv definiert werden

${\displaystyle x^{\alpha }\leq _{\mathrm {lex} }x^{\beta }\Leftrightarrow (\alpha _{1}<\beta _{1}){\mbox{ oder }}(\alpha _{1}=\beta _{1}{\mbox{ und }}x_{2}^{\alpha _{2}}\cdots x_{n}^{\alpha _{n}}\leq _{\mathrm {lex} }x_{2}^{\beta _{2}}\cdots x_{n}^{\beta _{n}}).}$

Die Totalgradordnung oder graduierte lexikalische Ordnung ${\displaystyle \leq _{\mathrm {tdeg} }}$ ist definiert durch

${\displaystyle x_{1}^{e_{1}}\cdots x_{n}^{e_{n}}\leq _{\mathrm {tdeg} }x_{1}^{f_{1}}\cdots x_{n}^{f_{n}}\Leftrightarrow \left(\sum _{i=1}^{n}e_{i}<\sum _{i=1}^{n}f_{i}\right){\mbox{ oder }}\left(\sum _{i=1}^{n}e_{i}=\sum _{i=1}^{n}f_{i}{\mbox{ und }}x_{1}^{e_{1}}\cdots x_{n}^{e_{n}}\leq _{\mathrm {lex} }x_{1}^{f_{1}}\cdots x_{n}^{f_{n}}\right)}$

Hier gilt[2]:

${\displaystyle x_{1}^{e_{1}}\cdots x_{n}^{e_{n}}\leq _{\mathrm {degrevlex} }x_{1}^{f_{1}}\cdots x_{n}^{f_{n}}\Leftrightarrow \left(\sum _{i=1}^{n}e_{i}<\sum _{i=1}^{n}f_{i}\right){\mbox{ oder }}\left(\sum _{i=1}^{n}e_{i}=\sum _{i=1}^{n}f_{i}{\mbox{ und }}f_{j}\leq e_{j}{\mbox{ für }}j=max\{i:e_{i}\neq f_{i}\}\right)}$

Sei ${\displaystyle A\in \mathbb {Z} ^{n\times n}}$invertierbar mit der Eigenschaft, dass in jeder Spalte der erste von Null verschiedene Eintrag positiv ist. Dann gilt[3]:

${\displaystyle x^{\alpha }\leq _{\mathrm {A} }x^{\beta }\Leftrightarrow (A\alpha \leq _{\mathrm {lex} }A\beta ).}$

Insbesondere kann man jede beliebige Monomordnung als Matrixordnung in ${\displaystyle \mathbb {R} ^{n\times n}}$darstellen. So ergibt sich beispielsweise für die Totalordnung (graduiert lexikographische Ordnung) folgende Matrix: ${\displaystyle {\begin{pmatrix}1&1&...&1&1\\1&0&...&0&0\\0&1&...&0&0\\...&...&...&...&...\\0&0&...&1&0\end{pmatrix}}}$. Die Grad-revers-lex-Ordnung kann folgendermaßen in eine Matrix umgesetzt werden: ${\displaystyle {\begin{pmatrix}1&1&...&1&1\\0&0&...&0&-1\\0&0&...&-1&0\\...&...&...&...&...\\0&-1&...&0&0\end{pmatrix}}}$.

Jedes Monom ${\displaystyle m}$ über einer Variablenmenge ${\displaystyle X\cup Y}$ kann auf eindeutige Weise in ein Produkt ${\displaystyle m_{x}m_{y}}$ zerlegt werden, so dass in ${\displaystyle m_{x}}$ nur Variablen aus ${\displaystyle X}$ und in ${\displaystyle m_{y}}$ nur Variablen aus ${\displaystyle Y}$ vorkommen. Mit dieser Schreibweise wird für gegebene Monomordnungen ${\displaystyle \leq _{x}}$ und ${\displaystyle \leq _{y}}$ auf Monomen über den Variablen aus ${\displaystyle X}$ bzw. ${\displaystyle Y}$ die Blockordnung ${\displaystyle \leq _{x>y}}$ auf Monomen in ${\displaystyle X\cup Y}$ definiert als

${\displaystyle m\leq _{x>y}n{\mbox{ genau dann, wenn }}(m_{x}\leq _{x}n_{x}){\mbox{ oder }}(m_{x}=n_{x}{\mbox{ und }}m_{y}\leq _{y}n_{y})}$