FACTOID # 21: 15% of Army recruits from South Dakota are Native American, which is roughly the same percentage for female Army recruits in the state.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Order theory

Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering. This article gives a detailed introduction to the field and includes some of the most basic definitions. For a quick lookup of order-theoretic terms, there is also an order theory glossary. A list of order topics collects the various articles in the vicinity of order theory. Mathematics is commonly defined as the study of patterns of structure, change, and space; more informally, one might say it is the study of figures and numbers. Mathematical knowledge is constantly growing, through research and application, but mathematics itself is not usually considered a natural science. ... In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ... 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. ... This is a list of order topics, by Wikipedia page. ...

Contents

Background and motivation

Orders appear everywhere - at least as far as mathematics and related areas, such as computer science, are concerned. The first order that one typically meets in primary school mathematical education is the order ≤ of natural numbers. This intuitive concept is easily extended to orderings of other sets of numbers, such as the integers and the reals. Indeed the idea of being greater or smaller than another number is one of the basic intuitions of number systems in general (although one usually is also interested in the actual difference of two numbers, which is not given by the order). Another familiar example of an ordering is the lexicographic order of words in a dictionary. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Primary or elementary education is the first years of formal, structured education that occurs during childhood. ... Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is... A number is an abstract entity that represents a count or measurement. ... The integers are commonly denoted by the above symbol. ... In mathematics, the real numbers may be described informally in several different ways. ... Difference is the contrary of equality, in particular of objects. ... In mathematics, the lexicographical order, or dictionary order, is a natural order structure of the cartesian product of two ordered sets. ...


The above types of orders have a special property: each element can be compared to any other element, i.e. it is either greater, smaller, or equal. However, this is not always a desired requirement. A well-known example is the subset ordering of sets. If a set A contains all the elements of a set B, then B is said to be smaller than or equal to A. Yet there are sets that cannot be compared in this fashion since each of them contains some elements that are not present in the other. Hence, subset-inclusion is a partial order, as opposed to the total orders given before. A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... In mathematics, a total order, linear order or simple order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ...


Order theory captures the intuition of orders that arises from such examples in a general setting. This is achieved by specifying properties that a relation ≤ must have to be a mathematical order. This more abstract approach makes much sense, because one can derive numerous theorems in the general setting, without focusing on the details of any particular order. These insights can then be readily transferred to many concrete applications. Look up Relation in Wiktionary, the free dictionary In mathematics, a relation is a generalization of arithmetic relations, such as = and <, which occur in statements, such as 5 < 6 or 2 + 2 = 4. See relation (mathematics), binary relation (of set theory and logic) and relational algebra. ...


Driven by the wide practical usage of orders, numerous special kinds of ordered sets have been defined, some of which have grown to mathematical fields of their own. In addition, order theory does not restrict to the various classes of ordering relations, but also considers appropriate functions between them. A simple example of an order theoretic property for functions comes from analysis where monotone functions are found frequently. Partial plot of a function f. ... Functional analysis is the branch of mathematics, and specifically of analysis, concerned with the study of spaces of functions. ... In mathematics, functions between ordered sets are monotonic (or monotone, or even isotone) if they preserve the given order. ...


Basic definitions

