Himpunan terurut parsial

memformalkan dan menggeneralisasi konsep intuitif dari suatu urutan, pengurutan, atau susunan elemen dari sebuah himpunan

Dalam matematika, terutama teori urutan, himpunan terurut parsial (bahasa Inggris: Partially ordered set atau disingkat poset) memformalkan dan menggeneralisasi konsep intuitif dari suatu urutan, pengurutan, atau susunan elemen dari sebuah himpunan. Poset terdiri dari himpunan bersama dengan relasi biner yang menunjukkan itu, untuk pasangan elemen tertentu dalam himpunan, salah satu elemen mendahului elemen lainnya dalam urutan. Relasi itu sendiri disebut "urutan parsial". Kata parsial pada nama "urutan parsial" dan "himpunan terurut parsial" digunakan sebagai indikasi bahwa tidak setiap pasangan elemen perlu disusun. Artinya, mungkin ada pasangan elemen yang tidak ada elemen yang mendahului yang lain dalam poset. Perintah parsial kemudian menggeneralisasi urutan total, di mana setiap pasangan dapat dibandingkan.

Diagram Hasse dari himpunan semua himpunan bagian dari himpunan tiga elemen {x, y, z}, dengan penyertaan. Set berbeda pada tingkat horizontal yang sama tidak dapat dibandingkan satu sama lain. Beberapa pasangan lainnya, seperti {x} dan {y, z}, juga tak tertandingi.

Secara formal, urutan parsial adalah setiap relasi biner yang refleksif (setiap elemen sebanding dengan dirinya sendiri), antisimetrik (tidak ada dua elemen berbeda yang mendahului satu sama lain), dan transitif (awal dari rantai relasi prioritas harus mendahului akhir dari kaidah).

Satu contoh familiar dari himpunan yang tersusun sebagian adalah kumpulan orang yang diurutkan berdasarkan silsilah keturunan. Beberapa pasang orang memiliki relasi keturunan-leluhur, tetapi pasangan orang lainnya tidak ada bandingannya, karena tidak ada yang menjadi keturunan dari yang lain.

Sebuah poset dapat divisualisasikan melalui diagram Hasse, yang menggambarkan relasi urutan.[1]

Definisi formalSunting

Sebuat urutan parsial (taksempurna)[2] adalah relasi biner homogen ≤ di atas himpunan P yang memenuhi aksioma tertentu yang akan dibahas di bawah ini. Ketika a b , kita mengatakan bahwa a adalah terkait dengan b . (Ini tidak berarti bahwa b juga terkait dengan a , karena relasinya tidak perlu simetris.)

Aksioma untuk tatanan parsial non-ketat menyatakan bahwa relasi ≤ adalah refleksif, antisimetrik, dan transitif. Artinya, untuk semua a , b , dan c dalam P , harus memenuhi:

  1. aa ( refleksivitas: setiap elemen terkait dengan dirinya sendiri).
  2. jika ab dan ba, kemudian a = b ( antisimetri: dua elemen berbeda tidak dapat dihubungkan di kedua arah).
  3. jika ab dan bc, kemudian ac ( transitivitas: jika elemen pertama terkait dengan elemen kedua, dan, pada gilirannya, elemen tersebut terkait dengan elemen ketiga, maka elemen pertama terkait dengan elemen ketiga).

Dengan kata lain, urutan parsial adalah antisimetri pratatanan.

Himpunan dengan urutan parsial disebut himpunan urutan sebagian (juga disebut poset). Istilah himpunan terurut terkadang juga digunakan, selama jelas dari konteksnya bahwa tidak ada jenis urutan lain yang berarti. Secara khusus, himpunan terurut total juga bisa disebut sebagai "himpunan terurut", terutama di area di mana struktur ini lebih umum daripada poset.

Untuk a , b , elemen dari himpunan berurutan sebagian P , jika ab atau ba, then a dan b adalah sebanding. Pada gambar di kanan atas, yaitu {x} and {x, y, z} sebanding, sementara {x} dan {y} tidak. Urutan parsial di mana setiap pasangan elemen dapat dibandingkan disebut urutan total atau urutan linear; satu himpunan yang benar-benar tertata juga disebut kaidah (misalnya, bilangan asli dengan urutan standarnya). Himpunan bagian dari poset di mana tidak ada dua elemen berbeda yang sebanding disebut antikaidah (misalnya himpunan tunggal {{x}, {y}, {z}} di gambar kanan atas).

