Teori order

Teori order (Inggris: order theory) atau teori tatanan (= teori keteraturan) adalah suatu cabang matematika yang meneliti pandangan intuitif manusia terhadap tatanan atau keteraturan dengan menggunakan hubungan biner. Teori ini memberikan kerangka formal untuk mengungkapkan pernyataan-pernyataan seperti "ini lebih kecil dari itu" atau "ini mendahului itu". Dalam artikel ini diperkenalkan bidang ini dan memberikan definisi dasar.

Latar belakang dan motivasi

Tatanan dapat dijumpai di mana-mana dalam matematika atau bidang-bidang terkait seperti sains komputer. Tatanan pertama yang sering didiskusikan dalam sekolah dasar adalah tatanan baku pada bilangan asli misalnya "2 lebih kecil dari 3", "10 lebih besar dari 5", atau "Apakah Toto mempunyai lebih sedikit kue daripada Siti?". Konsep intuitif ini dapat dikembangkan kepada tatanan-tatanan dalam himpunan bilangan yang lain, seperti bilangan bulat dan bilangan real. Konsep "lebih besar dari" atau "lebih kecil dari" suatu bilangan lain adalah salah satu intuisi dasar dalam sistem bilangan secara umum, meskipun orang juga tertarik untuk mengetahui perbedaan (yaitu pengurangan) dua bilangan, yang tidak diberikan oleh tatanan. Contoh umum lain adalah tatanan (atau urutan leksikografi) kata-kata dalam suatu kamus.

Definisi dasar

Bagian ini memperkenalkan sejumlah himpunan tertata yang dibangun di atas konsep-konsep teori himpunan, aritmetika, dan relasi biner.

Himpunan dengan tatanan parsial

Tatanan merupakan relasi biner khusus. Misalkan P adalah suatu himpunan dan ≤ adalah relasi terhadap P, maka ≤ merupakan "tatanan parsial" (partial order) jika bersifat refleksif, antisimetri, dan transitif, yaitu untuk setiap a, b dan c dalam P, didapatkan:

a ≤ a (refleksivitas)

jika a ≤ b dan b ≤ a maka a = b (antisimetri)

jika a ≤ b dan b ≤ c maka a ≤ c (transitivitas).

Suatu himpunan dengan tatanan parsial di dalamnya dikatakan himpunan dengan tatanan parsial (partially ordered set), poset, atau hanya himpunan tertata (ordered set) jika maknanya sudah jelas. Dengan memandang sifat-sifat ini, langsung dapat dilihat tatanan yang sudah dikenal dalam bilangan asli, bilangan bulat, bilangan rasional dan bilangan real yang semuanya adalah tatanan dalam makna di atas. Namun, ada juga sifat tambahan tatanan total (total order), yaitu untuk setiap a dan b dalam P, didapatkan:

a ≤ b atau b ≤ a (totalitas).

Tatanan-tatanan ini dapat juga disebut tatanan linear (linear order) atau rantai (chain). Banyak tatanan klasik bersifat linear, tetapi tatanan subset pada himpunan memberi contoh kapan hal ini tidak benar. Contoh lain dapat diberikan dari relasi divisibilitas "|". Untuk dua bilangan asli n dan m, ditulis n|m jika n dibagi oleh m tanpa sisa. Dapat dengan mudah dilihat bahwa ini menghasilkan tatanan parsial.

Elemen khusus dalam suatu tatanan

Dalam suatu himpunan dengan tatanan parsial ada sejumlah elemen yang berperan penting. Contoh paling dasar adalah "elemen terkecil" dalam suatu poset. Misalnya, 1 adalah elemen terkecil dari bilangan bulat positif dan himpunan kosong adalah himpunan terkecil di bawah tatanan subset. Secara formal, suatu elemen m merupakan elemen terkecil jika:

m ≤ a, untuk semua elemen a dalam tatanan itu.

