Ensiklopedia

Artikel ini sudah memiliki referensi , tetapi tidak disertai kutipan yang cukup . Anda dapat membantu mengembangkan artikel ini dengan menambahkan lebih banyak kutipan pada teks artikel. ( Mei 2021 ) ( Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini )

Dalam matematika , sebuah total atau urutan (atau tatanan ) linear adalah dimana dua elemen dapat dibandingkan. Artinya, urutan total adalah relasi biner ${\displaystyle \leq }$ pada beberapa himpunan ${\displaystyle X}$ , yang memenuhi berikut ini untuk semua ${\displaystyle a,b}$ dan ${\displaystyle c}$ dalam ${\displaystyle X}$ :

1. ${\displaystyle a\leq a}$ ( refleksif ).
2. Jika ${\displaystyle a\leq b}$ dan ${\displaystyle b\leq c}$ maka ${\displaystyle a\leq c}$ ( transitif )
3. Jika ${\displaystyle a\leq b}$ dan ${\displaystyle b\leq a}$ maka ${\displaystyle a=b}$ ( )
4. ${\displaystyle a\leq b}$ atau ${\displaystyle b\leq a}$ ( , sebelumnya disebut total).

Jumlah tatanan terkadang disebut sederhana , ^{[ 1 ]} koneks , ^{[ 2 ]} atau tatanan penuh . ^{[ 3 ]}

Satu himpunan yang dilengkapi dengan urutan total adalah himpunan berurutan total ; ^{[ 4 ]} istilah himpunan berurutan sederhana , ^{[ 1 ]} himpunan berurutan linear , ^{[ 2 ] [ 4 ]} dan loset ^{[ 5 ] [ 6 ]} dan penggunaannya. Istilah kaidah terkadang didefinisikan sebagai sinonim dari himpunan berurutan total , ^{[ 4 ]} tetapi secara umum mengacu pada himpunan bagian berurutan total dari himpunan berurutan sebagian.

Perpanjangan urutan parsial tertentu ke urutan total disebut dari urutan parsial tersebut.

Sebuah urutan total batasan pada himpunan ${\displaystyle X}$ adalah ${\displaystyle X}$ dimana dua elemen dapat dibandingkan. Artinya, urutan total adalah relasi biner ${\displaystyle <}$ pada beberapa himpunan ${\displaystyle X}$ , yang memenuhi berikut ini untuk semua ${\displaystyle a,b}$ dan ${\displaystyle c}$ dalam ${\displaystyle X}$ :

1. ${\displaystyle a<a}$ bukan merupakan .
2. Jika ${\displaystyle a<b}$ dan ${\displaystyle b<c}$ maka ${\displaystyle a<c}$ merupakan transitif .
3. Jika ${\displaystyle a\neq b}$ , maka ${\displaystyle a<b}$ atau ${\displaystyle b<a}$ merupakan .

Untuk setiap urutan total (non-batasan) ${\displaystyle \leq }$ berada dalam relasi terkait dengan ${\displaystyle <}$ yang disebut urutan total batasan ${\displaystyle \leq }$ untuk mendefinisikan dalam dua cara yang setara:

• ${\displaystyle a<b}$ jika ${\displaystyle a\leq b}$ dan ${\displaystyle a\neq b}$ ( ).
• ${\displaystyle a<b}$ jika bukan ${\displaystyle b\leq a}$ (yaitu, ${\displaystyle <}$ adalah komplemen dari dari ${\displaystyle \leq }$ ).

Sebaliknya, dari urutan total ketat ${\displaystyle <}$ adalah urutan total (non-batasan).