EkstremaSunting

 
Bilangan bulat nonnegatif, diurutkan berdasarkan pembagian
 
Gambar di atas dengan elemen terbesar dan terkecil dihilangkan. Dalam poset yang diperkecil ini, baris teratas dari elemen adalah semua elemen maksimal , dan baris paling bawah adalah semua elemen minimal , tetapi tidak ada elemen terbesar dan tidak ada elemen terkecil . Himpunan {x, y} adalah batas atas untuk kumpulan elemen {{x}, {y}}.

Ada beberapa pengertian tentang elemen "terbesar" dan "terkecil" dalam sebuah poset P , terutama:

  • Elemen terbesar dan elemen terkecil: Sebuah elemen g dalam P adalah elemen terbesar jika untuk setiap elemen a dalam P , a ≤ g. Sebuah elemen m dalam P adalah elemen terkecil jika untuk setiap elemen a dalam P , a m . Poset hanya dapat memiliki satu elemen terbesar atau terkecil.
  • Elemen maksimal dan elemen minimal: Elemen g di P adalah elemen maksimal jika tidak ada elemen a di P sehingga a > g . Demikian pula, elemen m di P adalah elemen minimal jika tidak ada elemen a di P sehingga a < m . Jika poset memiliki elemen terbesar, itu harus menjadi elemen maksimal yang unik, tetapi jika tidak, bisa ada lebih dari satu elemen maksimal, dan juga untuk elemen terkecil dan elemen minimal.
  • Batas atas dan bawah: Untuk subset A dari P , elemen x dalam P adalah batas atas dari A if a x, untuk setiap elemen a pada A. Secara khusus, x tidak perlu berada di A untuk menjadi batas atas dari A . Demikian pula, elemen x dalam P adalah batas bawah dari A jika ax, untuk setiap elemen a di A . Unsur terbesar dari P adalah batas atas P , dan unsur terkecil adalah batas bawah P .

Misalnya, perhatikan bilangan bulat positif, yang diurutkan berdasarkan dapat dibagi: 1 adalah elemen terkecil, karena membagi semua elemen lainnya; di sisi lain poset ini tidak memiliki elemen terbesar (meskipun jika seseorang akan menyertakan 0 dalam poset, yang merupakan kelipatan dari bilangan bulat, itu akan menjadi elemen terbesar; lihat gambar). Kumpulan yang diurutkan sebagian ini bahkan tidak memiliki elemen maksimal, karena ada g yang terbagi misalnya 2g, yang berbeda dari itu, lagu tidak maksimal. Jika angka 1 dikecualikan, sambil menjaga agar dapat dibagi sebagai urutan pada elemen yang lebih besar dari 1, maka poset yang dihasilkan tidak memiliki elemen terkecil, tetapi bilangan prima adalah elemen minimal untuk itu. Dalam poset ini, 60 adalah batas atas (meskipun bukan batas atas terkecil) dari subset {2, 3, 5, 10}, yang tidak memiliki batas bawah (karena 1 tidak ada di poset); di sisi lain 2 adalah batas bawah dari himpunan bagian dari pangkat 2, yang tidak memiliki batas atas.

Urutan pada produk Kartesius dari himpunan urutan sebagianSunting

 
Penutupan refleksif atas pesanan produk langsung yang ketat pada ℕ × ℕ. Elemen tertutup oleh (3,3) dan penutup (3,3) disorot dalam warna hijau dan merah, masing-masing.
 
Pesanan produk pada ℕ × ℕ
 
Urutan leksikografik pada ℕ×ℕ

Untuk meningkatkan kekuatan, yaitu, penurunan set pasangan, tiga dari kemungkinan pesanan parsial pada Produk Kartesius dari dua set yang dipesan sebagian adalah (lihat gambar):

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

Diterapkan ke ruang vektor terurut di atas bidang yang sama, hasilnya dalam setiap kasus juga merupakan ruang vektor terurut.

Lihat pula urutan pada produk Kartesius dari himpunan berurutan total.

Jumlah himpunan yang diurutkan sebagianSunting

 
Diagram Hasse dari urutan parsial deret-paralel, dibentuk sebagai jumlah ordinal dari tiga ordo parsial yang lebih kecil.

Cara lain untuk menggabungkan dua poset adalah jumlah ordinal[3] (or jumlah linear[4]), Z = X ⊕ Y, ditentukan pada penyatuan himpunan yang mendasari X dan Y berdasarkan urutan aZ b jika dan hanya jika:

  • a, bX dengan aX b, atau
  • a, bY dengan aY b, atau
  • aX dan bY.

