Compact element
Encyclopedia
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".
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 lattice
s 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.
.
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 relation
s 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.
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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
area of order theory
Order theory
Order theory is a branch of mathematics which investigates our 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 gives some basic definitions...
, the compact or finite elements of a partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
are those elements that cannot be subsumed by a supremum
Supremum
In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...
of any non-empty directed set
Directed set
In mathematics, a directed set is a nonempty set A together with a reflexive and transitive binary relation ≤ , with the additional property that every pair of elements has an upper bound: In other words, for any a and b in A there must exist a c in A with a ≤ c and b ≤...
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
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
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:- For every directed subsetDirected setIn mathematics, a directed set is a nonempty set A together with a reflexive and transitive binary relation ≤ , with the additional property that every pair of elements has an upper bound: In other words, for any a and b in A there must exist a c in A with a ≤ c and b ≤...
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 idealIdeal (order theory)In mathematical order theory, an ideal is a special subset of a partially ordered set . 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...
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
Semilattice
In mathematics, a join-semilattice is a partially ordered set which 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...
(i.e., if it has binary suprema) then these conditions are equivalent to the following statement:
- For every nonempty 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 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 lattice
Complete lattice
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...
s 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)
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 . A special use of the term refers to complete partial orders or complete lattices...
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
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
unit interval [0,1] shows.
Examples
- The most basic example is obtained by considering the power set of some set, ordered by subset inclusionSubsetIn mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
. 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 setOpen setThe concept of an open set is fundamental to many areas of mathematics, especially point-set topology and metric topology. Intuitively speaking, a set U is open if any point x in U can be "moved" a small amount in any direction and still be in the set U...
s of some topological spaceTopological spaceTopological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
, also ordered by subset inclusionSubsetIn mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
. 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.
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 theoryDomain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets 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...
.
As an important special case, an algebraic lattice is a complete lattice
Complete lattice
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...
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:
- 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
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
: For every algebra A
we let Con(A) be the set of all congruence relation
Congruence relation
In abstract algebra, a congruence relation is an equivalence relation on an algebraic structure that is compatible with the structure...
s 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 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 scienceComputer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
in the semantic approach called domain theory
Domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets 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...
, 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.