Himpunan Berurutan Parsial

Himpunan berurutan parsial, atau poset, adalah suatu himpunan beserta relasi yang menangkap gagasan satu elemen mendahului atau berada di bawah elemen lain, tanpa mengharuskan semua pasangan dapat dibandingkan.

Definition

Himpunan berurutan parsial adalah suatu himpunan dengan relasi biner yang bersifat refleksif, antisimetris, dan transitif; elemen-elemen dapat dibandingkan atau tidak dapat dibandingkan di bawah relasi ini.

Scope

Topik ini mencakup aksioma urutan parsial, diagram Hasse, rantai dan antiranai, elemen maksimal dan minimal, peta pelestari urutan dan dualitas, serta teorema struktur kombinatorial Dilworth dan Mirsky. Ini juga memperkenalkan fungsi Mobius dari suatu poset, mesin teoretis-urutan di balik inklusi-eksklusi umum.

Core questions

• Bagaimana relasi preseden antar elemen diaksiomatisasi dan digambar?
• Bagaimana elemen-elemen poset dipartisi menjadi rantai atau antiranai?
• Apa antiranai terbesar atau rantai terpanjang dalam suatu poset?
• Bagaimana fungsi Mobius menggeneralisasi penghitungan dengan inklusi-eksklusi?

Key concepts

• Aksioma urutan parsial
• Diagram Hasse
• Rantai dan antiranai
• Elemen maksimal dan minimal
• Teorema Dilworth
• Fungsi Mobius

Key theories

Teorema Dilworth

Dalam setiap poset hingga, jumlah minimum rantai yang dibutuhkan untuk menutupi semua elemen sama dengan ukuran maksimum antiranai, suatu dualitas min-maks fundamental dengan banyak konsekuensi kombinatorial.

Fungsi Mobius dari suatu poset

Setiap poset yang terbatas secara lokal memiliki fungsi Mobius yang membalik penjumlahan di atas urutan; teori Rota menjadikan ini sumber pemersatu inklusi-eksklusi dan inversi teori bilangan.

Clinical relevance

Poset memodelkan penjadwalan tugas dengan dependensi, hierarki versi dan pewarisan, serta relasi preferensi dan subsumsi, sementara dekomposisi rantai dan antiranai muncul dalam algoritma penjadwalan dan pengurutan.

History

Teorema rantai-antiranai Dilworth tahun 1950 dan dasar-dasar fungsi Mobius Rota tahun 1964 mengubah studi kombinatorial himpunan berurutan menjadi topik sentral matematika diskrit modern.

Key figures

• Robert Dilworth
• Gian-Carlo Rota
• Richard P. Stanley

Seminal works

• davey2002
• stanley2011

Frequently asked questions

Apa itu diagram Hasse?

Ini adalah gambar poset hingga di mana setiap elemen adalah titik yang ditempatkan di atas elemen yang ditutupinya, dengan hanya ada garis tepi di antara pasangan yang menutupi, sehingga urutan dibaca ke atas.

Apa itu antiranai?

Antiranai adalah himpunan elemen yang tidak ada dua di antaranya yang dapat dibandingkan, seperti kumpulan himpunan bagian yang tidak ada satu pun yang mengandung yang lain.