Jika dua poset urutan rapi, maka jumlah ordinalnya juga.[5] Operasi penjumlahan ordinal adalah salah satu dari dua operasi yang digunakan untuk membentuk urutan parsial deret-paralel, dan dalam konteks ini disebut komposisi seri. Operasi lain yang digunakan untuk membentuk tatanan ini, penyatuan dua himpunan yang terurut sebagian (tanpa hubungan keteraturan antara unsur satu himpunan dan unsur himpunan lainnya) disebut dalam komposisi paralel konteks ini.

Pemetaan antara kumpulan yang diurutkan sebagianSunting

 
Isomorfisme urutan antara pembagi 120 (sebagian diurutkan berdasarkan pembagian) dan himpunan bagian tertutup pembagi dari {2, 3, 4, 5, 8} (diurutkan sebagian oleh penyertaan himpunan)
 
Memelihara pesanan, tetapi tidak mencerminkan pesanan (karena f(u) ≤ f(v), tapi tidak uv) peta.

Diberikan dua set yang dipesan sebagian (S, ≤) dan (T, ≤), sebuah fungsi f: ST disebut pengawetan urutan, atau monoton, atau isoton, jika untuk x dan y pada S , xy menyiratkan f(x) ≤ f(y). Jika (U, ≤) juga merupakan himpunan yang dipesan sebagian, dan keduanya f: ST dan g: TU menjaga keteraturan, komposisi ​​mereka gf : SU juga menjaga ketertiban. Sebuah fungsi f: ST disebut urutan refleksi jika untuk x dan y pada S , f(x) ≤ f(y) menyiratkan xy. Jika f baik untuk menjaga ketertiban maupun mencerminkan ketertiban, maka ini disebut urutan pembenaman dari (S, ≤) menjadi (T, ≼). Dalam kasus terakhir, f harus injektif, karena f(x) = f(y) menyiratkan xy dan yx. Jika ada urutan pembenaman antara dua himpunan terurut parsial S dan T, satunya dikatakan bahwa S dapat menjadi terbenam ke dalam T . Jika urutan pembenaman f: ST adalah bijektif, ini disebut 'isomorfisme tatanan' , dan urutan parsial (S,≤) dan (T ,≤) dikatakan menjadi isomorfik. Ordo isomorfik memiliki struktur serupa diagram Hasse (lih. Gambar kanan). Dapat ditunjukkan bahwa jika peta pelestarian pesanan f: ST dan g: TS dirumuskan gf dan fg menghasilkan fungsi identitas pada S dan T , lalu S dan T adalah urutan-isomorfik. [6]

Misalnya, pemetaan f: ℕ → ℙ(ℕ) dari himpunan bilangan asli (diurutkan berdasarkan pembagian) ke himpunan daya dari bilangan asli (diurutkan berdasarkan set inklusi) dapat ditentukan dengan mengambil setiap bilangan ke himpunan pembagi utama. Ini menjaga keteraturan: jika x membagi y , maka setiap pembagi utama dari x juga merupakan pembagi utama dari y . Namun, ini bukan injektif (karena memetakan 12 dan 6 ke {2, 3}) atau mencerminkan urutan (karena 12 tidak membagi 6). Mengambil alih-alih setiap bilangan ke himpunan pangkat utama -nya mendefinisikan peta g: ℕ → ℙ(ℕ) yaitu memelihara ketertiban, mencerminkan ketertiban, dan karenanya merupakan penyematan pesanan. Ini bukan isomorfisme urutan (karena misalnya tidak memetakan nomor apa pun ke himpunan {4}), tapi bisa dibuat dengan membatasi kodomain menjadi g(ℕ). Gambar kanan menunjukkan subhimpunan dari ℕ dan gambar isomorfiknya di bawah g . Konstruksi isomorfisme-tatanan semacam itu ke dalam himpunan daya dapat digeneralisasikan ke kelas luas tatanan parsial, disebut kekisi distributif, lihat "Teorema wakilan Birkhoff".

Jumlah urutan parsialSunting

Urutan A001035 di OEIS memberikan jumlah urutan parsial pada satu himpunan unsur dinamakan n :

