Teori order: Perbedaan antara revisi
JohnThorne (bicara | kontrib) Tidak ada ringkasan suntingan |
JohnThorne (bicara | kontrib) Tidak ada ringkasan suntingan |
||
| Baris 70: | Baris 70: | ||
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 [[complement (set theory)|set complement]] on a [[powerset]] is an example of an antitone function. |
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 [[complement (set theory)|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 isomorphism]]s''' 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 |
An important question is when two orders are "essentially equal", i.e. when they are the same up to renaming of elements. '''[[Order isomorphism]]s''' 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 istilah "embedding". |
||
A more elaborate type of functions is given by so-called '''[[Galois connection]]s'''. 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. |
A more elaborate type of functions is given by so-called '''[[Galois connection]]s'''. 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. |
||
| Baris 133: | Baris 133: | ||
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 [[equivalence of categories|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]]. |
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 [[equivalence of categories|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 == |
== Sejarah == |
||
Sebagaimana dijelaskan sebelumnya, tatanan sangat banyak ditemuai dalam matematika. Namun, penyebutan eksplisit paling awal mengenai tatanan parsial dapat dilacak setelah abad ke-19. Dalam konteks ini karya [[George Boole]] dianggap sangat penting. Di samping itu [[Charles Sanders Peirce]], [[Richard Dedekind]], dan [[Ernst Schröder]] juga membahas konsep teori order. |
|||
| ⚫ | Istilah "''poset''" sebagai singkatan dari "''<u>p</u>artially <u>o</u>rdered <u>set</u>''", yaitu "himpunan dengan tatanan parsial", digagas oleh [[:en:Garrett Birkhoff|Garrett Birkhoff]] dalam edisi kedua bukunya yang berpengaruh ''Lattice Theory''.<ref>Birkhoff 1948, p.1</ref><ref>[http://jeff560.tripod.com/o.html Earliest Known Uses of Some of the Words of Mathematics]</ref> |
||
| ⚫ | |||
| ⚫ | |||
== Lihat pula == |
== Lihat pula == |
||
* [[Cyclic order]] |
* [[Cyclic order]] |
||
* [[Hierarki]] |
* [[Hierarki]] |
||
* [[Incidence algebra]] |
* [[Incidence algebra]] |
||
* [[List of publications in mathematics#Order theory|Important publications in order theory]] |
|||
* [[Himpunan kausal]] |
* [[Himpunan kausal]] |
||
Revisi per 18 Desember 2014 19.12
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").
Sejarah
Sebagaimana dijelaskan sebelumnya, tatanan sangat banyak ditemuai dalam matematika. Namun, penyebutan eksplisit paling awal mengenai tatanan parsial dapat dilacak setelah abad ke-19. Dalam konteks ini karya George Boole dianggap sangat penting. Di samping itu Charles Sanders Peirce, Richard Dedekind, dan Ernst Schröder juga membahas konsep teori order.
Istilah "poset" sebagai singkatan dari "partially ordered set", yaitu "himpunan dengan tatanan parsial", digagas oleh Garrett Birkhoff dalam edisi kedua bukunya yang berpengaruh Lattice Theory.[1][2]
Lihat pula
Referensi
- ^ Birkhoff 1948, p.1
- ^ Earliest Known Uses of Some of the Words of Mathematics
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