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 directed set that does not already contain members above the compact element. Note that there are other notions of compactness in mathematics and that the term finite with its common set theoretic semantics does not coincide with the order theoretic notion of finite elements either. Euclid, a famous Greek mathematician known as the father of geometry, is shown here in detail from The School of Athens by Raphael. ... Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... In mathematics, especially order theory, a partially ordered set (or poset for short) is a set equipped with a partial order relation. ... In mathematics, the supremum of an ordered set S is the least element that is greater than or equal to each element of S. Consequently, it is also referred to as the least upper bound (also lub and LUB). ... In mathematics, a directed set is a set A together with a binary relation ≤ having the following properties: a ≤ a for all a in A (reflexivity) if a ≤ b and b ≤ c, then a ≤ c (transitivity) for any two a and b in A, there exists a c in A... The compactness theorem is a basic fact in symbolic logic and model theory and asserts that a set (possibly infinite) of first-order sentences is satisfiable, i. ... Set theory is the mathematical theory of sets, which represent collections of abstract objects. ...

Compact elements are important in 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. Especially 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 compacts is often smaller than the original poset -- the examples below illustrate this. Posets that can be recovered from their set of compact elements are called algebraic posets. Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. ... In mathematics, especially order theory, a partially ordered set (or poset for short) is a set equipped with a partial order relation. ...

Formal definition

For some partially ordered set (P,≤) an element c of P 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 than c is an element of I.
• The element c is way below itself, i.e. c << c

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 mathematics, a directed set is a set A together with a binary relation ≤ having the following properties: a ≤ a for all a in A (reflexivity) if a ≤ b and b ≤ c, then a ≤ c (transitivity) for any two a and b in A, there exists a c in A... In mathematical order theory, an ideal is a special subset of a partially ordered set. ... A semilattice is a mathematical concept with two definitions, one as a type of ordered set, the other as an algebraic structure. ...

• 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.

Using the definitions of the involved concepts these equivalences are easily verified. For the case of the join-semilattices 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. In mathematics, directed complete partial orders and complete partial orders are special classes of partially ordered sets. ... In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). ... In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually. ... In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set. ...

If it exists, the least element of a poset is always compact. It may well be that this is the only compact element, as the example of the real unit interval [0,1] shows. In mathematics, the real numbers are intuitively defined as numbers that are in one-to-one correspondence with the points on an infinite line—the number line. ...

Examples

• The most basic example is obtained by considering the powerset of some set, ordered by subset inclusion. Within this complete lattice, the compact elements are exactly the finite sets. This justifies the name "finite element".

• The term "compact" is explained by considering the complete lattices of open sets of some topological space. Within this order, the compact elements are just the compact sets. Indeed, the condition for compactness in join-semilattices translates immediately to the corresponding definition.

In mathematics, given a set S, the power set of S, written P(S) or 2S, is the set of all subsets of S. In formal language, the existence of power set of any set is presupposed by the axiom of power set. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. The relationship of one set being a subset of another is called inclusion. ... In mathematics, a set is called finite if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ... In topology and related fields of mathematics, a set U is called open if, intuitively speaking, you can wiggle or change any point x in U by a small amount in any direction and still be inside U. In other words, if x is surrounded only by elements of U... Topological spaces are structures that allow one to formalize concepts such as convergence, connectedness and continuity. ... In mathematics, a compact set is a set of points in a topological space such that every one of its (possibly infinite) open covers has a finite subcover. ...

Algebraic lattices

A complete lattice L is called algebraic, if every element x of L is the supremum of the compact elements below x. A typical example (which served as the motiviation for the name "algebraic") is the following: In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). ...

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 interesction.
• 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 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 Universal algebra is the field of mathematics that studies the ideas common to all algebraic structures. ... In mathematics and especially in abstract algebra, a congruence relation or simply congruence is an equivalence relation that is compatible with some algebraic operation(s). ...

• Con(A), ordered by set inclusion, is a lattice.
• The greatest element of Con(A) 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(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 G. Grätzer and E.T.Schmidt, every algebraic lattice is isomorphic to Con(A) for some algebra A.

Literature

Compact elements are standard. See the literature given for order theory and domain theory. Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. ... Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. ...