Jumlah n -relasi biner elemen dari tipe yang berbeda
Ele­men Any Transitif Refleksif Urutan utama Urutan sebagian Total praorder Total urutan Relasi kesetaraan
0 1 1 1 1 1 1 1 1
1 2 2 1 1 1 1 1 1
2 16 13 4 4 3 3 2 2
3 512 171 64 29 19 13 6 5
4 65,536 3,994 4,096 355 219 75 24 15
n 2n2 2n2n n
k=0
 
k! S(n, k)
n! n
k=0
 
S(n, k)
OEIS A002416 A006905 A053763 A000798 A001035 A000670 A000142 A000110

Jumlah urutan parsial ketat sama dengan jumlah pesanan parsial.

Jika hitungan dilakukan hanya hingga isomorfisme, urutan 1, 1, 2, 5, 16, 63, 318,… (barisan A000112 pada OEIS) diperoleh.

Ekstensi linearSunting

Urutan parsial ≤* pada himpunan X adalah ekstensi dari urutan parsial lain ≤ on X asalkan untuk semua elemen x dan y dari X , setiap kali x y , hal itu juga terjadi x ≤* y. A ekstensi linier adalah ekstensi yang juga merupakan tatanan linear (yaitu total). Setiap pesanan parsial dapat diperpanjang menjadi pesanan total (prinsip perpanjangan urutan).[7]

Dalam ilmu komputer, Algoritma untuk menemukan ekstensi linier dari urutan parsial (diwakilkan sebagai jangkauan urutan grafik asiklik terarah) disebut penyortiran topologis.

Dalam teori kategoriSunting

Setiap poset (dan setiap set praorder) dapat dianggap sebagai kategori di mana, untuk objek x dan y , paling banyak ada satu morfisme dari x hingga y . Lebih eksplisit lagi, maka hom(x, y) = {(x, y)} if xy (dan sebalik himpunan kosong) dan (y, z)∘(x, y) = (x, z). Kategori seperti itu kadang disebut posetal .

Poset adalah ekuivalen satu sama lain jika dan hanya jika poset tersebut isomorfik. Dalam poset, elemen terkecil, jika ada, adalah objek awal, dan elemen terbesar, jika ada, adalah objek terminal. Selain itu, setiap set yang dipesan sebelumnya setara dengan poset. Akhirnya, setiap subkategori poset adalah isomorfisme tertutup.

Urutan parsial dalam ruang topologiSunting

Jika P adalah himpunan terurut parsial yang juga telah diberi struktur ruang topologi, maka biasanya diasumsikan bahwa   adalah subhimpunan tertutup dari topologi ruang produk  . Di bawah asumsi ini, hubungan urutan parsial berperilaku baik pada batas dalam arti jika  , dan  , dan untuk  ,    , kemudian  .[8]

Lihat pulaSunting

CatatanSunting

  1. ^ Merrifield, Richard E.; Simmons, Howard E. (1989). Topological Methods in Chemistry . New York: John Wiley & Sons. hlm. 28. ISBN 0-471-83817-9. Diakses tanggal 27 July 2012. A partially ordered set is conveniently represented by a Hasse diagram... 
  2. ^ Simovici, Dan A.; Djeraba, Chabane (2008). "Partially Ordered Sets". Mathematical Tools for Data Mining: Set Theory, Partial Orders, Combinatorics. Springer. ISBN 9781848002012. 
  3. ^ Neggers, J.; Kim, Hee Sik (1998), "4.2 Product Order and Lexicographic Order", Basic Posets, World Scientific, hlm. 62–63, ISBN 9789810235895 
  4. ^ Davey, B. A.; Priestley, H. A. (2002). Introduction to Lattices and Order (edisi ke-Second). New York: Cambridge University Press. hlm. 17–18. ISBN 0-521-78451-4 – via Google Books. 
  5. ^ P. R. Halmos (1974). Naive Set Theory . Springer. hlm. 82. ISBN 978-1-4757-1645-0. 
  6. ^ Davey, B. A.; Priestley, H. A. (2002). "Maps between ordered sets". Introduction to Lattices and Order (edisi ke-2nd). New York: Cambridge University Press. hlm. 23–24. ISBN 0-521-78451-4. MR 1902334. .
  7. ^ Jech, Thomas (2008) [1973]. The Axiom of Choice. Dover Publications. ISBN 978-0-486-46624-8. 
  8. ^ Ward, L. E. Jr (1954). "Partially Ordered Topological Spaces". Proceedings of the American Mathematical Society. 5 (1): 144–161. doi:10.1090/S0002-9939-1954-0063016-5 . hdl:10338.dmlcz/101379. 

ReferensiSunting

Pranala luarSunting