• Himpunan bagian dari himpunan berurutan total X seluruhnya untuk pembatas urutan pada X .
• Urutan unik pada himpunan kosong ∅ , adalah urutan total.
• Setiap himpunan bilangan kardinal atau bilangan ordinal yang merupakan urutan rapi .
• Jika X adalah himpunan dan f sebuah dari X ke himpunan berurutan total maka f sebagai induksi pengurutan total pada X dengan menyetel x ₁ ≤ x ₂ jika dan hanya jika f ( x ₁ ) ≤ f ( x ₂ ) .
• dengan produk Kartesius dari suatu grup himpunan tatanan total, indeks oleh 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 hingga dari himpunan tatanan total dengan sifat tertentu, tatanan total A adalah inisial untuk sifat, jika, setiap B memiliki sifat, dan tatanan isomorfisme dari A ke himpunan bagian dari B : ^{[ 7 ] [ butuh rujukan ]}
  • Bilangan asli sebagai bentuk himpunan terurut total tidak kosong awal tanpa .
  • Bilangan bulat sebagai bentuk himpunan terurut total tidak kosong awal tanpa batas atas atau pun .
  • Bilangan rasional sebagai bentuk himpunan terurut total awal yang dalam bilangan riil. Selain itu, pengurangan refleksif < adalah pada bilangan rasional.
  • Bilangan riil sebagai bentuk himpunan terurut total tak hingga awal yang terhubung di (didefinisikan di bawah).
• diurutkan seluruhnya menurut definisi. Hal tersebut termasuk bilangan rasional dan bilangan riil. Setiap medan tatanan dengan submedan tatanan isomorfik ke bilangan rasional. Setiap yang merupakan medan isomorfik ke bilangan riil.
• Huruf-huruf alfabet diurutkan menurut standar , misalnya, A < B < C dll, adalah tatanan total ketat.

Istilah kaidah terkadang didefinisikan sebagai sinonim untuk himpunan tatanan total, namun umumnya digunakan untuk merujuk ke himpunan bagian dari tatanan total untuk urutan induksi. ^{[ 8 ] [ 9 ]} 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 X memiliki batas atas di X , maka X berisi setidaknya satu elemen maksimal. ^{[ 10 ]} Lemma Zorn biasanya digunakan dengan X yang sebagai himpunan bagian; dalam hal ini, batas atas diperoleh dengan membuktikan bahwa penyatuan elemen kaidah di X yang terdapat pada X . Cara inilah yang umumnya digunakan untuk membuktikan bahwa ruang vektor memiliki basis Hamel dan bahwa gelanggang memiliki .

Dalam beberapa konteks, kaidah yang dianggap sebagai urutan isomorfik ke bilangan asli dengan urutan biasa atau . Dalam hal ini, kaidah dapat diidentifikasi dengan , dan disebut kaidah tingkatan atau kaidah turunan , tergantung apakah urutannya meningkat atau menurun. ^{[ 11 ]}

Himpunan berurutan sebagian memiliki jika setiap kaidah turunan pada akhirnya stabil. ^{[ 12 ]} Misalnya, tatanan adalah jika bersyarat kaidah turunan. Demikian pula, berarti bahwa setiap kaidah tingkatan pada akhirnya menjadi stabil. Misalnya, adalah gelanggang ideal yang memenuhi kondisi kaidah tingkatan.

"Kaidah" juga dapat digunakan untuk beberapa himpunan berurutan total dari struktur yang bukan merupakan himpunan berurutan sebagian. Sebuah contoh diberikan oleh dari polinomial. Contoh lain adalah penggunaan "kaidah" sebagai sinonim untuk dalam .

Kita dapat mendefinisikan himpunan terurut total sebagai jenis tertentu dari kekisi , yaitu

${\displaystyle \{a\vee b,a\wedge b\}=\{a,b\}}$ for all a , b .

Maka, kita menulis a ≤ b jika dan hanya jika ${\displaystyle a=a\wedge b}$ . Oleh karena itu, himpunan tatanan total adalah .

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 ke ordinal satu mungkin menunjukkan bahwa setiap total order hingga ke 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 ω dengan bilangan asli dengan cara yang sesuai dengan urutan (baik dimulai dengan nol atau dengan satu).

Himpunan berurutan total membentuk dari kategori dari himpunan berurutan sebagian , dengan adalah peta dengan dukungan, yaitu memetakan f sehingga jika a ≤ b maka f ( a ) ≤ f ( b ).

Sebuah peta bijektif antara dua himpunan terurut total dengan dua urutan tersebut adalah sebuah isomorfisme dalam kategori ini.

Untuk setiap himpunan terurut total X kita dapat mendefinisikan 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 .

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 .

