Details
| Original language | English |
|---|---|
| Pages (from-to) | 375-403 |
| Number of pages | 29 |
| Journal | ORDER |
| Volume | 12 |
| Issue number | 4 |
| Publication status | Published - Dec 1995 |
Abstract
We investigate the structure of intervals in the lattice of all closed quasiorders on a compact or discrete space. As a first step, we show that if the interval I has no infinite chains then the underlying space may be assumed to be finite, and in particular, I must be finite, too. We compute several upper bounds for its size in terms of its height h, which in turn can be computed easily by means of the least and the greatest element of I. The cover degree c of the interval (i.e. the maximal number of atoms in a subinterval) is less than 4 h. Moreover, if c≥4(n-1) then I contains a Boolean subinterval of size 2n, and if I is geometric then it is already a finite Boolean lattice. While every finite distributive lattice is isomorphic to some interval of quasiorders, we show that a nondistributive finite interval of quasiorders is neither a vertical sum nor a horizontal sum of two lattices, with exception of the pentagon. Many further lattices are excluded from the class of intervals of quasiorders by the fact that no join-irreducible element of such an interval can have two incomparable join-irreducible complements. Up to isomorphism, we determine all quasiorder intervals with less than 9 elements and all quasiorder intervals with two complementary atoms or coatoms.
Keywords
- (closed) quasiorder, Atom, complete lattice, height, Mathematics Subject Classifications (1991): 06A07, 06A23, 06B15, 54F05, ordered topological space
ASJC Scopus subject areas
- Mathematics(all)
- Algebra and Number Theory
- Mathematics(all)
- Geometry and Topology
- Computer Science(all)
- Computational Theory and Mathematics
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: ORDER, Vol. 12, No. 4, 12.1995, p. 375-403.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Intervals in lattices of quasiorders
AU - Erné, Marcel
AU - Reinhold, Jürgen
PY - 1995/12
Y1 - 1995/12
N2 - We investigate the structure of intervals in the lattice of all closed quasiorders on a compact or discrete space. As a first step, we show that if the interval I has no infinite chains then the underlying space may be assumed to be finite, and in particular, I must be finite, too. We compute several upper bounds for its size in terms of its height h, which in turn can be computed easily by means of the least and the greatest element of I. The cover degree c of the interval (i.e. the maximal number of atoms in a subinterval) is less than 4 h. Moreover, if c≥4(n-1) then I contains a Boolean subinterval of size 2n, and if I is geometric then it is already a finite Boolean lattice. While every finite distributive lattice is isomorphic to some interval of quasiorders, we show that a nondistributive finite interval of quasiorders is neither a vertical sum nor a horizontal sum of two lattices, with exception of the pentagon. Many further lattices are excluded from the class of intervals of quasiorders by the fact that no join-irreducible element of such an interval can have two incomparable join-irreducible complements. Up to isomorphism, we determine all quasiorder intervals with less than 9 elements and all quasiorder intervals with two complementary atoms or coatoms.
AB - We investigate the structure of intervals in the lattice of all closed quasiorders on a compact or discrete space. As a first step, we show that if the interval I has no infinite chains then the underlying space may be assumed to be finite, and in particular, I must be finite, too. We compute several upper bounds for its size in terms of its height h, which in turn can be computed easily by means of the least and the greatest element of I. The cover degree c of the interval (i.e. the maximal number of atoms in a subinterval) is less than 4 h. Moreover, if c≥4(n-1) then I contains a Boolean subinterval of size 2n, and if I is geometric then it is already a finite Boolean lattice. While every finite distributive lattice is isomorphic to some interval of quasiorders, we show that a nondistributive finite interval of quasiorders is neither a vertical sum nor a horizontal sum of two lattices, with exception of the pentagon. Many further lattices are excluded from the class of intervals of quasiorders by the fact that no join-irreducible element of such an interval can have two incomparable join-irreducible complements. Up to isomorphism, we determine all quasiorder intervals with less than 9 elements and all quasiorder intervals with two complementary atoms or coatoms.
KW - (closed) quasiorder
KW - Atom
KW - complete lattice
KW - height
KW - Mathematics Subject Classifications (1991): 06A07, 06A23, 06B15, 54F05
KW - ordered topological space
UR - http://www.scopus.com/inward/record.url?scp=21344448799&partnerID=8YFLogxK
U2 - 10.1007/BF01110380
DO - 10.1007/BF01110380
M3 - Article
AN - SCOPUS:21344448799
VL - 12
SP - 375
EP - 403
JO - ORDER
JF - ORDER
SN - 0167-8094
IS - 4
ER -