เซตอันดับบางส่วน

เซตอันดับบางส่วน หรือ โพเซต (poset) คือเซตที่มาพร้อมกับความสัมพันธ์ที่แสดงแนวคิดของการที่สมาชิกหนึ่งนำหน้าหรืออยู่ต่ำกว่าอีกสมาชิกหนึ่ง โดยไม่จำเป็นต้องเปรียบเทียบสมาชิกทุกคู่ได้

Definition

เซตอันดับบางส่วนคือเซตที่มีความสัมพันธ์ทวิภาคที่สะท้อนกลับ (reflexive), ปฏิสมมาตร (antisymmetric) และถ่ายทอด (transitive) โดยที่สมาชิกอาจเปรียบเทียบกันได้หรือไม่สามารถเปรียบเทียบกันได้ภายใต้ความสัมพันธ์นี้

Scope

หัวข้อนี้ครอบคลุมสัจพจน์ของอันดับบางส่วน, แผนภาพ Hasse, โซ่และแอนติโซ่, สมาชิกสูงสุดและต่ำสุด, ฟังก์ชันคงอันดับและภาวะคู่กัน, และทฤษฎีโครงสร้างเชิงการจัดเรียงของ Dilworth และ Mirsky นอกจากนี้ยังแนะนำฟังก์ชัน Mobius ของโพเซต ซึ่งเป็นกลไกเชิงทฤษฎีอันดับที่อยู่เบื้องหลังหลักการเพิ่มเข้า-ตัดออกทั่วไป

Core questions

• ความสัมพันธ์นำหน้าในหมู่สมาชิกถูกกำหนดด้วยสัจพจน์และวาดได้อย่างไร?
• สมาชิกของโพเซตถูกแบ่งออกเป็นโซ่หรือแอนติโซ่ได้อย่างไร?
• แอนติโซ่ที่ใหญ่ที่สุดหรือโซ่ที่ยาวที่สุดในโพเซตคืออะไร?
• ฟังก์ชัน Mobius ทำให้การนับโดยหลักการเพิ่มเข้า-ตัดออกเป็นแบบทั่วไปได้อย่างไร?

Key concepts

• สัจพจน์อันดับบางส่วน
• แผนภาพ Hasse
• โซ่และแอนติโซ่
• สมาชิกสูงสุดและต่ำสุด
• ทฤษฎีบทของ Dilworth
• ฟังก์ชัน Mobius

Key theories

ทฤษฎีบทของ Dilworth

ในโพเซตจำกัดใดๆ จำนวนโซ่ขั้นต่ำที่จำเป็นในการครอบคลุมสมาชิกทั้งหมดจะเท่ากับขนาดสูงสุดของแอนติโซ่ ซึ่งเป็นภาวะคู่กันแบบ min-max พื้นฐานที่มีผลลัพธ์เชิงการจัดเรียงมากมาย

ฟังก์ชัน Mobius ของโพเซต

โพเซตที่จำกัดเฉพาะที่ทุกโพเซตมีฟังก์ชัน Mobius ที่ผกผันผลรวมเหนืออันดับ ทฤษฎีของ Rota ทำให้สิ่งนี้เป็นแหล่งรวมของหลักการเพิ่มเข้า-ตัดออกและการผกผันเชิงทฤษฎีจำนวน

Clinical relevance

โพเซตใช้จำลองการจัดตารางงานที่มีการพึ่งพา, ลำดับชั้นของเวอร์ชันและการสืบทอด, และความสัมพันธ์ของการเลือกและความครอบคลุม ในขณะที่การแยกส่วนโซ่และแอนติโซ่ปรากฏในอัลกอริทึมการจัดตารางและการเรียงลำดับ

History

ทฤษฎีโซ่-แอนติโซ่ของ Dilworth ในปี 1950 และรากฐานของฟังก์ชัน Mobius ของ Rota ในปี 1964 ได้เปลี่ยนการศึกษาเชิงการจัดเรียงของเซตอันดับให้กลายเป็นหัวข้อสำคัญของคณิตศาสตร์ไม่ต่อเนื่องสมัยใหม่

Key figures

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

Seminal works

• davey2002
• stanley2011

Frequently asked questions

แผนภาพ Hasse คืออะไร?

เป็นภาพวาดของโพเซตจำกัดที่สมาชิกแต่ละตัวเป็นจุดที่วางอยู่เหนือสมาชิกที่มันครอบคลุม โดยมีเส้นเชื่อมเฉพาะระหว่างคู่ที่ครอบคลุมกันเท่านั้น ดังนั้นอันดับจึงอ่านขึ้นไปด้านบน

แอนติโซ่คืออะไร?

แอนติโซ่คือเซตของสมาชิกที่ไม่มีสองตัวใดๆ ที่สามารถเปรียบเทียบกันได้ เช่น กลุ่มของเซตย่อยที่ไม่มีเซตย่อยใดครอบคลุมอีกเซตย่อยหนึ่ง