In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

area of

order theory Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...

, the compact elements or finite elements of a

partially ordered set In mathematics, especially order theory, a partial order on a Set (mathematics), set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements need ...

are those elements that cannot be subsumed by a

supremum In mathematics, the infimum (abbreviated inf; : infima) of a subset S of a partially ordered set P is the greatest element in P that is less than or equal to each element of S, if such an element exists. If the infimum of S exists, it is unique, ...

of any non-empty

directed set In mathematics, a directed set (or a directed preorder or a filtered set) is a preordered set in which every finite subset has an upper bound. In other words, it is a non-empty preordered set A such that for any a and b in A there exists c in A wit ...

that does not already contain members above the compact element. This notion of compactness simultaneously generalizes the notions of finite sets in

set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory – as a branch of mathema ...

, compact sets in

topology Topology (from the Greek language, Greek words , and ) is the branch of mathematics concerned with the properties of a Mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformat ...

, and finitely generated modules in

algebra Algebra is a branch of mathematics that deals with abstract systems, known as algebraic structures, and the manipulation of expressions within those systems. It is a generalization of arithmetic that introduces variables and algebraic ope ...

. (There are other notions of

compactness In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space. The idea is that a compact space has no "punctures" or "missing endpoints", i.e., it ...

in mathematics.)

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: * For every directed subset ''D'' of ''P'', if ''D'' has a supremum sup ''D'' and ''c'' ≤ sup ''D'' then ''c'' ≤ ''d'' for some element ''d'' of ''D''. * For every ideal ''I'' of ''P'', if ''I'' has a supremum sup ''I'' and ''c'' ≤ sup ''I'' then ''c'' is an element of ''I''. 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: * For every subset ''S'' of ''P'', if ''S'' has a supremum sup ''S'' and ''c'' ≤ sup ''S'', then ''c'' ≤ sup ''T'' for some finite subset ''T'' 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 (non-empty) suprema. When considering directed complete partial orders or

complete lattice In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum ( join) and an infimum ( meet). A conditionally complete lattice satisfies at least one of these properties for bounded subsets. For compariso ...

s 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 (possibly lacking a

least element In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) is an element of S that is greater than every other element of S. The term least element is defined dually, that is, it is an ele ...

)—see

completeness (order theory) In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set (poset). The most familiar example is the completeness of the real numbers. A special use of ...

for details.

Examples

* The most basic example is obtained by considering the

power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...

of some set ''A'', ordered by subset inclusion. Within this complete lattice, the compact elements are exactly the

finite subset In mathematics, a set is a collection of different things; the things are '' elements'' or ''members'' of the set and are typically mathematical objects: numbers, symbols, points in space, lines, other geometric shapes, variables, or other set ...

s of ''A''. This justifies the name "finite element". * The term "compact" is inspired by the definition of (topologically) compact subsets of a

topological space In mathematics, a topological space is, roughly speaking, a Geometry, geometrical space in which Closeness (mathematics), closeness is defined but cannot necessarily be measured by a numeric Distance (mathematics), distance. More specifically, a to ...

''T''. A set ''Y'' is compact if for every collection of ''open'' sets ''S'', if the union over ''S'' includes ''Y'' as a subset, then ''Y'' is included as a subset of the union of a finite subcollection of ''S''. Considering the power set of ''T'' as a complete lattice with the subset inclusion order, where the supremum of a collection of sets is given by their union, the topological condition for compactness mimics the condition for compactness in join-semilattices, but for the additional requirement of openness. * If it exists, the

of a poset is always compact. It may be that this is the only compact element, as the example of the real unit interval ,1(with the standard ordering inherited from the real numbers) shows. * Every completely join-prime element of a lattice is compact.

Algebraic posets

A poset in which every element is the supremum of the directed set formed by the compact elements below it is called an ''algebraic poset''. Such posets that are dcpos are much used in

domain theory Domain theory is a branch of mathematics that studies special kinds of partially ordered sets (posets) commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer ...

. As an important special case, an ''algebraic lattice'' is a

''L'' where 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: * The set Sub(''A''), ordered by set inclusion, is a lattice. * The greatest element of Sub(''A'') is the set ''A'' itself. * For any ''S'', ''T'' in Sub(''A''), the greatest lower bound of ''S'' and ''T'' is the set theoretic intersection of ''S'' and ''T''; the smallest upper bound is the subalgebra generated by the union of ''S'' and ''T''. * The set Sub(''A'') is even a complete lattice. The greatest lower bound of any family of substructures is their intersection (or ''A'' if the family is empty). * The compact elements of Sub(''A'') are exactly the finitely generated substructures of ''A''. * Every substructure is the union of its finitely generated substructures; hence Sub(''A'') is an algebraic lattice. Also, a kind of converse holds: Every algebraic lattice is

isomorphic In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...

to Sub(''A'') for some algebra ''A''. There is another algebraic lattice that plays an important role in

universal algebra Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures in general, not specific types of algebraic structures. For instance, rather than considering groups or rings as the object of stud ...

: For every algebra ''A'' we let Con(''A'') be the set of all

congruence relation In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group (mathematics), group, ring (mathematics), ring, or vector space) that is compatible with the structure in the ...

s on ''A''. Each congruence on ''A'' is a subalgebra of the product algebra ''A''x''A'', so Con(''A'') ⊆ Sub(''A''x''A''). Again we have * Con(''A''), ordered by set inclusion, is a lattice. * The greatest element of Con(''A'') is the set ''A''x''A'', which is the congruence corresponding to the constant homomorphism. The smallest congruence is the diagonal of ''A''x''A'', corresponding to isomorphisms. * Con(''A'') is a complete lattice. * The compact elements of Con(''A'') are exactly the finitely generated congruences. * Con(''A'') 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(''A'') for some algebra ''A''.

Applications

Compact elements are important in

computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

in the semantic approach called

, 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

and

References

{{reflist Order theory