Lihat sumber Urutan total

{{short description|Urutan matematika dimana semua elemen dapat dibandingkan}}
{{More footnotes|date=Mei 2021}}
{{stack|{{Relasi biner}}}}
Dalam [[matematika]], sebuah '''total''' atau '''urutan''' (atau '''tatanan''') '''linear''' adalah [[tatanan parsial]] dimana dua elemen dapat dibandingkan. Artinya, urutan total adalah [[relasi biner]] <math>\leq</math> pada beberapa [[himpunan (matematika)|himpunan]] <math>X</math>, yang memenuhi berikut ini untuk semua <math>a, b</math> dan <math>c</math> dalam <math>X</math>:

# <math>a \leq a</math> ([[relasi refleksif|refleksif]]).
# Jika <math>a \leq b</math> dan <math>b \leq c</math> maka <math>a \leq c</math> ([[relasi transitif|transitif]])
# Jika <math>a \leq b</math> dan <math>b \leq a</math> maka <math>a = b</math> ([[relasi antisimetris|antisimetris]])
# <math>a \leq b</math> atau <math>b \leq a</math> ([[relasi terhubung|terhubung]], sebelumnya disebut total).

Jumlah tatanan terkadang disebut '''sederhana''',{{sfn|Birkhoff|1967|p=2}} '''koneks''',{{sfn|Schmidt|Ströhlein|1993|p=32}} atau '''tatanan penuh'''.{{sfn|Fuchs|1963|p=2}}

Satu himpunan yang dilengkapi dengan urutan total adalah '''himpunan berurutan total''';{{sfn|Davey|Priestley|1990|p=3}} istilah '''himpunan berurutan sederhana''', {{sfn|Birkhoff|1967|p=2}} '''himpunan berurutan linear''',{{sfn|Schmidt|Ströhlein|1993|p=32}}{{sfn|Davey|Priestley|1990|p=3}} dan '''loset'''<ref>{{Cite journal|last1=Strohmeier|first1=Alfred|last2=Genillard|first2=Christian|last3=Weber|first3=Mats|date=1990-08-01|title=Ordering of characters and strings|journal=ACM SIGAda Ada Letters|language=EN|issue=7|pages=84|doi=10.1145/101120.101136|s2cid=38115497}}</ref><ref>{{Cite journal|last=Ganapathy|first=Jayanthi|title=Maximal Elements and Upper Bounds in Posets|date=1992|journal=Pi Mu Epsilon Journal|volume=9|issue=7|pages=462–464|jstor=24340068|issn=0031-952X}}</ref> dan penggunaannya. Istilah ''kaidah'' terkadang didefinisikan sebagai sinonim dari ''himpunan berurutan total'',{{sfn|Davey|Priestley|1990|p=3}} tetapi secara umum mengacu pada himpunan bagian berurutan total dari himpunan berurutan sebagian.

Perpanjangan urutan parsial tertentu ke urutan total disebut [[ekstensi linear]] dari urutan parsial tersebut.

== Urutan total batasan dan non-batasan ==

Sebuah '''{{em|urutan total batasan}}''' pada himpunan <math>X</math> adalah [[urutan parsial batasan]] <math>X</math> dimana dua elemen dapat dibandingkan. Artinya, urutan total adalah [[relasi biner]] <math><</math> pada beberapa [[himpunan (matematika)|himpunan]] <math>X</math>, yang memenuhi berikut ini untuk semua <math>a, b</math> dan <math>c</math> dalam <math>X</math>:

# <math>a < a</math> bukan merupakan [[Relasi irrefleksif|irrefleksif]].
# Jika <math>a < b</math> dan <math>b < c</math> maka <math>a < c</math> merupakan [[relasi transitif|transitif]].
# Jika <math>a \neq b</math>, maka <math>a < b</math> atau <math>b < a</math> merupakan [[relasi terhubung|terhubung]].

