Combinatorial properties of regressive mappings (Q791524): Difference between revisions

The main theorem proved in the paper is the following Ramsey type theorem: Let \({\mathbb{C}}\) be a (*)-category which is well and Ramsey. Then for every positive integer m there exists a positive integer n such that for every mapping \(\rho:{\mathcal L}(n,{\mathbb{C}})\to {\mathcal L}(n,{\mathbb{C}})\) such that \(\rho\) (f)\(\leq f\) for every \(f\in {\mathcal L}(n,{\mathbb{C}})\) there is a strictly ascending sequence \(f_ 0<f_ 1<...<f_ m\) in \({\mathcal L}(n,{\mathbb{C}})\) such that one of the following three cases is obtained: (\(\alpha)\) \(\rho(f_{i+1})=f_ i\) for \(i=0,...,m-1\); (\(\beta)\) \(\rho(f_ i)=f_ i\) for \(i=0,...,m\); (\(\gamma)\) \(\rho(f_ 0)=\rho(f_ 1)=...=\rho(f_ m).\) (1) If \({\mathbb{C}}\) is a category whose objects are non-negative integers and if \({\mathbb{C}}\binom AB\) is the set of morphisms f:\(B\to A\), then \({\mathbb{C}}\) is a (*)-category if \(k<\ell\) implies \(| {\mathbb{C}}\binom \ell\ell| =1\), \({\mathbb{C}}\binom k\ell = \emptyset\), \({\mathbb{C}}\binom\ell k \neq \emptyset\). On \(\cup \{{\mathbb{C}}\binom \ell k | \ell \in w\}\) define \(f\leq_ kg\) iff \(h\cdot f=g\), \(f\in {\mathbb{C}}\binom\ell k\), \(g\in {\mathbb{C}}\binom mk\), \(h\in {\mathbb{C}}\binom m\ell\). (2) \({\mathbb{C}}\) is well if \(\leq_ k\) is a well partial order for each object k. If \({\mathcal L}(n,{\mathbb{C}})=\cup \{{\mathbb{C}}\binom n\ell | 0\leq \ell \leq n\},\) then \(f<g\) provided for some h, \(g\cdot h=f,\) \(f\in {\mathbb{C}}\binom n\ell\), \(g\in {\mathbb{C}}\binom nm\), \(\ell<m\), \(h\in {\mathbb{C}}\binom m\ell\) provides a ranking as well as a partial order. (3) \({\mathbb{C}}\) is Ramsey iff for every pair of positive integers \(\delta\), m there exists a positive integer n such that for every mapping \(\Delta:{\mathcal L}(n,{\mathbb{C}})\to \delta\) there exists an \(X\in {\mathcal L}(n,{\mathbb{C}})\) such that \(rank X=m\left(X\in {\mathbb{C}}\binom mm\right)\) and such that \(\Delta(Y)=\Delta(Z)\) for all Y,\(Z\leq X\) with \(rank Y=rank Z.\) The main theorem yields various short proofs of other Ramsey type theorems (including one of Harzheim) from the construction of various (*)-categories \({\mathbb{C}}\) which are well and Ramsey. These include finite sets (Boolean algebras) and the original Ramsey theorem, finite alphabets, partition, linear and affine lattices. All these are special cases along with Harzheim's theorem of the most general application, to classes of finite ranked lattices with the regressive chain property. Here a class \({\mathcal L}\) of (finite) ranked lattices has the regressive chain property iff for every positive integer m there exists a positive integer n such that for every \(L\in {\mathcal L}\) with \(rank L\geq n\) and for every (regressive) mapping \(\rho:L\to L\) such that \(\rho\) (X)\(\leq X\) for every \(X\in L\), there exists a strictly ascending sequence \(X_ 0<X_ 1<...<X_ m\) of elements of L satisfying conditions (\(\alpha)\), (\(\beta)\), (\(\gamma)\) of the main theorem with respect to the mapping \(\rho\) and the ascending sequence \(X_ 0<X_ 1<...<X_ m.\) The arguments provided are general enough to provide wide applicability and simple enough to remain clear to readers with moderate experience in the area.