Notasi 0 sering dijumpai pada elemen terkecil, meskipun tidak melibatkan bilangan apapun. Namun, dalam tatanan suatu himpunan bilangan, notasi ini tidak tepat dan bahkan menimbulkan kerancuan, karena bilangan 0 tidak selalu yang terkecil. Contohnya adalah pada tatanan divisibilitas |, di mana 1 adalah elemen terkecil karena bilangan itu membangi semua bilangan yang lain. Sebaliknya, bilangan 0 merupakan bilangan yang dapat dibagi oleh semua bilangan lain. Jadi bilangan 0 merupakan elemen terbesar dari tatanan tersebut. Istilah lain untuk "terkecil" dan "terbesar" adalah "terendah" ("terbawah", "paling dasar"; bottom) dan "tertinggi" ("teratas"; top) dan juga "nol" (zero) dan "unit" ("satuan").

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.

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 all concepts are symmetric, 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.

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) a ≤ b and x ≤ y. (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.

Every partial order ≤ gives rise to a so-called strict order <, by defining a < b if a ≤ b and not b ≤ a. This transformation can be inverted by setting a ≤ b 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.

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 a ≤ b 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 a ≤ b. On the other hand, a function may also be order-reversing or antitone, if a ≤ b implies f(b) ≤ f(a).

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.

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".

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.

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. x ≤ f(x). These have many applications in all kinds of "closures" that appear in mathematics.

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.

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 f ≤ g 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.

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 a ≤ b and b ≤ a. Preorders can be turned into orders by identifying all elements that are equivalent with respect to this relation.

Several types of orders can be defined from numerical data on the items of the order: a total order results from attaching distinct real numbers to each item and using the numerical comparisons to order the items; instead, if distinct items are allowed to have equal numerical scores, one obtains a strict weak ordering. Requiring two scores to be separated by a fixed threshold before they may be compared leads to the concept of a semiorder, while allowing the threshold to vary on a per-item basis produces an interval order.

An additional simple but useful property leads to so-called well-orders, for which all non-empty subsets have a minimal element. Generalizing well-orders from linear to partial orders, a set is well partially ordered if all its non-empty subsets have a finite number of minimal elements.

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:

• Bounded posets, i.e. posets with a least and greatest element (which are just the supremum and infimum of the empty subset),
• Lattices, in which every non-empty finite set has a supremum and infimum,
• Complete lattices, where every set has a supremum and infimum, and
• Directed complete partial orders (dcpos), that guarantee the existence of suprema of all directed subsets and that are studied in domain theory.
• Partial orders with complements, or poc sets, are posets S having a unique bottom element 0∈S, along with an order-reversing involution, such that $a\leq a^{*}\Rightarrow a=0$.

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 ∨ are available, and one can define new properties by giving identities, such as

x ∧ (y ∨ z)  =  (x ∧ y) ∨ (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

• Heyting algebras and
• Boolean algebras,

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.

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.

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 y ≤ x}. 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.

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 points of contact 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.

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 T₀.

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 | 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).

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 a ≤ b. Dropping the requirement of being acyclic, one can also obtain all preorders.

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 infima and suprema 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.

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.

Sejarah

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 Sanders 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.

The term poset as an abbreviation for partially ordered set was coined by Garrett Birkhoff in the second edition of his influential book Lattice Theory. -->

Lihat pula

• Cyclic order
• Hierarki
• Incidence algebra
• Important publications in order theory
• Himpunan kausal

Pustaka

• Birkhoff, Garrett (1940). Lattice Theory. 25 (edisi ke-3rd Revised). American Mathematical Society. ISBN 978-0-8218-1025-5. 
• Burris, S. N.; Sankappanavar, H. P. (1981). A Course in Universal Algebra. Springer. ISBN 978-0-387-90578-5. 
• Davey, B. A.; Priestley, H. A. (2002). Introduction to Lattices and Order (edisi ke-2nd). Cambridge University Press. ISBN 0-521-78451-4. 
• Gierz, G.; Hofmann, K. H.; Keimel, K.; Mislove, M.; Scott, D. S. (2003). Continuous Lattices and Domains. Encyclopedia of Mathematics and its Applications. 93. Cambridge University Press. ISBN 978-0-521-80338-0. 

Pranala luar

• Orders at ProvenMath partial order, linear order, well order, initial segment; formal definitions and proofs within the axioms of set theory.
• Nagel, Felix (2013). Set Theory and Topology. An Introduction to the Foundations of Analysis

[[Kategori:Matematika