Untuk setiap urutan total (non-batasan) <math>\leq</math> berada dalam relasi terkait dengan <math><</math> yang disebut ''urutan total batasan'' <math>\leq</math> untuk mendefinisikan dalam dua cara yang setara:
* <math>a < b</math> jika <math>a \leq b</math> dan <math>a \neq b</math> ([[reduksi refleksif]]).
* <math>a < b</math> jika bukan <math>b \leq a</math> (yaitu, <math><</math> adalah [[relasi biner#komplemen|komplemen]] dari [[relasi konversi|konversi]] dari <math>\leq</math>).

Sebaliknya, [[penutupan refleksif]] dari urutan total ketat <math><</math> adalah urutan total (non-batasan).

== Contoh ==
* [[Himpunan bagian]] dari himpunan berurutan total {{math|''X''}} seluruhnya untuk pembatas urutan pada {{math|''X''}}. 
* Urutan unik pada himpunan kosong {{math|∅}}, adalah urutan total.
* Setiap himpunan [[bilangan kardinal]] atau [[bilangan ordinal]] yang merupakan [[urutan rapi]].
* Jika {{math|''X''}} adalah himpunan dan {{math|''f''}} sebuah [[fungsi injeksi]] dari {{math|''X''}} ke himpunan berurutan total maka {{math|''f''}} sebagai induksi pengurutan total pada {{math|''X''}} dengan menyetel {{math|''x''<sub>1</sub> ≤ ''x''<sub>2</sub>}} jika dan hanya jika {{math|''f''(''x''<sub>1</sub>) ≤ ''f''(''x''<sub>2</sub>)}}.
* [[Tatanan leksikografis]] dengan [[produk Kartesius]] dari suatu grup himpunan tatanan total, [[Himpunan indeks|indeks]] oleh [[himpunan terurut rapi]] yang merupakan tatanan total.  
* Himpunan [[bilangan riil]] yang diurutkan oleh hubungan biasa "kurang dari atau sama dengan" (≤) atau "lebih besar dari atau sama dengan" (≥) diurutkan total, dan karenanya himpunan bagian dari [[bilangan asli]], [[bilangan bulat]], dan [[bilangan rasional]]. Masing-masing dapat ditampilkan sebagai "contoh awal" unik sebagai [[tatanan isomorfisma]] hingga dari himpunan tatanan total dengan sifat tertentu, tatanan total {{math|''A''}} adalah ''inisial'' untuk sifat, jika, setiap {{math|''B''}} memiliki sifat, dan tatanan isomorfisme dari {{math|''A''}} ke himpunan bagian dari {{math|''B''}}:<ref>Definisi ini mirip dengan [[objek awal]] dari [[kategori (matematika)|kategori]], tetapi nilai tersebut lemah.</ref>{{cn|reason=sifat yang tidak terbukti tersebut harus bersumber; lihat halaman pembicaraan|date=Maret 2021}}
** Bilangan asli sebagai bentuk himpunan terurut total tidak kosong awal tanpa [[batas atas]].
** Bilangan bulat sebagai bentuk himpunan terurut total tidak kosong awal tanpa batas atas atau pun [[batas bawah]].
** Bilangan rasional sebagai bentuk himpunan terurut total awal yang [[himpunan padat|padat]] dalam bilangan riil. Selain itu, pengurangan refleksif < adalah [[urutan padat]] pada bilangan rasional.
** Bilangan riil sebagai bentuk himpunan terurut total tak hingga awal yang [[keterhubungan|terhubung]] di [[topologi urutan]] (didefinisikan di bawah).
* [[Medan tatanan]] diurutkan seluruhnya menurut definisi. Hal tersebut termasuk bilangan rasional dan bilangan riil. Setiap medan tatanan dengan submedan tatanan isomorfik ke bilangan rasional. Setiap ''[[kelengkapan Dedekind]]'' yang merupakan medan isomorfik ke bilangan riil.
* Huruf-huruf alfabet diurutkan menurut standar [[tatanan abjad|tatanan kamus]], misalnya, {{math|''A'' < ''B'' < ''C''}} dll, adalah tatanan total ketat.

== Kaidah ==

Istilah '''kaidah''' terkadang didefinisikan sebagai sinonim untuk himpunan tatanan total, namun umumnya digunakan untuk merujuk ke [[himpunan bagian]] dari [[himpunan terurut sebagian]] tatanan total untuk urutan induksi.<ref>{{cite book | author=Paul R. Halmos | author-link=Paul R. Halmos | title=Naive Set Theory | location=Princeton | publisher=Nostrand | year=1968 }} Here: Chapter 14</ref><ref>{{cite book | url=https://www.elsevier.com/books/theory-of-relations/fraisse/978-0-444-50542-2 | isbn=978-0-444-50542-2 | author=Roland Fraïssé | author-link=Roland Fraïssé| title=Theory of Relations | location= | publisher=Elsevier | series=Studies in Logic and the Foundations of Mathematics | volume=145 | edition=1st | date=Dec 2000 }} Di hlm. 35</ref> Biasanya, himpunan parsial diurutkan sebagian adalah himpunan bagian dari himpunan tertentu yang diurutkan dengan penyertaan, dan istilah tersebut digunakan untuk menyatakan sifat dari rangkaian kaidah. Jumlah himpunan bertingkat yang tinggi ini menjelaskan kegunaan istilah tersebut.

Contoh umum penggunaan ''kaidah'' untuk merujuk pada himpunan berurutan bagian yang seluruhnya adalah [[lemma Zorn]], jika setiap kaidah dalam rangkaian yang diurutkan sebagian {{mvar|X}} memiliki batas atas di {{mvar|X}}, maka {{mvar|X}} berisi setidaknya satu elemen maksimal.<ref>{{cite book | lccn=89009753 | isbn=0-521-36766-2 | author=Brian A. Davey and Hilary Ann Priestley | title=Introduction to Lattices and Order | publisher=Cambridge University Press | series=Cambridge Mathematical Textbooks | year=1990 }} Di hlm. 100</ref> Lemma Zorn biasanya digunakan dengan {{mvar|X}} yang sebagai himpunan bagian; dalam hal ini, batas atas diperoleh dengan membuktikan bahwa penyatuan elemen kaidah di {{mvar|X}} yang terdapat pada {{mvar|X}}. Cara inilah yang umumnya digunakan untuk membuktikan bahwa [[ruang vektor]] memiliki [[basis Hamel]] dan bahwa [[gelanggang (matematika)|gelanggang]] memiliki [[ideal maksimal]].

Dalam beberapa konteks, kaidah yang dianggap sebagai urutan isomorfik ke bilangan asli dengan urutan biasa atau [[relasi konversi|urutan konversi]]. Dalam hal ini, kaidah dapat diidentifikasi dengan [[urutan monoton]], dan disebut '''kaidah tingkatan''' atau '''kaidah turunan''', tergantung apakah urutannya meningkat atau menurun.<ref>[[Yiannis N. Moschovakis]] (2006) ''Notes on set theory'', [[Undergraduate Texts in Mathematics]] (Birkhäuser) {{ISBN|0-387-28723-X}}, p. 116</ref>

Himpunan berurutan sebagian memiliki [[kondisi kaidah turunan]] jika setiap kaidah turunan pada akhirnya stabil.<ref>artinya, di luar beberapa indeks, seluruh anggota urutan selanjutnya adalah sama</ref> Misalnya, tatanan adalah [[tatanan rapi didirikan|didirikan]] jika bersyarat kaidah turunan. Demikian pula, [[kondisi kaidah tingkatan]] berarti bahwa setiap kaidah tingkatan pada akhirnya menjadi stabil. Misalnya, [[gelanggang Noetherian]] adalah gelanggang [[ideal (teori gelanggang)|ideal]] yang memenuhi kondisi kaidah tingkatan.

"Kaidah" juga dapat digunakan untuk beberapa himpunan berurutan total dari [[struktur matematika|struktur]] yang bukan merupakan himpunan berurutan sebagian. Sebuah contoh diberikan oleh [[kaidah reguler]] dari polinomial. Contoh lain adalah penggunaan "kaidah" sebagai sinonim untuk [[berjalan (teori grafik)|berjalan]] dalam [[grafik (matematika diskrit)|grafik]].

== Konsep lebih lanjut ==
=== Teori kisi ===
Kita dapat mendefinisikan himpunan terurut total sebagai jenis tertentu dari [[Kekisi (tatanan)|kekisi]], yaitu 
: <math>\{a\vee b, a\wedge b\} = \{a, b\}</math> for all ''a'', ''b''.

Maka, kita menulis ''a'' ≤ ''b'' [[jika dan hanya jika]] <math>a = a\wedge b</math>. Oleh karena itu, himpunan tatanan total adalah [[kisi distributif]].

=== Urutan total hingga ===
Argumen [[pencacahan]] sederhana akan memverifikasi bahwa setiap himpunan terurut total hingga tidak kosong, dan karenanya setiap Himpunan bagian tidak kosong yang memiliki elemen terkecil. Jadi, setiap urutan total hingga adalah [[urutan rapi]]. Baik dengan pembuktian langsung atau dengan mengamati bahwa setiap urutan sumur [[urutan isomorfik]] ke [[bilangan ordinal|ordinal]] satu mungkin menunjukkan bahwa setiap total order hingga [[urutan isomorfik]] ke [[segmen awal]] dari bilangan asli yang diurutkan oleh <. Dengan kata lain, urutan total pada himpunan dengan elemen ''k'' menginduksi bijeksi dengan bilangan asli pertama ''k''. Oleh karena itu, adalah umum untuk mengindeks pesanan total hingga atau pesanan sumur dengan [[jenis pesanan]] ω dengan bilangan asli dengan cara yang sesuai dengan urutan (baik dimulai dengan nol atau dengan satu).

=== Teori kategori ===
Himpunan berurutan total membentuk [[subkategori|subkategori lengkap]] dari [[kategori (matematika)|kategori]] dari [[himpunan berurutan sebagian]], dengan [[morfisme]] adalah peta dengan dukungan, yaitu memetakan ''f'' sehingga jika ''a'' ≤ ''b'' maka ''f''(''a'') ≤ ''f''(''b'').

Sebuah [[peta (matematika)|peta]] [[bijeksi|bijektif]] antara dua himpunan terurut total dengan dua urutan tersebut adalah sebuah [[isomorfisme]] dalam kategori ini.

=== Urutan topologi ===
Untuk setiap himpunan terurut total ''X'' kita dapat mendefinisikan ''[[interval (matematika)|interval terbuka]]'' (''a'', ''b'') = {''x'' : ''a'' < ''x'' dan ''x'' < ''b''}, (−∞, ''b'') = {''x'' : ''x'' < ''b''}, (''a'', ∞) = {''x'' : ''a'' < ''x''} and (−∞, ∞) = ''X''. Kita bisa menggunakan interval terbuka ini untuk mendefinisikan [[topologi]] pada himpunan terurut yaitu [[topologi urutan]].

Ketika lebih dari satu urutan digunakan pada satu himpunan, maka satu akan berbicara tentang urutan topologi induksi oleh urutan tertentu. Misalnya jika '''N''' adalah bilangan asli, < lebih kecil dari dan > lebih besar dari yang mungkin kita lihat pada topologi urutan pada '''N''' induksi oleh < dan topologi urutan pada '''N''' induksi oleh >, dalam hal ini keduanya identik tetapi tidak secara umum.

Induksi topologi urutan oleh urutan total dapat ditampilkan secara turun-temurun [[ruang normal|normal]].

=== Kelengkapan ===<!-- Bagian ini ditautkan dari [[Kisi distributif lengkap]] -->
Sebuah himpunan berurutan total dikatakan '''[[Kelengkapan  (teori tatanan)|kelengkapan]]''' jika setiap himpunan bagian tidak kosong yang memiliki [[batas atas]], dan [[batas atas terkecil]]. Misalnya, himpunan [[bilangan riil]] '''R''' sebagai kelengkapan, tetapi himpunan [[bilangan rasional]] '''Q''' bukan kelengkapan. Dengan kata lain, berbagai konsep [[Kelengkapan (teori tatanan)|kelengkapan]] (jangan disamakan dengan "total") tidak terbawa pada [[relasi biner|pembatas]]. Misalnya, di atas [[bilangan riil]], sifat dari relasi adalah bahwa setiap himpunan bagian [[himpunan kosong|tidak kosong]] ''S'' dari '''R''' dengan [[batas atas]] dalam '''R''' memiliki [[Supremum|batas atas terkecil]] (juga disebut supremum) di '''R'''. Namun, untuk bilangan rasional supremum ini belum tentu rasional, sehingga sifat yang sama tidak berpegang pada restriksi relasi ≤ dengan bilangan rasional.

Ada sejumlah hasil yang mengaitkan sifat topologi urutan dengan kelengkapan X:
* Jika topologi urutan terhubung pada ''X'', maka ''X'' adalah kelengkapan.
* ''X'' yang terhubung di bawah topologi urutan jika dan hanya jika kelengkapan dan tidak ada ''celah'' dalam ''X''. Kesenjangannya adalah dua titik ''a'' dan ''b'' di ''X'' dengan ''a'' < ''b'' sehingga tidak ada ''c'' yang memenuhi ''a'' < ''c'' < ''b''.)
* ''X'' adalah kelengkapan jika dan hanya jika setiap himpunan berbatas yang ditutup dalam topologi urutan kompak.

Satu himpunan berurutan total dengan topologi urutan yang merupakan [[kisi lengkap]] adalah [[Ruang kompak|kompak]]. Contohnya adalah interval tertutup dari bilangan riil, misal [[interval unit]] [0,1], dan [[ekstensi garis bilangan riil]]. Ada [[homeomorfisme]] yang merupakan kelengkapan di antara contoh-contoh ini.

=== Jumlah urutan ===<!-- Bagian ini ditautkan dari [[urutan terpencar]] -->
Untuk dua urutan total disjoin <math>(A_1,\le_1)</math> dan <math>(A_2,\le_2)</math>, terdapat urutan alami <math>\le_+</math> dalam himpunan <math>A_1\cup A_2</math>, yang disebut jumlah dari dua tatanan atau terkadang hanya <math>A_1+A_2</math>: 
: Untuk <math>x,y\in A_1\cup A_2</math>, <math>x\le_+ y</math> memegang jika dan hanya jika salah satu dari yang berikut ini membekukan:
:# <math>x,y\in A_1</math> dan <math>x\le_1 y</math>
:# <math>x,y\in A_2</math> dan <math>x\le_2 y</math>
:# <math>x\in A_1</math> dan <math>y\in A_2</math>
Secara intuitif, ini berarti bahwa elemen dari himpunan kedua ditambahkan di atas elemen dari himpunan pertama.

Secara umum, jika <math>(I,\le)</math> adalah satu himpunan indeks berurutan total, dan untuk setiap <math>i\in I</math> struktur <math>(A_i,\le_i)</math> adalah urutan linear, dimana himpunan <math>A_i</math> adalah perpisahan pasangan, maka total urutan alami pada <math>\bigcup_i A_i</math> didefinisikan oleh
: Untuk <math>x,y\in \bigcup_{i\in I} A_i</math>, <math>x\le y</math> memegang jika: 
:# Beberapa <math>i\in I</math> dengan <math> x\le_i y </math>
:# atau beberapa <math>i<j</math> in <math>I</math> dengan <math> x\in A_i</math>, <math> y\in A_j</math>

== Urutan pada produk Kartesius dari himpunan berurutan total ==
Untuk meningkatkan kekuatan, yaitu, mengurangi penggunaan himpunan pasangan, tiga dari kemungkinan urutan pada [[produk Kartesius]] dari dua himpunan berurutan total adalah:
* [[Urutan leksikografis]]: (''a'',''b'') ≤ (''c'',''d'') jika dan hanya jika ''a'' < ''c'' atau (''a'' = ''c'' dan ''b'' ≤ ''d''). Ini merupakan urutan total. 
* (''a'',''b'') ≤ (''c'',''d'') jika dan hanya jika ''a'' ≤ ''c'' dan ''b'' ≤ ''d'' ([[pesanan produk]]). Ini merupakan urutan parsial. 
* (''a'',''b'') ≤ (''c'',''d'') jika dan hanya jika (''a'' < ''c'' dan ''b'' < ''d'') or (''a'' = ''c'' dan ''b'' = ''d'') dari penutupan refleksif dari [[Produk langsung#Produk langsung dari relasi biner|produk langsung]] dari total pesanan yang sesuai. Ini juga merupakan urutan parsial.

Ketiganya dapat didefinisikan secara serupa untuk produk Kartesius lebih dari dua himpunan.

Diterapkan ke [[ruang vektor]] '''R'''<sup>''n''</sup>, masing-masing yang menjadi sebagai [[ruang vektor terurut]].

Lihat pula [[Himpunan berurutan parsial#Contoh|contoh himpunan berurutan sebagian]].

Fungsi riil dari variabel riil ''n'' yang ditentukan pada subset dari '''R'''<sup>''n''</sup> [[Pengurutan batas lemah#Fungsi|mendefinisikan urutan batas lemah dan praorder total]] pada himpunan bagian tersebut.

== Struktur terkait ==
Relasi biner antisimetris, transitif, dan refleksif namun tidak total adalah [[urutan parsial]].

Sebuah [[grup (matematika)|grup]] dengan urutan total kompatibel adalah [[grup terurut total]].

Hanya ada beberapa struktur nontrivial yang dapat didefinisikan sebagai reduksi dari suatu tatanan total. Melupakan hasil orientasi dalam [[relasi keantaraan]]. Melupakan lokasi hasil akhir dalam [[urutan siklik]]. Melupakan kedua hasil data dalam [[relasi pemisahan]].<ref>{{Citation |last=Macpherson |first=H. Dugald |year=2011 |title=A survey of homogeneous structures |journal=Discrete Mathematics |volume=311 |issue=15 |pages=1599–1634 |doi=10.1016/j.disc.2011.01.024}}</ref>

== Lihat pula ==
{{cols}}
* [[Gelanggang Artinian]]
* [[Teori order]]
* [[Urutan rapi]]
* [[Masalah Suslin]]
* [[Garis senegaranya]]
* [[Permutasi]]
* [[Urutan prefiks]] - urutan parsial total ke bawah
{{colend}}

== Catatan ==
{{Reflist}}

== Referensi ==
* {{cite book | author=Garrett Birkhoff | author-link=Garrett Birkhoff | title=Lattice Theory | location=Providence | publisher=Am. Math. Soc. | series=Colloquium Publications | volume=25 | year=1967 }}
* {{cite book | author1=Brian A. Davey | author2=Hilary Ann Priestley | author2-link=Hilary Priestley | title=Introduction to Lattices and Order|title-link= Introduction to Lattices and Order | publisher=Cambridge University Press | series=Cambridge Mathematical Textbooks | isbn=0-521-36766-2 | lccn=89009753 | year=1990 }}
* {{cite book |last=Fuchs |first=L  |title=Partially Ordered Algebraic Systems |url=https://archive.org/details/partiallyordered0000fuch |publisher=Pergamon Press|year=1963}}
* George Grätzer (1971). ''Lattice theory: first concepts and distributive lattices.'' W. H. Freeman and Co. {{isbn|0-7167-0442-0}} 
* John G. Hocking and Gail S. Young (1961). ''Topology.'' Corrected reprint, Dover, 1988.  {{isbn|0-486-65676-4}}
* {{Cite book| publisher = Academic Press| last = Rosenstein| first = Joseph G.| title = Linear orderings| url = https://archive.org/details/linearorderings0000rose| location = New York| date = 1982}}
* {{cite book |last1=Schmidt |first1=Gunther |last2=Ströhlein |first2=Thomas |date=1993 |title=Relations and Graphs: Discrete Mathematics for Computer Scientists |url=https://books.google.com/books?id=ZgarCAAAQBAJ |location=Berlin |publisher=Springer-Verlag |isbn=978-3-642-77970-1 |author-link=Gunther Schmidt }}

== Pranala luar ==
* {{SpringerEOM
 |title=Totally ordered set
 |id=Total_order&oldid=35332
}}

[[Kategori:Relasi biner]]
[[Kategori:Teori order]]
[[Kategori:Teori himpunan]]