Compact element

In the mathematical area of order theory, the compact or finite elements of a partially ordered set are those elements that cannot be subsumed by a supremum of any non-empty directed set that does not already contain members above the compact element.

Note that there are other notions of compactness in mathematics; also, the term "finite" in its normal set theoretic meaning does not coincide with the order-theoretic notion of a "finite element".

Formal definition

In a partially ordered set (P,≤) an element c is called compact (or finite) if it satisfies one of the following equivalent conditions:

If the poset P additionally is a join-semilattice (i.e., if it has binary suprema) then these conditions are equivalent to the following statement:

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 note that any set can be turned into a directed set with the same supremum by closing under finite (non-empty) suprema.

When considering directed complete partial orders or complete lattices the additional requirements that the specified suprema exist can of course be dropped. Note also that a join-semilattice which is directed complete is almost a complete lattice (possibly lacking a least element) -- see completeness (order theory) for details.

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 [0,1] shows.

Examples

Algebraic posets

A poset in which every element is the supremum of the compact elements below it is called an algebraic poset. Such posets which 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 (which served as the motivation for the name "algebraic") is the following:

For any algebra A (for example, a group, a ring, a field, a lattice, etc.; or even a mere set without any operations), let Sub(A) be the set of all substructures of A, i.e., of all subsets of A which are closed under all operations of A (group addition, ring addition and multiplication, etc.) Here the notion of substructure includes the empty substructure in case the algebra A has no nullary operations.

Then:

Also, a kind of converse holds: Every algebraic lattice is isomorphic to Sub(A) for some algebra A.

There is another algebraic lattice which plays an important role in universal algebra: For every algebra A we let Con(A) be the set of all congruence relations on A. Each congruence on A is a subalgebra of the product algebra AxA, so Con(A) ⊆ Sub(AxA). Again we have

Again there is a converse: By a theorem of G. Grätzer and E.T.Schmidt, every algebraic lattice is isomorphic to Con(A) 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.

This article is issued from Wikipedia - version of the Monday, January 11, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.