Category: Order theory

Knaster–Tarski theorem
In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following: Let (L, ≤) be a complete lattice and let f : L
Monotonic function
In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generaliz
Complete Boolean algebra
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound). Complete Boolean algebras are used to construct Boolean-valued models of set t
Deviation of a poset
In order-theoretic mathematics, the deviation of a poset is an ordinal number measuring the complexity of a poset. A poset is also known as a partially ordered set. The deviation of a poset is used to
Partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A po
Preordered class
In mathematics, a preordered class is a class equipped with a preorder.
In mathematics, specifically order theory, a well-quasi-ordering or wqo is a quasi-ordering such that any infinite sequence of elements from contains an increasing pair with
Bruhat order
In mathematics, the Bruhat order (also called strong order or strong Bruhat order or Chevalley order or Bruhat–Chevalley order or Chevalley–Bruhat order) is a partial order on the elements of a Coxete
Order topology
In mathematics, an order topology is a certain topology that can be defined on any totally ordered set. It is a natural generalization of the topology of the real numbers to arbitrary totally ordered
Betweenness is an algorithmic problem in order theory about ordering a collection of items subject to constraints that some items must be placed between others. It has applications in bioinformatics a
Distributivity (order 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 se
Total order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation on some set , which satisfies the following for all and
Path ordering (term rewriting)
In theoretical computer science, in particular in term rewriting, a path ordering is a well-founded strict total order (>) on the set of all terms such that f(...) > g(s1,...,sn) if f .> g and f(...)
Boolean prime ideal theorem
In mathematics, the Boolean prime ideal theorem states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on sets is known as the ultrafilter l
Bourbaki–Witt theorem
In mathematics, the Bourbaki–Witt theorem in order theory, named after Nicolas Bourbaki and Ernst Witt, is a basic fixed point theorem for partially ordered sets. It states that if X is a non-empty ch
Linked set
In mathematics, an upwards linked set A is a subset of a partially ordered set, P, in which any two of elements A have a common upper bound in P. Similarly, every pair of elements of a downwards linke
In order theory, a branch of mathematics, a semiorder is a type of ordering for items with numerical scores, where items with widely differing scores are compared by their scores and where scores with
Bekić's theorem
In computability theory, Bekić's theorem or Bekić's lemma is a theorem about fixed-points which allows splitting a mutual recursion into recursions on one variable at a time. It was created by Hans Be
In the mathematical field of order theory, an ultrafilter on a given partially ordered set (or "poset") is a certain subset of namely a maximal filter on that is, a proper filter on that cannot be enl
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
Kernel operator
No description available.
In mathematics, majorization is a preorder on vectors of real numbers. For a vector , we denote by the vector with the same components, but sorted in descending order. Given , we say that weakly major
Kleene fixed-point theorem
In the mathematical areas of order and lattice theory, the Kleene fixed-point theorem, named after American mathematician Stephen Cole Kleene, states the following: Kleene Fixed-Point Theorem. Suppose
Hasse diagram
In order theory, a Hasse diagram (/ˈhæsə/; German: [ˈhasə]) is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Co
Kleene–Brouwer order
In descriptive set theory, the Kleene–Brouwer order or Lusin–Sierpiński order is a linear order on finite sequences over some linearly ordered set , that differs from the more commonly used lexicograp
Peck poset
No description available.
Order (journal)
Order (subtitled A Journal on the Theory of Ordered Sets and its Applications) is a quarterly peer-reviewed academic journal on order theory and its applications, published by Springer Science+Busines
Critical pair (order theory)
In order theory, a discipline within mathematics, a critical pair is a pair of elements in a partially ordered set that are incomparable but that could be made comparable without requiring any other c
Closure operator
In mathematics, a closure operator on a set S is a function from the power set of S to itself that satisfies the following conditions for all sets Closure operators are determined by their closed sets
Series-parallel partial order
In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations. The series-paralle
Upper topology
In mathematics, the upper topology on a partially ordered set X is the coarsest topology in which the closure of a singleton is the order section for each If is a partial order, the upper topology is
Dense order
In mathematics, a partial order or total order < on a set is said to be dense if, for all and in for which , there is a in such that . That is, for any two elements, one less than the other, there is
Linear extension
In order theory, a branch of mathematics, a linear extension of a partial order is a total order (or linear order) that is compatible with the partial order. As a classic example, the lexicographic or
Countable chain condition
In order theory, a partially ordered set X is said to satisfy the countable chain condition, or to be ccc, if every strong antichain in X is countable.
Archimedean ordered vector space
In mathematics, specifically in order theory, a binary relation on a vector space over the real or complex numbers is called Archimedean if for all whenever there exists some such that for all positiv
Dushnik–Miller theorem
In mathematics, the Dushnik–Miller theorem is a result in order theory stating that every infinite linear order has a non-identity order embedding into itself. It is named for Ben Dushnik and E. W. Mi
In 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 i
Ordered geometry
Ordered geometry is a form of geometry featuring the concept of intermediacy (or "betweenness") but, like projective geometry, omitting the basic notion of measurement. Ordered geometry is a fundament
Order polynomial
The order polynomial is a polynomial studied in mathematics, in particular in algebraic graph theory and algebraic combinatorics. The order polynomial counts the number of order-preserving maps from a
In mathematics, especially in order theory, the cofinality cf(A) of a partially ordered set A is the least of the cardinalities of the cofinal subsets of A. This definition of cofinality relies on the
Distributive polytope
In the geometry of convex polytopes, a distributive polytope is a convex polytope for which coordinatewise minima and maxima of pairs of points remain within the polytope. For example, this property 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 s
Order embedding
In order theory, a branch of mathematics, an order embedding is a special kind of monotone function, which provides a way to include one partially ordered set into another. Like Galois connections, or
Hausdorff maximal principle
In mathematics, the Hausdorff maximal principle is an alternate and earlier formulation of Zorn's lemma proved by Felix Hausdorff in 1914 (Moore 1982:168). It states that in any partially ordered set,
Infinite descending chain
No description available.
Dehornoy order
In the mathematical area of braid theory, the Dehornoy order is a left-invariant total order on the braid group, found by Patrick Dehornoy. Dehornoy's original discovery of the order on the braid grou
Scott continuity
In mathematics, given two partially ordered sets P and Q, a function f: P → Q between them is Scott-continuous (named after the mathematician Dana Scott) if it preserves all directed suprema. That is,
Ultrafilter (set theory)
In the mathematical field of set theory, an ultrafilter is a maximal proper filter: it is a filter on a given non-empty set which is a certain type of non-empty family of subsets of that is not equal
Alexandrov topology
In topology, an Alexandrov topology is a topology in which the intersection of any family of open sets is open. It is an axiom of topology that the intersection of any finite family of open sets is op
Complete partial order
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 proper
List of order structures in mathematics
In mathematics, and more specifically in order theory, several different types of ordered set have been studied.They include: * Cyclic orders, orderings in which triples of elements are either clockw
Introduction to Lattices and Order
Introduction to Lattices and Order is a mathematical textbook on order theory by Brian A. Davey and Hilary Priestley. It was published by the Cambridge University Press in their Cambridge Mathematical
List of order theory topics
Order theory is a branch of mathematics that studies various kinds of objects (often binary relations) that capture the intuitive notion of ordering, providing a framework for saying when one thing is
Szpilrajn extension theorem
In order theory, the Szpilrajn extension theorem (also called the order-extension principle), proved by Edward Szpilrajn in 1930, states that every strict partial order is contained in a total order.
Ascending chain condition
In mathematics, the ascending chain condition (ACC) and descending chain condition (DCC) are finiteness properties satisfied by some algebraic structures, most importantly ideals in certain commutativ
Pasch's theorem
In geometry, Pasch's theorem, stated in 1882 by the German mathematician Moritz Pasch, is a result in plane geometry which cannot be derived from Euclid's postulates.
Rewrite order
In theoretical computer science, in particular in automated reasoning about formal equations, reduction orderings are used to prevent endless loops. Rewrite orders, and, in turn, rewrite relations, ar
Directed set
In 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
Interval order
In mathematics, especially order theory,the interval order for a collection of intervals on the real lineis the partial order corresponding to their left-to-right precedence relation—one interval, I1,
Ordinal sum
No description available.
Prefix order
In mathematics, especially order theory, a prefix ordered set generalizes the intuitive concept of a tree by introducing the possibility of continuous progress and continuous branching. Natural prefix
Cantor's isomorphism theorem
In order theory and model theory, branches of mathematics, Cantor's isomorphism theorem states that every two countable dense unbounded linear orders are order-isomorphic. It is named after Georg Cant
Ordered topological vector space
In mathematics, specifically in functional analysis and order theory, an ordered topological vector space, also called an ordered TVS, is a topological vector space (TVS) X that has a partial order ≤
Scott domain
In the mathematical fields of order and domain theory, a Scott domain is an algebraic, bounded-complete cpo. They are named in honour of Dana S. Scott, who was the first to study these structures at t
Knaster's condition
In mathematics, a partially ordered set P is said to have Knaster's condition upwards (sometimes property (K)) if any uncountable subset A of P has an upwards-linked uncountable subset. An analogous d
Filter (mathematics)
In mathematics, a filter or order filter is a special subset of a partially ordered set (poset). Filters appear in order and lattice theory, but can also be found in topology, from which they originat
Incidence poset
In mathematics, an incidence poset or incidence order is a type of partially ordered set that represents the incidence relation between vertices and edges of an undirected graph. The incidence poset o
Linear continuum
In the mathematical field of order theory, a continuum or linear continuum is a generalization of the real line. Formally, a linear continuum is a linearly ordered set S of more than one element that
Bounded set
In mathematical analysis and related areas of mathematics, a set is called bounded if it is, in a certain sense, of finite measure. Conversely, a set which is not bounded is called unbounded. The word
Inclusion order
In the mathematical field of order theory, an inclusion order is the partial order that arises as the subset-inclusion relation on some collection of objects. In a simple way, every poset P = (X,≤) is
Schur–Horn theorem
In mathematics, particularly linear algebra, the Schur–Horn theorem, named after Issai Schur and Alfred Horn, characterizes the diagonal of a Hermitian matrix with given eigenvalues. It has inspired i
Solid set
In mathematics, specifically in order theory and functional analysis, a subset of a vector lattice is said to be solid and is called an ideal if for all and if then An ordered vector space whose order
In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup. When some object is said to be embedde
Stone duality
In mathematics, there is an ample supply of categorical dualities between certain categories of topological spaces and categories of partially ordered sets. Today, these dualities are usually collecte
Dilworth's theorem
In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum numbe
Maximal and minimal elements
In 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 o
Greatest element and least element
In mathematics, especially in order theory, the greatest element of a subset of a partially ordered set (poset) is an element of that is greater than every other element of . The term least element is
Specialization (pre)order
In the branch of mathematics known as topology, the specialization (or canonical) preorder is a natural preorder on the set of the points of a topological space. For most spaces that are considered in
Partially ordered group
In abstract algebra, a partially ordered group is a group (G, +) equipped with a partial order "≤" that is translation-invariant; in other words, "≤" has the property that, for all a, b, and g in G, i
Fence (mathematics)
In mathematics, a fence, also called a zigzag poset, is a partially ordered set (poset) in which the order relations form a path with alternating orientations: or A fence may be finite, or it may be f
Encompassment ordering
In theoretical computer science, in particular in automated theorem proving and term rewriting,the containment, or encompassment, preorder (≤) on the set of terms, is defined by s ≤ t if a subterm of
Law of trichotomy
In mathematics, the law of trichotomy states that every real number is either positive, negative, or zero. More generally, a binary relation R on a set X is trichotomous if for all x and y in X, exact
Interval (mathematics)
In mathematics, a (real) interval is a set of real numbers that contains all real numbers lying between any two numbers of the set. For example, the set of numbers x satisfying 0 ≤ x ≤ 1 is an interva
Graded poset
In mathematics, in the branch of combinatorics, a graded poset is a partially-ordered set (poset) P equipped with a rank function ρ from P to the set N of all natural numbers. ρ must satisfy the follo
Topkis's theorem
In mathematical economics, Topkis's theorem is a result that is useful for establishing comparative statics. The theorem allows researchers to understand how the optimal value for a choice variable ch
Bounded complete poset
In the mathematical field of order theory, a partially ordered set is bounded complete if all of its subsets that have some upper bound also have a least upper bound. Such a partial order can also be
Upper set
In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in X) of a partially ordered set is a subset with the following property: if s is in S and if x in X is larg
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitiv
Poset topology
In mathematics, the poset topology associated to a poset (S, ≤) is the Alexandrov topology (open sets are upper sets) on the poset of finite chains of (S, ≤), ordered by inclusion. Let V be a set of v
Order polytope
In mathematics, the order polytope of a finite partially ordered set is a convex polytope defined from the set. The points of the order polytope are the monotonic functions from the given set to the u
Mirsky's theorem
In mathematics, in the areas of order theory and combinatorics, Mirsky's theorem characterizes the height of any finite partially ordered set in terms of a partition of the order into a minimum number
In mathematics, two elements x and y of a set P are said to be comparable with respect to a binary relation ≤ if at least one of x ≤ y or y ≤ x is true. They are called incomparable if they are not co
Serial relation
In set theory a serial relation is a homogeneous relation expressing the connection of an element of a sequence to the following element. The successor function used by Peano to define natural numbers
Infinite divisibility
Infinite divisibility arises in different ways in philosophy, physics, economics, order theory (a branch of mathematics), and probability theory (also a branch of mathematics). One may speak of infini
In the theory of partially ordered sets, a pseudoideal is a subset characterized by a bounding operator LU.
1/3–2/3 conjecture
In order theory, a branch of mathematics, the 1/3–2/3 conjecture states that, if one is comparison sorting a set of items then, no matter what comparisons may have already been performed, it is always
Compact element
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
Separation relation
In mathematics, a separation relation is a formal way to arrange a set of objects in an unoriented circle. It is defined as a quaternary relation S(a, b, c, d) satisfying certain axioms, which is inte
Projection (order theory)
No description available.
Hausdorff gap
In mathematics, a Hausdorff gap consists roughly of two collections of sequences of integers, such that there is no sequence lying between the two collections. The first example was found by Hausdorff
In mathematics, a pantachy or pantachie (from the Greek word πανταχη meaning everywhere) is a maximal totally ordered subset of a partially ordered set, especially a set of equivalence classes of sequ
Fréchet filter
In mathematics, the Fréchet filter, also called the cofinite filter, on a set is a certain collection of subsets of (that is, it is a particular subset of the power set of ). A subset of belongs to th
Join and meet
In mathematics, specifically order theory, the join of a subset of a partially ordered set is the supremum (least upper bound) of denoted and similarly, the meet of is the infimum (greatest lower boun
Teichmüller–Tukey lemma
In mathematics, the Teichmüller–Tukey lemma (sometimes named just Tukey's lemma), named after John Tukey and Oswald Teichmüller, is a lemma that states that every nonempty collection of finite charact
Upper and lower bounds
In mathematics, particularly in order theory, an upper bound or majorant of a subset S of some preordered set (K, ≤) is an element of K that is greater than or equal to every element of S. Dually, a l
Complete Heyting algebra
In mathematics, especially in order theory, a complete Heyting algebra is a Heyting algebra that is complete as a lattice. Complete Heyting algebras are the objects of three different categories; the
Sperner property of a partially ordered set
In order-theoretic mathematics, a graded partially ordered set is said to have the Sperner property (and hence is called a Sperner poset), if no antichain within it is larger than the largest rank lev
Bound graph
In graph theory, a bound graph expresses which pairs of elements of some partially ordered set have an upper bound. Rigorously, any graph G is a bound graph if there exists a partial order ≤ on the ve
Pointwise order
No description available.
Glossary of order theory
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 avail
Cantor–Bernstein theorem
In set theory and order theory, the Cantor–Bernstein theorem states that the cardinality of the second type class, the class of countable order types, equals the cardinality of the continuum. It was u
Shortlex order
In mathematics, and particularly in the theory of formal languages, shortlex is a total ordering for finite sequences of objects that can themselves be totally ordered. In the shortlex ordering, seque
Chain-complete partial order
In mathematics, specifically order theory, a partially ordered set is chain-complete if every chain in it has a least upper bound. It is ω-complete when every increasing sequence of elements (a type o
In combinatorics and order-theoretic mathematics, a multitree may describe either of two equivalent structures: a directed acyclic graph (DAG) in which there is at most one directed path between any t
Nucleus (order theory)
In mathematics, and especially in order theory, a nucleus is a function on a meet-semilattice such that (for every in ): 1. * 2. * 3. * Every nucleus is evidently a monotone function.
In mathematics, a well-order (or well-ordering or well-order relation) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering. The set
Residuated mapping
In mathematics, the concept of a residuated mapping arises in the theory of partially ordered sets. It refines the concept of a monotone function. If A, B are posets, a function f: A → B is defined to
Η set
In mathematics, an η set (Eta set) is a type of totally ordered set introduced by Hausdorff that generalizes the order type η of the rational numbers.
Countryman line
In mathematics, a Countryman line (named after Roger Simmons Countryman Jr.) is an uncountable linear ordering whose square is the union of countably many chains. The existence of Countryman lines was
Facet theory
Facet theory is a metatheory for the multivariate behavioral sciences that posits that scientific theories and measurements can be advanced by discovering relationships between conceptual classificati
Monomial order
In mathematics, a monomial order (sometimes called a term order or an admissible order) is a total order on the set of all (monic) monomials in a given polynomial ring, satisfying the property of resp
In 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) parti
Least-upper-bound property
In mathematics, the least-upper-bound property (sometimes called completeness or supremum property or l.u.b. property) is a fundamental property of the real numbers. More generally, a partially ordere
Completely distributive lattice
In the mathematical area of order theory, a completely distributive lattice is a complete lattice in which arbitrary joins distribute over arbitrary meets. Formally, a complete lattice L is said to be
Boolean differential calculus
Boolean differential calculus (BDC) (German: Boolescher Differentialkalkül (BDK)) is a subject field of Boolean algebra discussing changes of Boolean variables and Boolean functions. Boolean different
Incidence algebra
In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for every locally finite partially ordered setand commutative ring with unity. Subalgebras called reduc
Inversion (discrete mathematics)
In computer science and discrete mathematics, an inversion in a sequence is a pair of elements that are out of their natural order.
Dedekind cut
In mathematics, Dedekind cuts, named after German mathematician Richard Dedekind but previously considered by Joseph Bertrand, are а method of construction of the real numbers from the rational number
Locally finite poset
In mathematics, a locally finite poset is a partially ordered set P such that for all x, y ∈ P, the interval [x, y] consists of finitely many elements. Given a locally finite poset P we can define its
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
Frink ideal
In mathematics, a Frink ideal, introduced by Orrin Frink, is a certain kind of subset of a partially ordered set.
Schnyder's theorem
In graph theory, Schnyder's theorem is a characterization of planar graphs in termsof the order dimension of their incidence posets. It is named after Walter Schnyder, who published its proof in . The
Ranked poset
In mathematics, a ranked partially ordered set or ranked poset may be either: * a graded poset, or * a poset with the property that for every element x, all maximal chains among those with x as grea
Galois connection
In mathematics, especially in order theory, a Galois connection is a particular correspondence (typically) between two partially ordered sets (posets). Galois connections find applications in various
Disjunction property of Wallman
In mathematics, especially in order theory, a partially ordered set with a unique minimal element 0 has the disjunction property of Wallman when for every pair (a, b) of elements of the poset, either
Causal sets
The causal sets program is an approach to quantum gravity. Its founding principles are that spacetime is fundamentally discrete (a collection of discrete spacetime points, called the elements of the c
Order convergence
In mathematics, specifically in order theory and functional analysis, a filter in an order complete vector lattice is order convergent if it contains an order bounded subset (that is, is contained in
Order dimension
In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order.This concept is also sometimes called
Partial cyclic order
In mathematics, a partial cyclic order is a ternary relation that generalizes a cyclic order in the same way that a partial order generalizes a linear order.
Kruskal's tree theorem
In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered under homeomorphic embedding.
Strong antichain
In order theory, a subset A of a partially ordered set P is a strong downwards antichain if it is an antichain in which no two distinct elements have a common lower bound in P, that is, In the case wh
In combinatorics, a greedoid is a type of set system. It arises from the notion of the matroid, which was originally introduced by Whitney in 1935 to study planar graphs and was later used by Edmonds
Order isomorphism
In the mathematical field of order theory, an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets (posets). Whenever t
Scattered order
In mathematical order theory, a scattered order is a linear order that contains no densely ordered subset with more than one element. A characterization due to Hausdorff states that the class of all s
Product order
In mathematics, given two preordered sets and the product order (also called the coordinatewise order or componentwise order) is a partial ordering on the Cartesian product Given two pairs and in decl
Least fixed point
In order theory, a branch of mathematics, the least fixed point (lfp or LFP, sometimes also smallest fixed point) of a function from a partially ordered set to itself is the fixed point which is less
In order theory a better-quasi-ordering or bqo is a quasi-ordering that does not admit a certain type of bad array. Every better-quasi-ordering is a well-quasi-ordering.
Limit-preserving function (order theory)
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
Aronszajn line
In mathematical set theory, an Aronszajn line (named after Nachman Aronszajn) is a linear ordering of cardinality which contains no subset order-isomorphic to * with the usual ordering * the reverse
Laver's theorem
Laver's theorem, in order theory, states that order embeddability of countable total orders is a well-quasi-ordering. That is, for every infinite sequence of totally-ordered countable sets, there exis
Zorn's lemma
Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory. It states that a partially ordered set containing upper bounds for every chain (that is, every totally ordered su
Higman's lemma
In mathematics, Higman's lemma states that the set of finite sequences over a finite alphabet, as partially ordered by the subsequence relation, is well-quasi-ordered. That is, if is an infinite seque
Covering relation
In mathematics, especially order theory, the covering relation of a partially ordered set is the binary relation which holds between comparable elements that are immediate neighbours. The covering rel
In set theory, a prewellordering on a set is a preorder on (a transitive and strongly connected relation on ) that is wellfounded in the sense that the relation is wellfounded. If is a prewellordering
Supermodular function
In mathematics, a function is supermodular if for all , , where denotes the componentwise maximum and the componentwise minimum of and . If −f is supermodular then f is called submodular, and if the i
Möbius inversion formula
In mathematics, the classic Möbius inversion formula is a relation between pairs of arithmetic functions, each defined from the other by sums over divisors. It was introduced into number theory in 183
Prime (order theory)
In mathematics, an element p of a partial order (P, ≤) is a meet prime element when p is the principal element of a principal prime ideal. Equivalently, if P is a lattice, p ≠ top, and for all a, b in
Infimum and supremum
In mathematics, the infimum (abbreviated inf; plural infima) of a subset of a partially ordered set is a greatest element in that is less than or equal to each element of if such an element exists. Co
Filter (set theory)
In mathematics, a filter on a set is a family of subsets such that: 1. * and 2. * if and ,then 3. * If ,and ,then A filter on a set may be thought of as representing a "collection of large subsets"
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 completen
Erdős–Dushnik–Miller theorem
In the mathematical theory of infinite graphs, the Erdős–Dushnik–Miller theorem is a form of Ramsey's theorem stating that every infinite graph contains either a countably infinite independent set, or
Continuous poset
In order theory, a continuous poset is a partially ordered set in which every element is the directed supremum of elements approximating it.
Banach lattice
In the mathematical disciplines of in functional analysis and order theory, a Banach lattice (X,‖·‖) is a complete normed vector space with a lattice order, such that for all x, y ∈ X, the implication
Weak ordering
In mathematics, especially order theory, a weak ordering is a mathematical formalization of the intuitive notion of a ranking of a set, some of whose members may be tied with each other. Weak orders a
Suslin's problem
In mathematics, Suslin's problem is a question about totally ordered sets posed by Mikhail Yakovlevich Suslin and published posthumously.It has been shown to be independent of the standard axiomatic s
Amoeba order
In mathematics, the amoeba order is the partial order of open subsets of 2ω of measure less than 1/2, ordered by reverse inclusion. Amoeba forcing is forcing with the amoeba order; it adds a measure 1
Friedman's SSCG function
In mathematics, a simple subcubic graph (SSCG) is a finite simple graph in which each vertex has degree at most three. Suppose we have a sequence of simple subcubic graphs G1, G2, ... such that each g
In constructive mathematics, a pseudo-order is a constructive generalisation of a linear order to the continuous case. The usual trichotomy law does not hold in the constructive continuum because of i
Order topology (functional analysis)
In mathematics, specifically in order theory and functional analysis, the order topology of an ordered vector space is the finest locally convex topological vector space (TVS) topology on for which ev
Lexicographic order
In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered
Positive linear operator
In mathematics, more specifically in functional analysis, a positive linear operator from an preordered vector space into a preordered vector space is a linear operator on into such that for all posit
Dedekind–MacNeille completion
In mathematics, specifically order theory, the Dedekind–MacNeille completion of a partially ordered set is the smallest complete lattice that contains it. It is named after Holbrook Mann MacNeille who
Cyclic order
In mathematics, a cyclic order is a way to arrange a set of objects in a circle. Unlike most structures in order theory, a cyclic order is not modeled as a binary relation, such as "a < b". One does n
Atom (order theory)
In the mathematical field of order theory, an element a of a partially ordered set with least element 0 is an atom if 0 < a and there is no x such that 0 < x < a. Equivalently, one may define an atom
Cofinal (mathematics)
In mathematics, a subset of a preordered set is said to be cofinal or frequent in if for every it is possible to find an element in that is "larger than " (explicitly, "larger than " means ). Cofinal
Ordered pair
In mathematics, an ordered pair (a, b) is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (a, b) is different from the ordered pair (b, a) unless
In mathematics, quantales are certain partially ordered algebraic structures that generalize locales (point free topologies) as well as various multiplicative lattices of ideals from ring theory and f
Lubell–Yamamoto–Meshalkin inequality
In combinatorial mathematics, the Lubell–Yamamoto–Meshalkin inequality, more commonly known as the LYM inequality, is an inequality on the sizes of sets in a Sperner family, proved by , , , and . It i
Centered set
In mathematics, in the area of order theory, an upwards centered set S is a subset of a partially ordered set, P, such that any finite subset of S has an upper bound in P. Similarly, any finite subset