1 Orders and Abstract Reduction Relations
1.1 Monomial Ideals and Dickson’s Lemma
Let \(r\) be a relation on \(M\). Then \(r\) is called
reflexive if \(\Delta (M) \subseteq r\),
symmetric if \(r \subseteq r^{-1}\),
transitive if \(r \circ r \subseteq r\),
antisymmetric if \(r \cap r^{-1} \subseteq \Delta (M)\),
connex if \(r \cup r^{-1} = M \times M\),
irreflexive if \(\Delta (M) \cap r = \emptyset \),
strictly antisymmetric if \(r \cap r^{-1} = \emptyset \),
an equivalence relation on \(M\) if \(r\) is reflexive, symmetric, and transitive,
a quasi-order (preorder) on \(M\) if \(r\) is reflexive and transitive,
a partial order on \(M\) if \(r\) is reflexive, transitive and antisymmetric,
a (linear) order on \(M\) if \(r\) is a connex partial order on \(M\), and
a linear quasi-order on \(M\) if \(r\) is a connex quasi-order on \(M\).
Let \(r\) be a relation on \(M\) with strict part \(r_s\), and let \(N \subseteq M\).
Then an element \(a\) of \(N\) is called \(r\)-minimal (\(r\)-maximal) in \(N\) if there is no \(b \in N\) with \(b \, r_s \, a\) (with \(a \, r_s \, b\)). For \(N = M\) the reference to \(N\) is omitted.
A strictly descending (strictly ascending) \(r\)-chain in \(M\) is an infinite sequence \(\{ a_n\} _{n \in \mathbb {N}}\) of elements of \(M\) such that \(a_{n+1} \, r_s \, a_n\) (such that \(a_n \, r_s \, a_{n+1}\)) for all \(n \in \mathbb {N}\).
The relation \(r\) is called well-founded (noetherian) if every non-empty subset \(N\) of \(M\) has an \(r\)-minimal (an \(r\)-maximal) element. \(r\) is a well-order on \(M\) if \(r\) is a well-founded linear order on \(M\).
Let \((M,\le )\) be a preordered set. Define an equivalence relation
We write \([a]\) for the equivalence class of \(a\), and denote the quotient by
Let \(N\subseteq M\). An element \(b\in N\) is called minimal in \(N\) if
We denote by
the set of all minimal elements of \(N\). The min–classes of \(N\) are then
Let \(\preceq \) be a quasi-order on \(M\) and let \(N \subseteq M\). Then a subset \(B\) of \(N\) is called a Dickson basis, or simply basis of \(N\) w.r.t. \(\preceq \), if for every \(a \in N\) there exists some \(b \in B\) with \(b \preceq a\).
We say that \(\preceq \) has the Dickson property, or is a well-quasi-order(wqo), if every subset \(N\) of \(M\) has a finite basis w.r.t. \(\preceq \).
A well partial order, or a wpo, is a wqo that is a proper ordering relation, i.e., it is antisymmetric.
Let \(\preceq \) be a quasi-order on \(M\) with associated equivalence relation \(\sim \). Then the following are equivalent:
\(\preceq \) is a well-quasi-order.
Whenever \(\{ a_n\} _{n \in \mathbb {N}}\) is a sequence of elements of \(M\), then there exist \(i {\lt} j\) with \(a_i \preceq a_j\).
For every nonempty subset \(N\) of \(M\), the number of min-classes in \(N\) is finite and non-zero.
Let \(\preceq \) be a well-partial-order on \(M\). Then every non-empty subset \(N\) of \(M\) has a unique minimal finite basis \(B\), i.e., a finite basis \(B\) such that \(B \subseteq C\) for all other bases \(C\) of \(N\). \(B\) consists of all minimal elements of \(N\).
Every well-quasi-order is well-founded.
Let \(\preceq \) be a well- quasi-order on \(M\), and let \(\{ a_n\} _{n \in \mathbb {N}}\) be a sequence of elements of \(M\). Then there exists a strictly ascending sequence \(\{ n_i\} _{i \in \mathbb {N}}\) of natural numbers such that \(a_{n_i} \preceq a_{n_j}\) for all \(i {\lt} j\).
Let \(I = \langle x^\alpha \mid \alpha \in A \rangle \) be a monomial ideal. Then a monomial \(x^\beta \) lies in \(I\) if and only if \(x^\beta \) is divisible by \(x^\alpha \) for some \(\alpha \in A\).
Let \((\mathbb {N}^n, \le ')\) be the direct product of \(n\) copies of the natural numbers \((\mathbb {N}, \le )\) with their natural ordering. Then \((\mathbb {N}^n, \le ')\) is a Dickson partially ordered set. More explicitly, every subset \(S \subseteq \mathbb {N}^n\) has a finite subset \(B\) such that for every \((m_1, \dots , m_n) \in S\), there exists \((k_1, \dots , k_n) \in B\) with
Test
Let \(I = \langle x^{\alpha } | \alpha \in A \rangle \subseteq k[x_1, \ldots , x_n]\) be a monomial ideal. Then \(I\) can be written in the form \(I = \langle x^{\alpha (1)}, \ldots , {\alpha (s)} \rangle \), where \(\alpha (1), \ldots , \alpha (s) \in A\). In particular, \(I\) has a finite basis.
quad