This section introduces ordered sets by building upon the concepts of set theory, arithmetics, and binary relations. Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... Arithmetic or arithmetics (from the Greek word &#945;&#961;&#953;&#952;&#956;&#972;&#962; = number) in common usage is a branch of (or the forerunner of) mathematics which records elementary properties of certain operations on numerals, though in usage by professional mathematicians, it often is treated as synonym for number... In mathematics, a binary relation (or a dyadic relation) is an arbitrary association of elements of one set with elements of another (perhaps the same) set. ...


Partially ordered sets

Orders are special binary relations. Suppose that P is a set and that ≤ is a relation on P. Then ≤ is a partial order if it is reflexive, antisymmetric, and transitive, i.e., for all a, b and c in P, we have that: In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In mathematics, especially order theory, a partially ordered set (or poset for short) is a set equipped with a partial order relation. ... In mathematics, a binary relation R on a set X is antisymmetric if, for all a and b in X, if a is related to b and b is related to a, then a = b. ... In mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c. ...

aa (reflexivity)
if ab and ba then a = b (antisymmetry)
if ab and bc then ac (transitivity)

A set with a partial order on it is called a partially ordered set, poset, or just an ordered set if the intended meaning is clear. By checking these properties, one immediately sees that the well-known orders on natural numbers, integers, rational numbers and reals are all orders in the above sense. However, they have the additional property of being total, i.e., for all a and b in P, we have that: In mathematics, a natural number is either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). The former definition is generally used in number theory, while the latter is preferred in set theory and computer science. ... The integers are commonly denoted by the above symbol. ... In mathematics, a rational number (commonly called a fraction) is a ratio or quotient of two integers, usually written as the vulgar fraction a/b, where b is not zero. ... In mathematics, the real numbers may be described informally in several different ways. ... In mathematics, a total order, linear order or simple order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ...

ab or ba (totality)

These orders can also be called linear orders or chains. While many classical orders are linear, the subset order on sets provides an example where this is not the case. Another example is given by the divisibility relation "|". For two natural numbers n and m, we write n|m if n divides m without remainder. One easily sees that this yields a partial order. The identity relation = on any set is also a partial order in which every two elements are incomparable. It is also the only relation that is both a partial order and an equivalence relation. Many advanced properties of posets are mainly interesting for non-linear orders. A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In mathematics, especially in elementary arithmetic, division is an arithmetic operation which is the inverse of multiplication. ... In mathematics, an equivalence relation, denoted by an infix ~, is a binary relation on a set X that is reflexive, symmetric, and transitive. ...


Visualizing a poset

Hasse diagram of the set of all divisors of 60, partially ordered by divisibility
Hasse diagram of the set of all divisors of 60, partially ordered by divisibility

Hasse diagrams can visually represent the elements and relations of a partial ordering. These are graph drawings where the vertices are the elements of the poset and the ordering relation is indicated by both the edges and the relative positioning of the vertices. Orders are drawn bottom-up: if an element x is smaller than (preceeds) y then there exists a path from x to y that is directed upwards. It is often necessary for the edges connecting elements to cross each other, but elements must never be located within an edge. An instructive exercise is to draw the Hasse diagram for the set of natural numbers that are smaller than or equal to 13, ordered by |. Image File history File links Lattice_of_the_divisibility_of_60. ... Image File history File links Lattice_of_the_divisibility_of_60. ... In the mathematical area of order theory, a Hasse diagram (pronounced HAHS uh, named after Helmut Hasse (1898–1979)) is a simple picture of a finite partially ordered set. ... In the mathematical area of order theory, a Hasse diagram (pronounced HAHS uh, named after Helmut Hasse (1898–1979)) is a simple picture of a finite partially ordered set. ... As a branch of Graph theory, Graph drawing applies topology and geometry to derive visual and haptic representations of graphs. ... In geometry, a vertex (Latin: whirl, whirlpool; plural vertices) is a corner of a polygon (where two sides meet) or of a polyhedron (where three or more faces and an equal number of edges meet). ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ...


Even some infinite sets can be diagrammed by superimposing an ellipsis (...) on a finite sub-order. This works well for the natural numbers, but it fails for the reals, where there is no immediate successor above 0. However, quite often one can obtain an intuition related to diagrams of a similar kind. It has been suggested that Elliptical construction be merged into this article or section. ...


Special elements within an order

In a partially ordered set there may be some elements that play a special role. The most basic example is given by the least element of a poset. For example, 1 is the least element of the positive integers and the empty set is the least set under the subset order. Formally, an element m is a least element if: 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 mathematics and more specifically set theory, the empty set is the unique set which contains no elements. ...

ma, for all elements a of the order.

The notation 0 is frequently found for the least element, even when no numbers are concerned. However, in orders on sets of numbers, this notation might be inappropriate or ambiguous, since the number 0 is not always least. An example is given by the above divisibility order |, where 1 is the least element since it divides all other numbers. On the other hand, 0 is the number that is divided by all other numbers. Hence it is the greatest element of the order! Other frequent terms for the least and greatest elements is bottom and top or zero and unit. Least and greatest elements may fail to exist, as the example of the real numbers shows. 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. ...


