Combinatorial properties of regressive mappings (Q791524): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q233347 |
||
Property / reviewed by | |||
Property / reviewed by: Joseph Neggers / rank | |||
Revision as of 10:18, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Combinatorial properties of regressive mappings |
scientific article |
Statements
Combinatorial properties of regressive mappings (English)
0 references
1983
0 references
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.
0 references
regressive mappings
0 references
finite ranked lattices
0 references
regressive chain property
0 references