In a partially ordered set an element c is called compact if it satisfies one of the following equivalent conditions:
For every directed subsetD of P, if D has a supremum sup D and c ≤ sup D then c ≤ d for some element d of D.
For every idealI of P, if I has a supremum sup I and c ≤ sup I then c is an element ofI.
If the poset P additionally is a join-semilattice then these conditions are equivalent to the following statement:
For every subset S of P, if S has a supremum sup S and c ≤ sup S, then c ≤ sup T for some finite subsetT of S.
In particular, if c = sup S, then c is the supremum of a finite subset of S. These equivalences are easily verified from the definitions of the concepts involved. For the case of a join-semilattice, any set can be turned into a directed set with the same supremum by closing under finite suprema. When considering directed complete partial orders or complete lattices the additional requirements that the specified suprema exist can of course be dropped. A join-semilattice that is directed complete is almost a complete lattice —see completeness for details.
Examples
The most basic example is obtained by considering the power set of some set A, ordered by subset inclusion. Within this complete lattice, the compact elements are exactly the finite subsets of A. This justifies the name "finite element".
The term "compact" is explained by considering the complete lattices of open sets of some topological spaceT, also ordered by subset inclusion. Within this order, the compact elements are just the compact subsets of T. Indeed, the condition for compactness in join-semilattices translates immediately to the corresponding definition.
If it exists, the least element of a poset is always compact. It may be that this is the only compact element, as the example of the real unit interval shows.
A poset in which every element is the supremum of the compact elements below it is called an algebraic poset. Such posets that are dcpos are much used in domain theory. As an important special case, an algebraic lattice is a complete lattice L, such that every element x of L is the supremum of the compact elements below x. A typical example is the following: For any algebra A, let Sub be the set of all substructures of A, i.e., of all subsets of A which are closed under all operations of A. Here the notion of substructure includes the empty substructure in case the algebra A has no nullary operations. Then:
The set Sub, ordered by set inclusion, is a lattice.
The set Sub is even a complete lattice. The greatest lower bound of any family of substructures is their intersection.
The compact elements of Sub are exactly the finitely generated substructures of A.
Every substructure is the union of its finitely generated substructures; hence Sub is an algebraic lattice.
Also, a kind of converse holds: Every algebraic lattice is isomorphic to Sub for some algebra A. There is another algebraic lattice that plays an important role in universal algebra: For every algebra A we let Con be the set of all congruence relations on A. Each congruence on A is a subalgebra of the product algebra AxA, so Con ⊆ Sub. Again we have
Con, ordered by set inclusion, is a lattice.
The greatest element of Con is the set AxA, which is the congruence corresponding to the constant homomorphism. The smallest congruence is the diagonal of AxA, corresponding to isomorphisms.
Con is a complete lattice.
The compact elements of Con are exactly the finitely generated congruences.
Con is an algebraic lattice.
Again there is a converse: By a theorem of George Grätzer and E. T. Schmidt, every algebraic lattice is isomorphic to Con for some algebra A.
Applications
Compact elements are important in computer science in the semantic approach called domain theory, where they are considered as a kind of primitive element: the information represented by compact elements cannot be obtained by any approximation that does not already contain this knowledge. Compact elements cannot be approximated by elements strictly below them. On the other hand, it may happen that all non-compact elements can be obtained as directed suprema of compact elements. This is a desirable situation, since the set of compact elements is often smaller than the original poset—the examples above illustrate this.
Literature
See the literature given for order theory and domain theory.