On the other hand, if they exist, least and greatest elements are always unique. In contrast, consider the divisibility relation | on the set {2,3,4,5,6}. Although this set has neither top nor bottom, the elements 2, 3, and 5 do not have any elements below them, while 4, 5, and 6 have no other number above. Such elements are called minimal and maximal, respectively. Formally, an element m is minimal if: In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually. ... In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually. ...

am implies a = m, for all elements a of the order.

Exchanging ≤ with ≥ yields the definition of maximality. As the example shows, there can be many maximal elements and some elements may be both maximal and minimal (e.g. 5 above). However, if there is a least element, then it is the only minimal element of the order. Again, in infinite posets maximal elements do not always exist - the set of all finite subsets of a given infinite set, ordered by subset inclusion, provides one out of many counterexamples. An important tool to ensure the existence of maximal elements under certain conditions is Zorn's Lemma. Zorns lemma, also known as the Kuratowski-Zorn lemma, is a proposition of set theory that states: Every non-empty partially ordered set in which every chain (i. ...


Subsets of partially ordered sets inherit the order. We already applied this by considering the subset {2,3,4,5,6} of the natural numbers with the induced divisibility ordering. Now there are also elements of a poset that are special with respect to some subset of the order. This leads to the definition of upper bounds. Given a subset S of some poset P, an upper bound of S is an element b of P that is above all elements of S. Formally, this means that In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element which is greater than or equal to every element of S. The term lower bound is defined dually. ...

sb, for all s in S.

Lower bounds again are defined by inverting the order. For example, -5 is a lower bound of the natural numbers as a subset of the integers. Given a set of sets, an upper bound for these sets under the subset ordering is given by their union. In fact, this upper bound is quite special: it is the smallest set that contains all of the sets. Hence, we have found the least upper bound of a set of sets. This concept is also called supremum or join, and for a set S one writes sup(S) or vS for its least upper bound. Conversely, the greatest lower bound is known as infimum or meet and denoted inf(S) or ^S. These concepts play an important role in many applications of order theory. For two elements x and y, one also writes x v y and x ^ y for sup({x,y}) and inf({x,y}), respectively. (Using Wikipedia's TeX markup, one can also write vee and wedge, as well as the larger symbols bigvee and bigwedge. Note however, that all of these symbols may fail to match the font size of the standard text and should therefore preferably be used in extra lines. The rendering of ∨ for v and ∧ for ^ is not supported by many of today's web browsers across all platforms and therefore avoided here.) In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ... In mathematics, the supremum of an ordered set S is the least element (not necessarily in S) which is greater than or equal to each element of S. Consequently, it is also referred to as the least upper bound. ... In mathematics the infimum of a subset of some set is the greatest element, not necessarily in the subset, that is smaller than all other elements of the subset. ... An example of a web browser (Mozilla Firefox running under Microsoft Windows). ...


For another example, consider again the relation | on natural numbers. The least upper bound of two numbers is the smallest number that is divided by both of them, i.e. the least common multiple of the numbers. Greatest lower bounds in turn are given by the greatest common divisor. In arithmetic and number theory the least common multiple or lowest common multiple (lcm) or smallest common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b. ... In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers. ...


Duality

In the previous definitions, we often noted that a concept can be defined by just inverting the ordering in a former definition. This is the case for "least" and "greatest", for "minimal" and "maximal", for "upper bound" and "lower bound", and so on. This is a general situation in order theory: A given order can be inverted by just exchanging its direction, pictorially flipping the Hasse diagram top-down. This yields the so-called dual, inverse, or opposite order.


Every order theoretic definition has its dual: it is the notion one obtains by applying the definition to the inverse order. Since the symmetry of all concepts, this operation preserves the theorems of partial orders. For a given mathematical result, one can just invert the order and replace all definitions by their duals and one obtains another valid theorem. This is important and useful, since one obtains two theorems for the price of one. Some more details and examples can be found in the article on duality in 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. ...


