Compact element

Last updated November 04, 2024

In the mathematical area of order theory, the compact elements 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. This notion of compactness simultaneously generalizes the notions of finite sets in set theory, compact sets in topology, and finitely generated modules in algebra. (There are other notions of compactness 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 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 (possibly lacking a least element)—see completeness (order theory) 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".^[1]
The term "compact" is inspired by the definition of (topologically) compact subsets of a topological space 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 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] (with the standard ordering inherited from the real numbers) shows.
Every completely join-prime element of a lattice is compact.^{[ citation needed ]}

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.

As an important special case, an algebraic lattice is a complete lattice 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.^[2]

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

There is another algebraic lattice that 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

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

Related Research Articles

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.

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 comparison, in a general lattice, only pairs of elements need to have a supremum and an infimum. Every non-empty finite lattice is complete, but infinite lattices may be incomplete.

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 science, where it is used to specify denotational semantics, especially for functional programming languages. Domain theory formalizes the intuitive ideas of approximation and convergence in a very general way and is closely related to topology.

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 introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary.

This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:

A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum and a unique infimum. An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor.

In mathematics, a closure operator on a set S is a function $:{\mathcal {P}}(S)\rightarrow {\mathcal {P}}(S)}$ from the power set of S to itself that satisfies the following conditions for all sets

In the mathematical area of order theory, one often speaks about functions that preserve certain limits, i.e. certain suprema or infima. Roughly speaking, these functions map the supremum/infimum of a set to the supremum/infimum of the image of the set. Depending on the type of sets for which a function satisfies this property, it may preserve finite, directed, non-empty, or just arbitrary suprema or infima. Each of these requirements appears naturally and frequently in many areas of order theory and there are various important relationships among these concepts and other notions such as monotonicity. If the implication of limit preservation is inverted, such that the existence of limits in the range of a function implies the existence of limits in the domain, then one obtains functions that are limit-reflecting.

In mathematical order theory, an ideal is a special subset of a partially ordered set (poset). Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion. Ideals are of great importance for many constructions in order and lattice 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 the term refers to complete partial orders or complete lattices. However, many other interesting notions of completeness exist.

In mathematics, the phrase complete partial order is variously used to refer to at least three similar, but distinct, classes of partially ordered sets, characterized by particular completeness properties. Complete partial orders play a central role in theoretical computer science: in denotational semantics and domain theory.

In the mathematical area of order theory, there are various notions of the common concept of distributivity, applied to the formation of suprema and infima. Most of these apply to partially ordered sets that are at least lattices, but the concept can in fact reasonably be generalized to semilattices as well.

In the mathematical fields of order and domain theory, a Scott domain is an algebraic, bounded-complete and directed-complete partial order (dcpo). They are named in honour of Dana S. Scott, who was the first to study these structures at the advent of domain theory. Scott domains are very closely related to algebraic lattices, being different only in possibly lacking a greatest element. They are also closely related to Scott information systems, which constitute a "syntactic" representation of Scott domains.

In mathematics, a join-semilattice is a partially ordered set that has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset. Every join-semilattice is a meet-semilattice in the inverse order and vice versa.

In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum. Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing. Every Boolean algebra A has an essentially unique completion, which is a complete Boolean algebra containing A such that every element is the supremum of some subset of A. As a partially ordered set, this completion of A is the Dedekind–MacNeille completion.

In mathematics, a Riesz space, lattice-ordered vector space or vector lattice is a partially ordered vector space where the order structure is a lattice.

In mathematics, the congruence lattice problem asks whether every algebraic distributive lattice is isomorphic to the congruence lattice of some other lattice. The problem was posed by Robert P. Dilworth, and for many years it was one of the most famous and long-standing open problems in lattice theory; it had a deep impact on the development of lattice theory itself. The conjecture that every distributive lattice is a congruence lattice is true for all distributive lattices with at most ℵ₁ compact elements, but F. Wehrung provided a counterexample for distributive lattices with ℵ₂ compact elements using a construction based on Kuratowski's free set theorem.

In the branch of mathematics known as universal algebra, a subdirectly irreducible algebra is an algebra that cannot be factored as a subdirect product of "simpler" algebras. Subdirectly irreducible algebras play a somewhat analogous role in algebra to primes in number theory.

In order theory, a continuous poset is a partially ordered set in which every element is the directed supremum of elements approximating it.

References

↑ "compact element in nLab". ncatlab.org. Retrieved 2024-11-03.
↑ "Compact lattice element - Encyclopedia of Mathematics". encyclopediaofmath.org. Retrieved 2024-11-03.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] "compact element in nLab". ncatlab.org. Retrieved 2024-11-03.

[2] "Compact lattice element - Encyclopedia of Mathematics". encyclopediaofmath.org. Retrieved 2024-11-03.

[1]

[2]