| Order Theory |
Article Index for Order |
Website Links For Order |
Information AboutOrder Theory |
| CATEGORIES ABOUT ORDER THEORY | |
| order theoryorder theory | |
| combinatorics | |
| category theory | |
| ordering | |
|
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 Number s, such as the Integer s 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. 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 Set s. 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. 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. 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. INTRODUCTION TO THE BASIC DEFINITIONS This section aims at giving a first guide to the realm of ordered sets. It addresses readers who have basic knowledge of Set Theory and Arithmetics and who know what a Binary Relation is, but who are not familiar with order theoretic considerations so far. Partially ordered sets As already hinted at above, orders are special binary relations. Hence consider some Set ''P'' and 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: a : if ''a'' ≤ ''b'' and ''b'' ≤ ''a'' then ''a'' = ''b'' (antisymmetry) : if ''a'' ≤ ''b'' and ''b'' ≤ ''c'' then ''a'' ≤ ''c'' (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 Number s, Integer s, Rational Number s and Reals are all orders in the above sense. However, they have the additional property of being ''' Total ''', i.e., for all distinct ''a'' and ''b'' in ''P'', we have that: a These orders can also be called linear orders or '''chains'''. While many classical orders are linear, the Subset order on Set s provides an example where this is not the case. In fact, many advanced properties of posets are mainly interesting for non-linear orders. Visualizing orders Before proceeding to further examples and definitions, it will be helpful to display orders in a convenient graphical way, in order to provide "pictures" that one can have in mind (or on paper) when trying to understand the more abstract concepts. For this purpose, so-called Hasse Diagram s have been introduced. These are Graph s where the Vertices are the elements of the poset and the ordering relation is indicated by both the Edge s and the relative positioning of the vertices. Orders are drawn bottom-up: if an element ''x'' is smaller than ''y'' then there exists a path from ''x'' to ''y'' that is directed upwards. It is often needed that connections between points intersect each other, but points must never be located at the direct connection between two other points. Even infinite sets can sometimes be illustrated by similar diagrams, using an Ellipsis (...) after drawing a sufficiently instructive 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. The above orders are all very common in mathematics. However, there are also examples that one does often not consider as orders. For instance, the identity relation = on any set is a partial order. Within this order, every two elements are incomparable. It is also the only relation that is both a partial order and an Equivalence Relation . The Hasse diagram of such a discrete order is just a collection of labeled points, without any edges between them. | ||
| 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 ''' | "http://wwwinformationdelightinfo/encyclopedia/entry/greatest_element" class="copylinks">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 |
|
| 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 ''' | "http://wwwinformationdelightinfo/encyclopedia/entry/minimal_element" class="copylinks">Minimal ''' and ''' Maximal ''', respectively Formally, an element ''m'' is minimal if: |
|
| 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, Ie The | "http://wwwinformationdelightinfo/encyclopedia/entry/least_common_multiple" class="copylinks">Least Common Multiple of the numbers Greatest lower bounds in turn are given by the Greatest Common Divisor |
|
| 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 | "http://wwwinformationdelightinfo/encyclopedia/entry/Alexandrov_topology" class="copylinks">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 (ie sets of the form {''y'' in ''X'' ''y'' ≤ ''x''} 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 ) |
|
|