Constructing new orders

There are many ways to construct orders out of given orders. The dual order is one example. Another important construction is the cartesian product of two partially ordered sets, taken together with the product order on pairs of elements. The ordering is defined by (a, x) ≤ (b, y) if (and only if) ab and xy. (Notice carefully that there are three distinct meanings for the relation symbol ≤ in this definition.) The disjoint union of two posets is another typical example of order construction, where the order is just the (disjoint) union of the original orders. In mathematics, the Cartesian product (or direct product) of two sets X and Y, denoted X × Y, is the set of all possible ordered pairs whose first component is a member of X and whose second component is a member of Y: The Cartesian product is named after René Descartes... In mathematics, given two ordered sets A and B, one can induce an ordering on the Cartesian product A × B. Given two pairs (a1,b1) and (a2,b2) in A × B, one sets (a1,b1) &#8804; (a2,b2) if and only if a1 &#8804; a2 and b1 &#8804; b2. ... In set theory, a disjoint union (or discriminated union) is a union of a collection of sets whose members are pairwise disjoint. ...


Every partial order ≤ gives rise to a so-called strict order <, by defining a < b if ab and not ba. This transformation can be inverted by setting ab if a < b or a = b. The two concepts are equivalent although in some circumstances one can be more convenient to work with than the other. A strict weak ordering is a binary relation that defines an equivalence relation and has the properties stated below. ...


Functions between orders

It is reasonable to consider functions between partially ordered sets having certain additional properties, that are related to the ordering relations of the two sets. The most fundamental condition that occurs in this context is monotonicity. A function f from a poset P to a poset Q is monotone, or order-preserving, if ab in P implies f(a) ≤ f(b) in Q (Noting that, strictly, the two relations here are different since they apply to different sets.). The converse of this implication leads to functions that are order-reflecting, i.e. functions f as above for which f(a) ≤ f(b) implies ab. On the other hand, a function may also be order-reversing or antitone, if ab implies f(b) ≤ f(a). In mathematics, functions between ordered sets are monotonic (or monotone, or even isotone) if they preserve the given order. ...


An order-embedding is a function f between orders that is both order-preserving and order-reflecting. Examples for these definitions are found easily. For instance, the function that maps a natural number to its successor is clearly monotone with respect to the natural order. Any function from a discrete order, i.e. from a set ordered by the identity order "=", is also monotone. Mapping each natural number to the corresponding real number gives an example for an order embedding. The set complement on a powerset is an example of an antitone function. In mathematical order theory, an order-embedding is a special kind of monotone function, which provides a way to include one partially ordered set into another. ... In set theory and other branches of mathematics, two kinds of complements are defined, the relative complement and the absolute complement. ... 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. ...


An important question is when two orders are "essentially equal", i.e. when they are the same up to renaming of elements. Order isomorphisms are functions that define such a renaming. An order-isomorphism is a monotone bijective function that has a monotone inverse. This is equivalent to being a surjective order-embedding. Hence, the image f(P) of an order-embedding is always isomorphic to P, which justifies the term "embedding". 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. ... In mathematics, a bijection, bijective function, or one-to-one correspondence is a function that is both injective (one-to-one) and surjective (onto), and therefore bijections are also called one_to_one and onto. ... In mathematics, a surjective function (or onto function or surjection) is a function with the property that all possible output values of the function are generated when the input ranges over all the values in the domain. ...


A more elaborate type of functions is given by so-called Galois connections. Monotone Galois connections can be viewed as a generalization of order-isomorphisms, since they constitute of a pair of two functions in converse directions, which are "not quite" inverse to each other, but that still have close relationships. In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets (posets). Galois connections generalize the correspondence between subgroups and subfields investigated in Galois theory. ...


Another special type of self-maps on a poset are closure operators, which are not only monotonic, but also idempotent, i.e. f(x) = f(f(x)), and extensive (or inflationary), i.e. xf(x). These have many applications in all kinds of "closures" that appear in mathematics. In mathematics, given a partially ordered set (P, ≤), a closure operator on P is a function C : P → P with the following properties: x ≤ C(x) for all x, i. ... In mathematics, an idempotent element is an element which, intuitively, leaves something unchanged. ...