Sebuah himpunan berurutan total dikatakan jika setiap himpunan bagian tidak kosong yang memiliki , dan batas atas terkecil . Misalnya, himpunan bilangan riil R sebagai kelengkapan, tetapi himpunan bilangan rasional Q bukan kelengkapan. Dengan kata lain, berbagai konsep (jangan disamakan dengan "total") tidak terbawa pada pembatas . Misalnya, di atas bilangan riil , sifat dari relasi adalah bahwa setiap himpunan bagian tidak kosong S dari R dengan dalam R memiliki 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 adalah kompak . Contohnya adalah interval tertutup dari bilangan riil, misal [0,1], dan . Ada homeomorfisme yang merupakan kelengkapan di antara contoh-contoh ini.

Untuk dua urutan total disjoin ${\displaystyle (A_{1},\leq _{1})}$ dan ${\displaystyle (A_{2},\leq _{2})}$ , terdapat urutan alami ${\displaystyle \leq _{+}}$ dalam himpunan ${\displaystyle A_{1}\cup A_{2}}$ , yang disebut jumlah dari dua tatanan atau terkadang hanya ${\displaystyle A_{1}+A_{2}}$ :

Untuk ${\displaystyle x,y\in A_{1}\cup A_{2}}$ , ${\displaystyle x\leq _{+}y}$ memegang jika dan hanya jika salah satu dari yang berikut ini membekukan:

1. ${\displaystyle x,y\in A_{1}}$ dan ${\displaystyle x\leq _{1}y}$
2. ${\displaystyle x,y\in A_{2}}$ dan ${\displaystyle x\leq _{2}y}$
3. ${\displaystyle x\in A_{1}}$ dan ${\displaystyle y\in A_{2}}$

Secara intuitif, ini berarti bahwa elemen dari himpunan kedua ditambahkan di atas elemen dari himpunan pertama.

Secara umum, jika ${\displaystyle (I,\leq )}$ adalah satu himpunan indeks berurutan total, dan untuk setiap ${\displaystyle i\in I}$ struktur ${\displaystyle (A_{i},\leq _{i})}$ adalah urutan linear, dimana himpunan ${\displaystyle A_{i}}$ adalah perpisahan pasangan, maka total urutan alami pada ${\displaystyle \bigcup _{i}A_{i}}$ didefinisikan oleh

Untuk ${\displaystyle x,y\in \bigcup _{i\in I}A_{i}}$ , ${\displaystyle x\leq y}$ memegang jika:

1. Beberapa ${\displaystyle i\in I}$ dengan ${\displaystyle x\leq _{i}y}$
2. atau beberapa ${\displaystyle i<j}$ in ${\displaystyle I}$ dengan ${\displaystyle x\in A_{i}}$ , ${\displaystyle y\in A_{j}}$

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 ( ). 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 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 ⁿ , masing-masing yang menjadi sebagai .

Lihat pula .

Fungsi riil dari variabel riil n yang ditentukan pada subset dari R ⁿ pada himpunan bagian tersebut.

Relasi biner antisimetris, transitif, dan refleksif namun tidak total adalah urutan parsial .

Sebuah grup dengan urutan total kompatibel adalah .

Hanya ada beberapa struktur nontrivial yang dapat didefinisikan sebagai reduksi dari suatu tatanan total. Melupakan hasil orientasi dalam . Melupakan lokasi hasil akhir dalam . Melupakan kedua hasil data dalam . ^{[ 13 ]}

• (1967). Lattice Theory . Colloquium Publications. 25 . Providence: Am. Math. Soc.
• Brian A. Davey; (1990). . Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 0-521-36766-2 . LCCN 89009753 .
• Fuchs, L (1963). Partially Ordered Algebraic Systems . Pergamon Press.
• 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
• Rosenstein, Joseph G. (1982). Linear orderings . New York: Academic Press.
• ; Ströhlein, Thomas (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists . Berlin: Springer-Verlag. ISBN 978-3-642-77970-1 .

• Hazewinkel, Michiel , ed. (2001) [1994], , Encyclopedia of Mathematics , Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4