AntichainIn mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its width. By Dilworth's theorem, this also equals the minimum number of chains (totally ordered subsets) into which the set can be partitioned. Dually, the height of the partially ordered set (the length of its longest chain) equals by Mirsky's theorem the minimum number of antichains into which the set can be partitioned.
Duality (order theory)In the mathematical area of order theory, every partially ordered set P gives rise to a dual (or opposite) partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the same set, but with the inverse order, i.e. x ≤ y holds in Pop if and only if y ≤ x holds in P. It is easy to see that this construction, which can be depicted by flipping the Hasse diagram for P upside down, will indeed yield a partially ordered set. In a broader sense, two partially ordered sets are also said to be duals if they are dually isomorphic, i.
Ideal (order theory)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. A subset I of a partially ordered set is an ideal, if the following conditions hold: I is non-empty, for every x in I and y in P, y ≤ x implies that y is in I (I is a lower set), for every x, y in I, there is some element z in I, such that x ≤ z and y ≤ z (I is a directed set).
Lattice (order)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 (also called a least upper bound or join) and a unique infimum (also called a greatest lower bound or meet). 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.
Maximal and minimal elementsIn mathematics, especially in order theory, a maximal element of a subset S of some preordered set is an element of S that is not smaller than any other element in S. A minimal element of a subset S of some preordered set is defined dually as an element of S that is not greater than any other element in S. The notions of maximal and minimal elements are weaker than those of greatest element and least element which are also known, respectively, as maximum and minimum.
Directed setIn mathematics, a directed set (or a directed preorder or a filtered set) is a nonempty set together with a reflexive and transitive binary relation (that is, a preorder), with the additional property that every pair of elements has an upper bound. In other words, for any and in there must exist in with and A directed set's preorder is called a direction. The notion defined above is sometimes called an . A is defined analogously, meaning that every pair of elements is bounded below.
Family of setsIn set theory and related branches of mathematics, a collection of subsets of a given set is called a family of subsets of , or a family of sets over More generally, a collection of any sets whatsoever is called a family of sets, set family, or a set system. A family of sets may be defined as a function from a set , known as the index set, to , in which case the sets of the family are indexed by members of .
PreorderIn mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special cases of a preorder: an antisymmetric (or ) preorder is a partial order, and a symmetric preorder is an equivalence relation. The name comes from the idea that preorders (that are not partial orders) are 'almost' (partial) orders, but not quite; they are neither necessarily antisymmetric nor asymmetric.
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 the term refers to complete partial orders or complete lattices. However, many other interesting notions of completeness exist. The motivation for considering completeness properties derives from the great importance of suprema (least upper bounds, joins, "") and infima (greatest lower bounds, meets, "") to the theory of partial orders.
Distributive latticeIn mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection. Indeed, these lattices of sets describe the scenery completely: every distributive lattice is—up to isomorphism—given as such a lattice of sets. As in the case of arbitrary lattices, one can choose to consider a distributive lattice L either as a structure of order theory or of universal algebra.