Besides being compatible with the mere order relations, functions between posets may also behave well with respect to special elements and constructions. For example, when talking about posets with least element, it may seem reasonable to consider only monotonic functions that preserve this element, i.e. which map least elements to least elements. If binary infima ^ exist, then a reasonable property might be to require that f(x^y) = f(x)^f(y), for all x and y. All of these properties, and indeed many more, may be compiled under the label of limit-preserving functions. In the mathematical area of order theory, one often speaks about functions that preserve certain limits, i. ...


Finally, one can invert the view, switching from functions of orders to orders of functions. Indeed, the functions between two posets P and Q can be ordered via the pointwise order. For two functions f and g, we have fg if f(x) ≤ g(x) for all elements x of P. This occurs for example in domain theory, where function spaces play an important role. Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. ... In mathematics, a function space is a set of functions of a given kind from a set X to a set Y. It is called a space because in many applications, it is a topological space or a vector space or both. ...


Special types of orders

Many of the structures that are studied in order theory employ order relations with further properties. In fact, even some relations that are not partial orders are of special interest. Mainly the concept of a preorder has to be mentioned. A preorder is a relation that is reflexive and transitive, but not necessarily antisymmetric. Each preorder induces an equivalence relation between elements, where a is equivalent to b, if ab and ab. Preorders can be turned into orders by identifying all elements that are equivalent with respect to this relation. In mathematics, especially in order theory, preorders are certain kinds of binary relations that are closely related to partially ordered sets. ... In mathematics, an equivalence relation, denoted by an infix ~, is a binary relation on a set X that is reflexive, symmetric, and transitive. ...


Basic types of special orders have already been given in form of total orders. An additional simple but useful property leads to so-called well-orders, within which all non-empty subsets have a least element, or equivalently in which there is no infinite descending sequence of distinct elements. For partial orders, a similar definition leads to well partial orders, where in addition to having no infinite descending chains there are no infinite antichains. In mathematics, a well-order (or well-ordering) 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. ... In mathematics, a well partial order is a partial order &#8804; with the property that, for any infinite sequence x1, x2, x3. ... Let S be a partially ordered set. ...


Many other types of orders arise when the existence of infima and suprema of certain sets is guaranteed. Focusing on this aspect, usually referred to as completeness of orders, one obtains: In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set. ...

However, one can go even further: if all finite non-empty infima exist, then ^ can be viewed as a total binary operation in the sense of universal algebra. Hence, in a lattice, two operations ^ and v are available, and one can define new properties by giving identities, such as In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set (poset) 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 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 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 mathematics and more specifically set theory, the empty set is the unique set which contains no elements. ... The name lattice is suggested by the form of the Hasse diagram depicting it. ... 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, directed complete partial orders and complete partial orders are special classes of partially ordered sets. ... In mathematics, a directed set is a set A together with a binary relation &#8804; having the following properties: a &#8804; a for all a in A (reflexivity) if a &#8804; b and b &#8804; c, then a &#8804; c (transitivity) for any two a and b in A, there... Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. ... Universal algebra is the field of mathematics that studies the ideas common to all algebraic structures. ...

x ^ (y v z)  =  (x ^ y) v (x ^ z), for all x, y, and z.

This condition is called distributivity and gives rise to distributive lattices. There are some other important distributivity laws which are discussed in the article on distributivity in order theory. Some additional order structures that are often specified via algebraic operations and defining identities are In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. ... 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. ...

which both introduce a new operation ~ called negation. Both structures play a role in mathematical logic and especially Boolean algebras have major applications in computer science. Finally, various structures in mathematics combine orders with even more algebraic operations, as in the case of quantales, that allow for the definition of an addition operation. In mathematics, Heyting algebras are special partially ordered sets that constitute a generalization of Boolean algebras. ... In abstract algebra, a Boolean algebra is an algebraic structure (a collection of elements and operations on them obeying defining axioms) that captures essential properties of both set operations and logic operations. ... Mathematical logic is a discipline within mathematics, studying formal systems in relation to the way they encode intuitive concepts of proof and computation as part of the foundations of mathematics. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In mathematics, quantales are certain partially ordered algebraic structures which generalize frames (pointless topologies) as well as various lattices of multiplicative ideals from ring theory and functional analysis (C*-algebras, von Neumann algebras). ...


