Himpunan terurut parsial: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Merapikan artikel |
|||
Baris 1:
{{Short description|Himpunan objek matematika yang dilengkapi dengan urutan}}{{stack|{{Relasi biner}}}}
[[Gambar:Hasse diagram of powerset of 3.svg
Satu contoh familiar dari himpunan yang tersusun sebagian adalah sekumpulan orang yang diurutkan berdasarkan [[Genealogi|silsilah keturunan]]. Beberapa pasang orang memiliki relasi keturunan, tetapi pasangan orang lainnya (misal, sesama saudara kandung) tidak dapat dibandingkan, karena tidak ada yang menjadi keturunan dari yang lain.
Baris 34:
[[File:PartialOrders redundencies svg.svg|thumb|upright=1.25|'''Fig.2''' [[Diagram komutatif]] tentang koneksi antara relasi tegas/tak-tegas dan dual mereka, lewat operasi ''reflexive closure'' (''cls''), ''irreflexive kernel'' (''ker''), dan ''converse relation'' (''cnv''). Setiap relasi ditunjukkan dengan [[matriks biner]] untuk poset yang [[diagram Hasse|diagram Hassenya]] digambarkan di bagian tengah ilustrasi. Sebagai contoh, <math>3 \not\leq 4</math> mengartikan elemen di baris-3 kolom-4 pada matriks di sisi kiri bawah kosong.]]
Urutan parsial tegas dan tak-tegas pada himpunan <math>P</math> memiliki hubungan yang erat. Urutan parsial tak-tegas <math>\leq</math> dapat diubah menjadi urutan parsial tegas dengan menghilangkan semua hubungan yang memiliki bentuk <math>a \leq a;</math> artinya, himpunan parsial tegas adalah himpunan <math>< \; := \ \leq\ \setminus \ \Delta_P,</math> dengan <math>\Delta_P := \{ (p, p) : p \in P \}</math> adalah [[relasi identitas]] pada <math>P \times P</math> dan <math>\;\setminus\;</math> menyatakan operasi pengurangan pada himpunan. Urutan parsial tegas <math><</math> pada <math>P</math> dapat diubah menjadi urutan parsial tak-tegas dengan menggabungkannya dengan realsi identitas; yakni <math>\leq\; := \;\Delta_P\; \cup \;<\;</math>. Akibatnya, jika <math>\leq</math> adalah urutan parsial tak-tegas, maka urutan parsial tegas <math><</math> yang berkorespodensi dengannya adalah ''[[irreflexive kernel]]'':<math display=block>a < b \text{ if } a \leq b \text{ dan } a \neq b.</math>Sebalinya, jika < adalah urutan parsial tegas, maka urutan parsial tak-tegas <math>\leq</math> yang berkorespodensi dengannya ''[[reflexive closure]]'':<math display="block">a \leq b \text{ if } a < b \text{ atau } a = b.</math>
==
Poset dapat disajikan sebagai [[rangkap]]-3 <math>(P,\leq,<)</math>,<ref>{{cite book|last1=Avigad|first1=Jeremy|last2=Lewis|first2=Robert Y.|last3=van Doorn|first3=Floris|date=29 March 2021|url=https://leanprover.github.io/logic_and_proof/relations.html#more-on-orderings|title=Logic and Proof|edition=Release 3.18.4|chapter=13.2. More on Orderings|quote=So we can think of every partial order as really being a pair, consisting of a weak partial order and an associated strict one.|access-date=24 July 2021}}</ref> dengan <math>\leq</math> adalah relasi parsial tak-tegas pada <math>P</math>, <math> < </math> adalah relasi parsial tegas yang berkorespodensi pada <math>P</math> ([[Irreflexive kernel|''irreflexive kernel'']] dari <math>\leq</math>). Simbol <math>\geq</math> digunakan untuk menunjukkan dual dari <math>\leq</math>, dan <math> > </math> untuk menunjukkan dual dari <math> < </math>.
[[Berkas:Infinite lattice of divisors.svg|thumb|x150px|Bilangan bulat nonnegatif, diurutkan berdasarkan pembagian]]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 ''a'' ≥ ''x'', untuk setiap elemen '' a '' di '' A ''. Unsur terbesar dari '' P '' adalah batas atas '' P '', dan unsur terkecil adalah batas bawah '' P ''.▼
[[Berkas:Hasse diagram of powerset of 3 no greatest or least.svg|thumb|x150px|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 {{nowrap|{{''x''}, {''y''}}}}.]]Misalnya, perhatikan [[bilangan bulat positif]], yang diurutkan berdasarkan dapat dibagi: 1 adalah elemen terkecil, karena [[pembagi | 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 2''g'', 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.▼
Salah satu dari empat relasi parsial <math>\leq, <, \geq, \text{ dan } ></math> pada suatu himpunan akan secara unik menentukan tiga relasi yang lain. Akibatnya, bentuk <math>(P,\leq)</math> atau <math>(P,<)</math> dapat digunakan sebagai notasi, dan berasumsi bahwa relasi-relasi yang lain akan didefinisikan secara wajar. Pendefinisian menggunakan urutan parsial tak-tegas <math>\leq</math> adalah yang paling umum. Beberapa penulis menggunakan simbol selain <math>\leq</math>, seperti <math>\sqsubseteq</math><ref>{{cite web|last1=Rounds|first1=William C.|date=7 March 2002|title=Lectures slides|url=http://www.eecs.umich.edu/courses/eecs203-1/203-Mar7.pdf|website=EECS 203: DISCRETE MATHEMATICS|access-date=23 July 2021}}</ref> dan <math>\preceq</math><ref>{{cite book|last1=Kwong|first1=Harris|date=25 April 2018|url=https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/A_Spiral_Workbook_for_Discrete_Mathematics_(Kwong)/07%3A_Relations/7.04%3A_Partial_and_Total_Ordering|title=A Spiral Workbook for Discrete Mathematics|language=en|chapter=7.4: Partial and Total Ordering|access-date=23 July 2021}}</ref>, untuk membedakannya dengan urutan total.
== Urutan pada produk Kartesius dari himpunan urutan sebagian ==▼
[[Berkas:Strict product order on pairs of natural numbers.svg|thumb|x150px|Penutupan refleksif atas pesanan produk langsung yang ketat pada ℕ × ℕ. Elemen [[#Definisi formal | tertutup]] oleh (3,3) dan penutup (3,3) disorot dalam warna hijau dan merah, masing-masing.]][[Berkas:N-Quadrat, gedreht.svg|thumb|x150px|Pesanan produk pada ℕ × ℕ]][[Berkas:Lexicographic order on pairs of natural numbers.svg|thumb|x150px|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):▼
Ketika mengacu pada urutan parsial, <math>\leq</math> sebaiknya tidak dianggap sebagai [[Relasi komplemen|komplemen]] dari <math> > </math>. Relasi <math> > </math> adalah konvers ''irreflexive kernel'' dari <math>\leq</math>, yang akan selalu berupa subset komplemen dari <math>\leq</math>, namun <math> > </math> sama dengan komplemen dari <math>\leq</math> [[Jika dan hanya jika|jika, dan hanya jika]], <math>\leq</math> adalah urutan total.{{efn|A proof can be found [[:File:PartialOrders redundencies.pdf|here]].}}
== Contoh ==
▲=== Urutan pada produk Kartesius dari himpunan urutan sebagian ===
▲[[Berkas:Strict product order on pairs of natural numbers.svg|thumb
*[[urutan leksikografis]]: (''a'',''b'') ≤ (''c'',''d'') jika ''a'' < ''c'' atau (''a'' = ''c'' dan ''b'' ≤ ''d'');
*[[urutan produk]]: (''a'',''b'') ≤ (''c'',''d'') jika ''a'' ≤ ''c'' dan ''b'' ≤ ''d'';
Baris 58 ⟶ 57:
Lihat pula [[Total urutan#Urutan pada produk Kartesius dari himpunan berurutan total | urutan pada produk Kartesius dari himpunan berurutan total]].
=== Jumlah himpunan yang diurutkan sebagian ===
[[Berkas:Series-parallel partial order.svg|thumb|upright=1.35|[[Diagram Hasse]] dari [[urutan parsial deret-paralel]], dibentuk sebagai jumlah ordinal dari tiga ordo parsial yang lebih kecil.]]
▲ | year = 1998}}</ref> (or '''jumlah linear'''<ref>{{cite book |last1=Davey |first1=B. A. |last2=Priestley |first2=H. A. |title=Introduction to Lattices and Order |edition=Second |location=New York |publisher=Cambridge University Press |year=2002 |isbn=0-521-78451-4 |pages=17–18 |url=https://books.google.com/books?id=vVVTxeuiyvQC&pg=PA17 |via=[[Google Books]] }}</ref>), ''Z'' = ''X'' ⊕ ''Y'', ditentukan pada penyatuan himpunan yang mendasari '' X '' dan '' Y '' berdasarkan urutan ''a'' ≤<sub>''Z''</sub> ''b'' jika dan hanya jika:
* ''a'', ''b'' ∈ ''X'' dengan ''a'' ≤<sub>''X''</sub> ''b'', atau
* ''a'', ''b'' ∈ ''Y'' dengan ''a'' ≤<sub>''Y''</sub> ''b'', atau
* ''a'' ∈ ''X'' dan ''b'' ∈ ''Y''.
Jika dua poset [[urutan rapi]], maka jumlah ordinalnya juga.<ref>{{cite book|author=P. R. Halmos|
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
[[Berkas:N-Quadrat, gedreht.svg|thumb|Pesanan produk pada ℕ × ℕ]]Diberikan dua set yang dipesan sebagian (''S'', ≤) dan (''T'', ≤), sebuah fungsi ''f'': ''S'' → ''T'' disebut '''[[pengawetan urutan]]''', atau '''[[Fungsi monotonik#Monotonisitas dalam teori urutan | monoton]]''', atau '''isoton''', jika untuk '' x '' dan '' y '' pada '' S '', ''x'' ≤ ''y'' menyiratkan ''f''(''x'') ≤ ''f''(''y'').▼
▲Diberikan dua set yang dipesan sebagian (''S'', ≤) dan (''T'', ≤), sebuah fungsi ''f'': ''S'' → ''T'' disebut '''[[pengawetan urutan]]''', atau '''[[Fungsi monotonik#Monotonisitas dalam teori urutan | monoton]]''', atau '''isoton''', jika untuk '' x '' dan '' y '' pada '' S '', ''x'' ≤ ''y'' menyiratkan ''f''(''x'') ≤ ''f''(''y'').
Jika (''U'', ≤) juga merupakan himpunan yang dipesan sebagian, dan keduanya ''f'': ''S'' → ''T'' dan ''g'': ''T'' → ''U'' menjaga keteraturan, [[komposisi fungsi | komposisi]] mereka ''g''∘''f'' : ''S'' → ''U'' juga menjaga ketertiban.
Sebuah fungsi ''f'': ''S'' → ''T'' disebut '''urutan refleksi''' jika untuk '' x '' dan '' y '' pada '' S '', ''f''(''x'') ≤ ''f''(''y'') menyiratkan ''x'' ≤ ''y''.
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 ''x'' ≤ ''y'' dan ''y'' ≤ ''x''. 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'': ''S'' → ''T'' 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'': ''S'' → ''T'' dan ''g'': ''T'' → ''S'' dirumuskan ''g''∘''f'' dan ''f''∘''g'' menghasilkan [[fungsi identitas]] pada ''S '' dan ''T '', lalu ''S'' dan'' T'' adalah urutan-isomorfik.
== Konsep yang berkaitan ==
=== Ekstrema ===
▲[[Berkas:Infinite lattice of divisors.svg|thumb
▲* [[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 ''a'' ≥ ''x'', untuk setiap elemen '' a '' di '' A ''. Unsur terbesar dari '' P '' adalah batas atas '' P '', dan unsur terkecil adalah batas bawah '' P ''.
▲[[Berkas:Hasse diagram of powerset of 3 no greatest or least.svg|thumb
▲ }}.</ref>[[Berkas:Birkhoff120.svg|thumb|x150px|Isomorfisme urutan antara pembagi 120 (sebagian diurutkan berdasarkan pembagian) dan himpunan bagian tertutup pembagi dari {{nowrap|{2, 3, 4, 5, 8}}} (diurutkan sebagian oleh penyertaan himpunan)]]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 [[Fungsi injektif#Injektif dapat dibuat tidak dapat diubah |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]]".
==
Urutan [{{fullurl:OEIS:A001035}} A001035] di [[On-Line Encyclopedia of Integer Sequences | OEIS]] memberikan jumlah urutan parsial pada satu himpunan unsur dinamakan ''n '':
Baris 117 ⟶ 94:
== Ekstensi linear ==
[[Berkas:Monotonic but nonhomomorphic map between lattices.gif|thumb
Dalam [[ilmu komputer]], Algoritma untuk menemukan ekstensi linier dari urutan parsial (diwakilkan sebagai [[jangkauan]] urutan [[grafik asiklik terarah]]) disebut [[penyortiran topologis]].
| |||