Cardinality questions concerning semilattices of finite breadth
✍ Scribed by S.Z Ditor
- Publisher
- Elsevier Science
- Year
- 1984
- Tongue
- English
- Weight
- 570 KB
- Volume
- 48
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
It is shown that if L is a lattice in which every element has only finitely many predecessors and (*) every element has no more than k immediate predecessors, for some positive integer k, then ILl~k-r An example is constructed in which k =2 and ILl=~t, but the question of whether ILl =~k-~ is possible for k >2 is left unanswered. The conclusion ILl~<Nk_x also holds if, instead of (*), we substitute the weaker condition (*)': [or any subset F o[ k + 1 elements of L, x<~sup(F{x}) for some xeF. If, in addition, it is assumed that L satisfies a modularity condition, then it turns out that L must in fact be countable. For sets and set operations, the following results can be stated: if 5~ is a collection of finite sets which is closed under finite union (resp. closed under finite intersection and directed upward) and ~: has the property that for any k + 1 sets in ~, one of the sets is contained in the union (resp. contains the intersection) of the others, then I~1 ~<Rk-1. More generally, we show that if L is a join-semilattice in which every element has fewer than R x predecessors and L satisfies (*)', then ILl ~<~x+k-~-(This turns out to be an application of a result of Erd6s and Hajnal on set-mappings.)