Many other important properties of posets exist. For example, a poset is locally finite if every closed interval [a, b] in it is finite. Locally finite posets give rise to incidence algebras which in turn can be used to define the Euler characteristic of finite bounded posets. In mathematics, interval is a concept relating to the sequence and set-membership of one or more numbers. ... 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 order theory, a field of mathematics, a locally finite partially ordered set is one for which every closed interval [a, b] = {x : a &#8804; x &#8804; b} within it is finite. ...


Subsets of ordered sets

In an ordered set, one can define many types of special subsets based on the given order. A simple example are upper sets; i.e. sets that contain all elements that are above them in the order. Formally, the upper closure of a set S in a poset P is given by the set {x in P | there is some y in S with yx}. A set that is equal to its upper closure is called an upper set. Lower sets are defined dually.


More complicated lower subsets are ideals, which have the additional property that each two of their elements have an upper bound within the ideal. Their duals are given by filters. A related concept is that of a directed subset, which like an ideal contains upper bounds of finite subsets, but does not have to be a lower set. Furthermore it is often generalized to preordered sets. In mathematical order theory, an ideal is a special subset of a partially ordered set. ... In mathematics, a filter is a special subset of a partially ordered set. ... In mathematics, a directed set is a set A together with a binary relation &#8804; having the following properties: a &#8804; a for all a in A (reflexivity) if a &#8804; b and b &#8804; c, then a &#8804; c (transitivity) for any two a and b in A, there...


A subset which is - as a sub-poset - linearly ordered, is called a chain. The opposite notion, the antichain, is a subset that contains no two comparable elements; i.e. that is a discrete order.


Related mathematical areas

Although most mathematical areas use orders in one or the other way, there are also a few theories that have relationships which go far beyond mere application. Together with their major touching points with order theory, some of these are to be presented below.


Universal algebra

As already mentioned, the methods and formalisms of universal algebra are an important tool for many order theoretic considerations. Beside formalizing orders in terms of algebraic structures that satisfy certain identities, one can also establish other connections to algebra. An example is given by the correspondence between Boolean algebras and Boolean rings. Other issues are concerned with the existence of free constructions, such as free lattices based on a given set of generators. Furthermore, closure operators are important in the study of universal algebra. Universal algebra is the field of mathematics that studies the ideas common to all algebraic structures. ... In abstract algebra, a Boolean algebra is an algebraic structure (a collection of elements and operations on them obeying defining axioms) that captures essential properties of both set operations and logic operations. ... In mathematics, a Boolean ring R is a ring for which x2 = x for all x in R; that is, R consists of idempotent elements. ...


Topology

In topology orders play a very prominent role. In fact, the set of open sets provides a classical example of a complete lattice, more precisely a complete Heyting algebra (or "frame" or "locale"). Filters and nets are notions closely related to order theory and the closure operator of sets can be used to define topology. Beyond these relations, topology can be looked at solely in terms of the open set lattices, which leads to the study of pointless topology. Furthermore, a natural preorder of elements of the underlying set of a topology is given by the so-called specialization order, that is actually a partial order if the topology is T0. A Möbius strip, a surface with only one side and one edge; such shapes are an object of study in topology. ... 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... In mathematics, a filter is a special subset of a partially ordered set. ... In topology and related areas of mathematics a net or Moore-Smith sequence is a generalization of a sequence, intended to unify the various notions of limit and generalize them to arbitrary topological spaces. ... In topology and related branches of mathematics, a closed set is a set whose complement is open. ... Pointless topology is an approach to topology which avoids the mentioning of points. ... In the branch of mathematics known as topology the specialization (or canonical) preorder defines a preorder on the set of the points of a topological space. ... In topology and related branches of mathematics, the T0 spaces or Kolmogorov spaces form a broad class of well behaved topological spaces. ...


Conversely, in order theory, one often makes use of topological results. There are various ways to define subsets of an order which can be considered as open sets of a topology. Especially, it is interesting to consider topologies on a poset (X, ≤) that in turn induce ≤ as their specialization order. The finest such topology is the Alexandrov topology, given by taking all upper sets as opens. Conversely, the coarsest topology that induces the specialization order is the upper topology, having the complements of principal ideals (i.e. sets of the form {y in X | yx} for some x) as a subbase. Additionally, a topology with specialization order ≤ may be order consistent, meaning that their open sets are "inaccessible by directed suprema" (with respect to ≤). The finest order consistent topology is the Scott topology, which is coarser than the Alexandrov topology. A third important topology in this spirit is the Lawson topology. There are close connections between these topologies and the concepts of order theory. For example, a function preserves directed suprema iff it is continuous with respect to the Scott topology (for this reason this order theoretic property is also called Scott-continuity). In general topology the open sets of a topological space satisfy by definition the conditions: The union of arbitrarily many open sets is open. ... In mathematics, the upper topology is the topology defined on a preordered set, in which the open sets are the up-sets. ... In mathematical order theory, an ideal is a special subset of a partially ordered set. ... In topology, a subbase (or subbasis) for a topological space X with topology T is a subcollection B of T which generates T, in the sense that T is the smallest topology containing B. A slightly different definition is used by some authors, and there are other useful equivalent formulations... 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. ... IFF, Iff or iff can stand for: Interchange File Format - a computer file format introduced by Electronic Arts Identification, friend or foe - a radio based identification system utilizing transponders iff - the mathematics concept if and only if International Flavors and Fragrances - a company producing flavors and fragrances International Freedom Foundation... In topology and related areas of mathematics a continuous function is a morphism between topological spaces. ... A monotone function f : P &#8594; Q between posets P and Q is Scott-continuous if, for every directed set D that has a supremum sup D in P, the set {fx | x in D} has the supremum f(sup D) in Q. Stated differently, a Scott-continuous function is...


Category theory

The visualization of orders with Hasse diagrams has a straightforward generalization: instead of displaying lesser elements below greater ones, the direction of the order can also be depicted by giving directions to the edges of a graph. In this way, each order is seen to be equivalent to a directed acyclic graph, where the nodes are the elements of the poset and there is a directed path from a to b if and only if ab. Dropping the requirement of being acyclic, one can also obtain all preorders. A simple directed acyclic graph In computer science and mathematics, a directed acyclic graph, also called a dag or DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no nonempty directed path starting and ending on v. ...


When equipped with all transitive edges, these graphs in turn are just special categories, where elements are objects and each set of morphisms between two elements is at most singleton. Functions between orders become functors between categories. Interestingly, many ideas of order theory are just concepts of category theory in small. For example, an infimum is just a categorical product. More generally, one can capture suprema and infima under the abstract notion of a categorical limit (or colimit, respectively). Another place where categorical ideas occur is the concept of a (monotone) Galois connection, which is just the same as a pair of adjoint functors. In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ... In category theory, one defines products to generalize constructions such as the cartesian product of sets, the product of groups, the product of rings and the product of topological spaces. ... In category theory, a branch of mathematics, the abstract notion of a limit captures the essential properties of universal constructions that are used in various parts of mathematics, like products and inverse limits. ... In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets (posets). Galois connections generalize the correspondence between subgroups and subfields investigated in Galois theory. ... The existence of many pairs of adjoint functors is a major observation of the branch of mathematics known as category theory. ...


But category theory also has its impact on order theory on a larger scale. Classes of posets with appropriate functions as discussed above form interesting categories. Often one can also state constructions of orders, like the product order, in terms of categories. Further insights result when categories of orders are found categorically equivalent to other categories, for example of topological spaces. This line of research leads to various representation theorems, often collected under the label of Stone duality. In mathematics, given two ordered sets A and B, one can induce an ordering on the Cartesian product A × B. Given two pairs (a1,b1) and (a2,b2) in A × B, one sets (a1,b1) &#8804; (a2,b2) if and only if a1 &#8804; a2 and b1 &#8804; b2. ... In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are essentially the same. There are numerous examples of categorical equivalences from many areas of mathematics. ... In mathematics, especially in topology and order theory, there is an ample supply of categorical dualities between certain categories of topological spaces and categories of partially ordered sets. ...


History

As explained before, orders are ubiquitous in mathematics. However, earliest explicit mentionings of partial orders are probably to be found not before the 19th century. In this context the works of George Boole are of great importance. Moreover, works of Charles S. Peirce, Richard Dedekind, and Ernst Schröder also consider concepts of order theory. Certainly, there are others to be named in this context and surely there exists more detailed material on the history of order theory. Please contribute if any further knowledge is available to you. George Boole [], (November 2, 1815 – December 8, 1864) was a British mathematician and philosopher. ... Charles Sanders Peirce Charles Sanders Peirce (September 10, 1839 &#8211; April 19, 1914) was an American logician, philosopher, scientist, and mathematician. ... Richard Dedekind Julius Wilhelm Richard Dedekind (October 6, 1831 – February 12, 1916) was a German mathematician who did important work in abstract algebra and the foundations of the real numbers. ... Ernst Schröder Ernst Schröder (25 November 1841 Mannheim, Germany - 16 June 1902 Karlsruhe Germany) was a German mathematician mainly known for his work on algebraic logic. ...


The term poset as an abbreviation for partially ordered set was coined by Garrett Birkhoff, a fact that, according to Earliest Known Uses of Some of the Words of Mathematics,[1] is stated on page 1 of the second edition of his influential book Lattice Theory.[2] Garrett Birkhoff (January 19, 1911, Princeton, New Jersey, USA - November 22, 1996, Water Mill, New York, USA) was an American mathematician. ...


See also

In mathematics, a cyclic order on a set X with n elements is an arrangement of X as on a clock face, for an n-hour clock. ... In order theory, a field of mathematics, a locally finite partially ordered set is one for which every closed interval [a, b] = {x : a &#8804; x &#8804; b} within it is finite. ... This is a list of order topics, by Wikipedia page. ... The classical Möbius function is an important multiplicative function in number theory and combinatorics. ... In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... A strict weak ordering is a binary relation that defines an equivalence relation and has the properties stated below. ... In mathematics, a total order, linear order or simple order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... This is a list of important publications in mathematics, organized by field. ...

References

  1. ^ http://members.aol.com/jeff570/mathword.html
  2. ^ (1948) Lattice Theory, volume 25. New York: Amer. Math. Soc. Coll. Publ..
  • B. A. Davey and H. A. Priestley, 2002. Introduction to Lattices and Order, 2nd ed. Cambridge University Press. ISBN 0-521-78451-4
A good contemporary introduction to the subject. Suitable for undergraduates.
  • G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, and D. S. Scott, 2003, "Continuous Lattices and Domains," in Encyclopedia of Mathematics and its Applications, Vol. 93, Cambridge University Press. ISBN 0-521-80338-1
The comprehensive new version of the famous "Compendium" of continuous lattices. Assumes some advanced mathematical background.
  • S. N. Burris and H. P. Sankappanavar, 1981. A Course in Universal Algebra. Springer Verlag.
A free online introduction to universal algebra, with much material on lattices.

External links

  • Orders at ProvenMath partial order, linear order, well order, initial segment; formal definitions and proofs within the axioms of set theory.

  Results from FactBites:
 
order theory: Information from Answers.com (4046 words)
Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of a mathematical ordering.
These are graph drawings where the vertices are the elements of the poset and the ordering relation is indicated by both the edges and the relative positioning of the vertices.
Directed complete partial orders (dcpos), that guarantee the existence of suprema of all directed subsets and that are studied in domain theory.
Order theory - Wikipedia, the free encyclopedia (3937 words)
Orders appear everywhere - at least as far as mathematics and related areas, such as computer science, are concerned.
The first order that one typically meets in primary school mathematical education is the order of natural numbers.
Order theory captures the intuition of orders that arises from such examples in a general setting.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m