ความสัมพันธ์ทวิภาคแบบถ่ายทอด วี ที อี
สมมาตร แอนติสมมาตร เชื่อมต่อแล้ว มีเหตุผลที่ดี ได้เข้าร่วมแล้ว ได้พบปะแล้ว สะท้อนกลับ ไร้ปฏิกิริยาตอบสนอง ไม่สมมาตร โททอลเซมิคอนเน็กซ์ ต่อต้านปฏิกิริยาสะท้อน ความสัมพันธ์สมมูล วาย ✗ ✗ ✗ ✗ ✗ วาย ✗ ✗ สั่งซื้อล่วงหน้า(กึ่งสั่งซื้อ) ✗ ✗ ✗ ✗ ✗ ✗ วาย ✗ ✗ คำสั่งซื้อบางส่วน ✗ วาย ✗ ✗ ✗ ✗ วาย ✗ ✗ ยอดสั่งซื้อล่วงหน้าทั้งหมด ✗ ✗ วาย ✗ ✗ ✗ วาย ✗ ✗ คำสั่งซื้อทั้งหมด ✗ วาย วาย ✗ ✗ ✗ วาย ✗ ✗ การสั่งซื้อล่วงหน้า ✗ ✗ วาย วาย ✗ ✗ วาย ✗ ✗ การจัดลำดับแบบกึ่งดี ✗ ✗ ✗ วาย ✗ ✗ วาย ✗ ✗ การจัดระเบียบที่ดี ✗ วาย วาย วาย ✗ ✗ วาย ✗ ✗ โครงตาข่าย ✗ วาย ✗ ✗ วาย วาย วาย ✗ ✗ ข้อต่อเซมิแลตติซ ✗ วาย ✗ ✗ วาย ✗ วาย ✗ ✗ มีท-เซมิแลตติซ ✗ วาย ✗ ✗ ✗ วาย วาย ✗ ✗ ลำดับบางส่วนที่เข้มงวด ✗ วาย ✗ ✗ ✗ ✗ ✗ วาย วาย คำสั่งที่เข้มงวดแต่ไม่เข้มงวด ✗ วาย ✗ ✗ ✗ ✗ ✗ วาย วาย ลำดับที่เข้มงวดทั้งหมด ✗ วาย วาย ✗ ✗ ✗ ✗ วาย วาย สมมาตร แอนติสมมาตร เชื่อมต่อแล้ว มีเหตุผลที่ดี ได้เข้าร่วมแล้ว ได้พบปะแล้ว สะท้อนกลับ ไร้ปฏิกิริยาตอบสนอง ไม่สมมาตร คำจำกัดความสำหรับทุกคนและ${\displaystyle a,b}$${\displaystyle S\neq \varnothing :}$ ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ และ }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ หรือ }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle aRa}$ ${\displaystyle {\text{not }}aRa}$ ${\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}$
วายเครื่องหมาย * แสดงว่าคุณสมบัติของคอลัมน์นั้นเป็นจริงเสมอสำหรับพจน์ของแถวนั้น (ทางซ้ายสุด) ในขณะที่ เครื่องหมาย ✗แสดงว่าคุณสมบัตินั้นไม่ได้รับการรับประกันโดยทั่วไป (อาจเป็นจริงหรือไม่ก็ได้) ตัวอย่างเช่น ความสัมพันธ์สมมูลทุกความสัมพันธ์เป็นสมมาตร แต่ไม่จำเป็นต้องเป็นปฏิสมมาตรจะแสดงด้วย * ในคอลัมน์ "สมมาตร" และ เครื่องหมาย ✗ในคอลัมน์ "ปฏิสมมาตร" ตามลำดับ วาย โดยปริยายแล้ว นิยามทั้งหมดกำหนดให้ความสัมพันธ์เอกพันธุ์ ต้องเป็นแบบถ่ายทอดได้ กล่าวคือ สำหรับทุกถ้าและแล้ว นิยามของคำศัพท์อาจต้องการคุณสมบัติเพิ่มเติมที่ไม่ได้ระบุไว้ในตารางนี้ ${\displaystyle R}$${\displaystyle a,b,c,}$${\displaystyle aRb}$${\displaystyle bRc}$${\displaystyle aRc.}$

ในทฤษฎีลำดับการเรียงลำดับแบบอ่อนเป็นการกำหนดรูปแบบทางคณิตศาสตร์ของแนวคิดเชิงสัญชาตญาณของการจัดอันดับของเซตซึ่งสมาชิกบางส่วนอาจผูกติดกัน การเรียงลำดับแบบอ่อนเป็นการวางนัยทั่วไปของเซตที่มีลำดับสมบูรณ์ (การจัดอันดับโดยไม่มีการผูกติดกัน) และในทางกลับกันก็เป็นการวางนัยทั่วไปของ เซตที่มีลำดับบางส่วน (อย่างเคร่งครัด) และ ลำดับ ก่อนหน้า^{[ 1 ]}

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

ลำดับที่อ่อนแอจะถูกนับโดยตัวเลขเบลล์ที่เรียงลำดับมีการใช้ในวิทยาศาสตร์คอมพิวเตอร์เป็นส่วนหนึ่งของ อัลกอริธึม การปรับปรุงพาร์ติชันและในไลบรารีมาตรฐาน C ++ ^{[ 2 ]}

ในการแข่งม้าการใช้ภาพถ่ายตัดสินผลการแข่งขันได้ขจัดผลเสมอหรือ (ตามที่เรียกในบริบทนี้) ผลเสมอออกไปได้บ้าง แต่ไม่ใช่ทั้งหมดดังนั้นผลลัพธ์ของการแข่งม้าจึงอาจจำลองได้ด้วยการจัดลำดับแบบอ่อน^{[ 3 ]}ในตัวอย่างจากการแข่งขัน กระโดดข้ามสิ่งกีดขวาง Maryland Hunt Cupในปี 2007 The Bruce เป็นผู้ชนะอย่างชัดเจน แต่มีม้าสองตัวคือ Bug River และ Lear Charm ที่ได้อันดับสองร่วมกัน โดยม้าตัวอื่นๆ อยู่ด้านหลัง และมีม้าสามตัวที่ไม่เข้าเส้นชัย^{[ 4 ​​]}ในการจัดลำดับแบบอ่อนที่อธิบายผลลัพธ์นี้ The Bruce จะเป็นอันดับแรก Bug River และ Lear Charm จะถูกจัดอันดับหลังจาก The Bruce แต่ก่อนม้าตัวอื่นๆ ที่เข้าเส้นชัย และม้าสามตัวที่ไม่เข้าเส้นชัยจะถูกจัดไว้เป็นอันดับสุดท้ายแต่เสมอกัน

จุดต่างๆ บนระนาบยุคลิดสามารถเรียงลำดับตามระยะห่างจากจุดกำเนิดได้ซึ่งเป็นอีกตัวอย่างหนึ่งของการเรียงลำดับแบบอ่อนที่มีองค์ประกอบอนันต์ มีเซตย่อยขององค์ประกอบที่เชื่อมโยงกันอนันต์ (เซตของจุดที่อยู่ในวงกลม เดียวกัน ที่มีจุดศูนย์กลางอยู่ที่จุดกำเนิด) และมีจุดภายในเซตย่อยเหล่านี้อนันต์ แม้ว่าการเรียงลำดับนี้จะมีองค์ประกอบที่เล็กที่สุด (จุดกำเนิดเอง) แต่ก็ไม่มีองค์ประกอบที่เล็กเป็นอันดับสอง หรือองค์ประกอบที่ใหญ่ที่สุด

การสำรวจความคิดเห็นในการเลือกตั้งทางการเมืองเป็นตัวอย่างของลำดับประเภทหนึ่งที่คล้ายกับลำดับแบบอ่อน แต่แบบจำลองทางคณิตศาสตร์ที่ดีกว่าควรเป็นไปในรูปแบบอื่น ในผลการสำรวจ ผู้สมัครคนหนึ่งอาจนำหน้าอีกคนหนึ่งอย่างชัดเจน หรือผู้สมัครทั้งสองอาจมีคะแนนเท่ากันทางสถิติ ซึ่งหมายความว่าผลการสำรวจไม่ได้เท่ากัน แต่อยู่ในช่วงความคลาดเคลื่อนของกันและกัน อย่างไรก็ตาม หากผู้สมัครคนหนึ่งมีคะแนนเท่ากันทางสถิติกับอีก คน หนึ่ง ก็ยังอาจเป็นไปได้ที่ผู้สมัครคนหนึ่งจะดีกว่าอีกคนหนึ่งอย่างชัดเจนดังนั้นในกรณีนี้ การที่คะแนนเท่ากันจึงไม่ใช่ความสัมพันธ์แบบถ่ายทอดได้เนื่องจากความเป็นไปได้นี้ การจัดอันดับประเภทนี้จึงควรจำลองเป็นลำดับกึ่งมากกว่าลำดับแบบอ่อน^{[ 5 ]}${\displaystyle x}$${\displaystyle y,}$${\displaystyle y}$${\displaystyle z,}$${\displaystyle x}$${\displaystyle z,}$

สมมติตลอดว่าเป็นความสัมพันธ์ทวิภาคเอกพันธุ์บนเซต(นั่นคือเป็นเซตย่อยของ) และตามปกติ ให้เขียนและกล่าวว่าเป็นจริงก็ต่อเมื่อ${\displaystyle \,<\,}$${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle S\times S}$${\displaystyle x<y}$${\displaystyle x<y}$${\displaystyle (x,y)\in \,<.\,}$

เบื้องต้นเกี่ยวกับความไม่สามารถเปรียบเทียบกันได้และการถ่ายทอดความไม่สามารถเปรียบเทียบกันได้

กล่าวกันว่าองค์ประกอบสองอย่างและของ ไม่สามารถ เปรียบเทียบกันได้เมื่อเทียบกับถ้าทั้งและไม่เป็นจริง^{[ 1 ]} ลำดับบางส่วนที่เข้มงวดเป็นลำดับอ่อนที่เข้มงวดก็ต่อเมื่อการเปรียบเทียบไม่ได้เมื่อเทียบกับเป็นความสัมพันธ์สมมูลการเปรียบเทียบไม่ได้เมื่อเทียบกับ เป็น ความสัมพันธ์สมมาตรเอก พันธุ์ บนเสมอ เป็นความสัมพันธ์สะท้อนก็ต่อเมื่อไม่สะท้อน (หมายความว่าเป็นเท็จเสมอ) ซึ่งจะถูกสมมติเพื่อให้การถ่ายทอดเป็นคุณสมบัติเดียวที่ "ความสัมพันธ์เปรียบเทียบไม่ได้" นี้ต้องการเพื่อให้เป็น ความ สัมพันธ์ สมมูล${\displaystyle x}$${\displaystyle y}$${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle x<y}$${\displaystyle y<x}$${\displaystyle \,<\,}$${\displaystyle \,<\,}$${\displaystyle \,<\,}$${\displaystyle S.}$${\displaystyle \,<\,}$${\displaystyle x<x}$

กำหนดความสัมพันธ์เอกพันธุ์เหนี่ยวนำบนโดยประกาศว่า โดยที่สำคัญ นิยามนี้ไม่จำเป็นต้องเหมือนกับ: ก็ต่อเมื่อ สององค์ประกอบเปรียบเทียบกันไม่ได้เมื่อเทียบกับก็ต่อเมื่อเทียบเท่ากันเมื่อเทียบกับ(หรือพูดให้สั้นกว่าคือ เทียบเท่ากัน ) ซึ่งตามนิยามหมายความว่าทั้งสองเป็นจริง ความสัมพันธ์ "เปรียบเทียบกันไม่ได้เมื่อเทียบกับ" จึงเหมือนกับ (นั่นคือ เท่ากับ) ความสัมพันธ์ "เทียบเท่ากัน" (ดังนั้น โดยเฉพาะอย่างยิ่ง ความสัมพันธ์แรกเป็นแบบถ่ายทอดได้ ก็ต่อเมื่อความสัมพันธ์หลังเป็นแบบถ่ายทอดได้) เมื่อไม่สะท้อนกลับ คุณสมบัติที่เรียกว่า " การถ่ายทอดของการเปรียบเทียบกันไม่ได้ " (นิยามไว้ด้านล่าง) คือเงื่อนไขที่จำเป็นและเพียงพอที่จะรับประกันว่าความสัมพันธ์ " เทียบเท่ากัน" ก่อให้เกิดความสัมพันธ์สมมูลบน เมื่อเป็นเช่นนี้ จะอนุญาตให้ระบุสององค์ประกอบใดๆที่ตรงตามเงื่อนไขเป็นวัตถุเดียว (โดยเฉพาะอย่างยิ่ง พวกมันถูกระบุร่วมกันในชั้นสมมูล ร่วมกัน ) ${\displaystyle \,\lesssim \,}$${\displaystyle S}$$${\displaystyle x\lesssim y{\text{ เป็นจริง }}\quad {\text{ ก็ต่อเมื่อ }}\quad y<x{\text{ เป็นเท็จ}}}$$${\displaystyle x\lesssim y}$$x < y หรือ x = y$${\displaystyle x,y\in S}$${\displaystyle \,<\,}$${\displaystyle x{\text{ และ }}y}$${\displaystyle \,\lesssim \,}$${\displaystyle \,\lesssim }$${\displaystyle x\lesssim y{\text{ และ }}y\lesssim x}$${\displaystyle \,<}$${\displaystyle \,\lesssim }$${\displaystyle \,<\,}$${\displaystyle \,\lesssim }$${\displaystyle S.}$${\displaystyle x,y\in S}$${\displaystyle x\lesssim y{\text{ และ }}y\lesssim x}$

คำนิยาม

ลำดับอ่อนที่เข้มงวดบนเซตคือลำดับบางส่วนที่เข้มงวดบนเซตซึ่งความสัมพันธ์ที่ไม่สามารถเปรียบเทียบกันได้ที่เหนี่ยวนำบนเซตโดยเซตนั้นเป็น ความสัมพันธ์ แบบถ่ายทอด^{[ 1 ]} กล่าวคือ ลำดับอ่อนที่เข้มงวดบนเซตคือความสัมพันธ์เอกพันธุ์บนเซตที่มีคุณสมบัติทั้งสี่ประการต่อไปนี้: ${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle S}$${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle S}$

1. ความไม่สะท้อนกลับ : เพราะความจริงแล้วมันไม่เป็นเช่นนั้น${\displaystyle x\in S,}$${\displaystyle x<x.}$
   • เงื่อนไขนี้จะ เป็นจริงก็ต่อเมื่อความสัมพันธ์ที่เหนี่ยวนำบนเป็นความสัมพันธ์สะท้อนกลับโดยที่ถูกกำหนดโดยการประกาศว่าเป็นจริงก็ต่อเมื่อเป็นเท็จ${\displaystyle \,\lesssim \,}$${\displaystyle S}$${\displaystyle \,\lesssim \,}$${\displaystyle x\lesssim y}$${\displaystyle y<x}$
2. คุณสมบัติการถ่ายทอด : สำหรับทุกเงื่อนไข " ถ้า...แล้ว... "${\displaystyle x,y,z\in S,}$${\displaystyle x<y{\text{ และ }}y<z}$${\displaystyle x<z.}$
3. ความไม่สมมาตร : สำหรับทุกกรณีถ้าเป็นจริง แล้วจะเป็นเท็จ${\displaystyle x,y\in S,}$${\displaystyle x<y}$${\displaystyle y<x}$
4. คุณสมบัติการถ่ายทอดของความไม่สามารถเปรียบเทียบกันได้ : สำหรับทุกกรณีถ้าไม่สามารถเปรียบเทียบกับ(หมายความว่าทั้งและ ไม่เป็นจริง) และถ้าไม่สามารถเปรียบเทียบกับแล้วก็ไม่สามารถเปรียบเทียบกับ${\displaystyle x,y,z\in S,}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x<y}$${\displaystyle y<x}$${\displaystyle y}$${\displaystyle z,}$${\displaystyle x}$${\displaystyle z.}$
   • องค์ประกอบสองอย่างเปรียบเทียบกันไม่ได้ก็ต่อเมื่อองค์ประกอบทั้งสองนั้นเทียบเท่ากันโดยสัมพันธ์ที่เหนี่ยวนำ(ซึ่งตามคำนิยามหมายความว่าเป็นจริงทั้งคู่) โดยที่ เป็นจริงก็ต่อเมื่อ เป็นเท็จ ดังนั้นเงื่อนไขนี้จะเป็นจริงก็ต่อเมื่อความสัมพันธ์สมมาตรบน ที่กำหนดโดย " เทียบเท่ากันโดยสัมพันธ์" เป็นความสัมพันธ์ถ่ายทอด หมายความว่าเมื่อใดก็ตามที่เทียบเท่ากันโดยสัมพันธ์ และเทียบเท่า กันโดยสัมพันธ์ แล้ว เทียบเท่า กันโดยสัมพันธ์ อย่างแน่นอนสามารถเขียนใหม่ได้ว่า: เมื่อใดก็ตามที่และแล้ว เทียบเท่ากันโดยสัมพันธ์ อย่างแน่นอน${\displaystyle x{\text{ และ }}y}$${\displaystyle \,<\,}$${\displaystyle \,\lesssim \,}$${\displaystyle x\lesssim y{\text{ และ }}y\lesssim x}$${\displaystyle x\lesssim y}$${\displaystyle y<x}$${\displaystyle S}$${\displaystyle x{\text{ และ }}y}$${\displaystyle \,\lesssim \,}$${\displaystyle x{\text{ และ }}y}$${\displaystyle \,\lesssim }$${\displaystyle y{\text{ และ }}z}$${\displaystyle \,\lesssim }$${\displaystyle x{\text{ และ }}z}$${\displaystyle \,\lesssim }$${\displaystyle x\lesssim y{\text{ และ }}y\lesssim x}$${\displaystyle y\lesssim z{\text{ และ }}z\lesssim y}$${\displaystyle x\lesssim z{\text{ และ }}z\lesssim x.}$

คุณสมบัติ (1), (2) และ (3) เป็นคุณสมบัติที่กำหนดลำดับบางส่วนที่เข้มงวด แม้ว่าจะมีความซ้ำซ้อนในรายการนี้บ้าง เนื่องจากความไม่สมมาตร (3) บ่งบอกถึงความไม่สะท้อน (1) และเนื่องจากความไม่สะท้อน (1) และการถ่ายทอด (2) ร่วมกันบ่งบอกถึงความไม่สมมาตร (3) ^{[ 6 ]}ความสัมพันธ์ที่ไม่สามารถเปรียบเทียบกันได้นั้นสมมาตร เสมอ และจะเป็นแบบสะท้อนก็ต่อเมื่อเป็นความสัมพันธ์ที่ไม่สะท้อน (ซึ่งสมมติโดยคำจำกัดความข้างต้น) ดังนั้น ลำดับบางส่วนที่เข้มงวดจึงเป็นลำดับอ่อนที่เข้มงวดก็ต่อเมื่อความสัมพันธ์ที่ไม่สามารถเปรียบเทียบกันได้ที่เหนี่ยวนำเป็นความสัมพันธ์สมมูลในกรณีนี้ชั้นสมมูลจะแบ่งส่วนและยิ่งไปกว่านั้น เซตของชั้นสมมูลเหล่านี้สามารถเรียงลำดับทั้งหมดอย่างเข้มงวดโดยความสัมพันธ์ทวิภาคซึ่งแสดงด้วยซึ่งกำหนดสำหรับทุกโดย: ${\displaystyle \,<\,}$${\displaystyle \,<\,}$${\displaystyle S}$${\displaystyle {\mathcal {P}}}$${\displaystyle \,<,}$${\displaystyle A,B\in {\mathcal {P}}}$

$A<B ก็ต่อเมื่อ a<b$สำหรับตัวแทนบางส่วน (หรือในทำนองเดียวกัน สำหรับตัวแทนทั้งหมด)${\displaystyle a\in A{\text{ และ }}b\in B.}$

ในทางกลับกันลำดับสมบูรณ์ที่เข้มงวด ใดๆ บนพาร์ติชัน ของจะก่อให้เกิดลำดับอ่อนที่เข้มงวดบน ซึ่งกำหนดโดยก็ต่อเมื่อมีเซตในพาร์ติชันนี้ เช่นนั้น${\displaystyle {\mathcal {P}}}$${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle S}$${\displaystyle a<b}$${\displaystyle A,B\in {\mathcal {P}}}$${\displaystyle a\in A,b\in B,{\text{ และ }}A<B.}$

ไม่ใช่ว่าลำดับบางส่วนทุกอันจะสอดคล้องกับกฎการถ่ายทอดสำหรับความไม่สามารถเปรียบเทียบกันได้ ตัวอย่างเช่น พิจารณาลำดับบางส่วนในเซตที่กำหนดโดยความสัมพันธ์คู่ต่างๆไม่สามารถเปรียบเทียบกันได้ แต่และมีความสัมพันธ์กัน ดังนั้นความไม่สามารถเปรียบเทียบกันได้จึงไม่ก่อให้เกิดความสัมพันธ์สมมูล และตัวอย่างนี้ไม่ใช่ลำดับอ่อนที่เข้มงวด ${\displaystyle \{a,b,c\}}$${\displaystyle b<c.}$${\displaystyle a,b{\text{ และ }}a,c}$${\displaystyle b}$${\displaystyle c}$

สำหรับการถ่ายทอดความไม่สามารถเปรียบเทียบกันได้ เงื่อนไขต่อไปนี้แต่ละข้อเป็นเงื่อนไขที่จำเป็นและสำหรับลำดับบางส่วนที่เข้มงวดก็เป็นเงื่อนไขที่เพียงพอ เช่นกัน :

• ถ้าเช่นนั้นสำหรับทั้งสองอย่างหรืออย่างใดอย่างหนึ่ง${\displaystyle x<y}$${\displaystyle z,}$${\displaystyle x<z{\text{ หรือ }}z<y}$
• ถ้าไม่สามารถเปรียบเทียบกับได้ดังนั้นสำหรับทุก ๆ( ) หรือ ( ) หรือ ( ไม่สามารถเปรียบเทียบกับได้และไม่สามารถเปรียบเทียบกับได้)${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle x<z{\text{ และ }}y<z}$${\displaystyle z<x{\text{ และ }}z<y}$${\displaystyle z}$${\displaystyle x}$${\displaystyle z}$${\displaystyle y}$

ลำดับอ่อนที่เข้มงวดมีความเกี่ยวข้องอย่างใกล้ชิดกับลำดับก่อนทั้งหมดหรือลำดับอ่อน (ที่ไม่เข้มงวด)และแนวคิดทางคณิตศาสตร์เดียวกันที่สามารถจำลองได้ด้วยลำดับอ่อนที่เข้มงวดก็สามารถจำลองได้ดีเช่นกันด้วยลำดับก่อนทั้งหมด ลำดับก่อนทั้งหมดหรือลำดับอ่อนคือลำดับก่อนซึ่งองค์ประกอบสองตัวใด ๆ สามารถเปรียบเทียบกันได้^{[ 7 ]}ลำดับก่อนทั้งหมดเป็นไปตามคุณสมบัติต่อไปนี้: ${\displaystyle \,\lesssim \,}$

• คุณสมบัติการถ่ายทอด : สำหรับทุกเงื่อนไข " ถ้า...แล้ว... "${\displaystyle x,y,{\text{ and }}z,}$${\displaystyle x\lesssim y{\text{ and }}y\lesssim z}$${\displaystyle x\lesssim z.}$
• ความเชื่อมโยงที่แน่นแฟ้น : สำหรับทุกคน${\displaystyle x{\text{ and }}y,}$${\displaystyle x\lesssim y{\text{ or }}y\lesssim x.}$
  • ซึ่งหมายถึงการสะท้อนกลับ : สำหรับทุกสิ่ง${\displaystyle x,}$${\displaystyle x\lesssim x.}$

ลำดับรวม (Total order)คือลำดับก่อนการจัดลำดับรวม (Total preorder) ที่ไม่สมมาตร (Antisymmetric) กล่าวอีกนัยหนึ่งคือ เป็นลำดับบางส่วน (Partial order ) ลำดับก่อนการจัดลำดับรวมบางครั้งเรียกว่าความสัมพันธ์ของความชอบ (Privacy relations )

ส่วนเติมเต็มของลำดับอ่อนที่เข้มงวดคือลำดับก่อนทั้งหมด และในทางกลับกัน แต่ดูเหมือนว่าจะเป็นธรรมชาติมากกว่าที่จะเชื่อมโยงลำดับอ่อนที่เข้มงวดและลำดับก่อนทั้งหมดในลักษณะที่รักษาลำดับขององค์ประกอบไว้แทนที่จะกลับลำดับ ดังนั้นเราจึงใช้ส่วนกลับของส่วนเติมเต็ม: สำหรับลำดับอ่อนที่เข้มงวดให้กำหนดลำดับก่อนทั้งหมดโดยการตั้งค่าเมื่อใดก็ตามที่ไม่ใช่กรณีที่ในทางกลับกัน เพื่อกำหนดลำดับอ่อนที่เข้มงวด < จากชุด ลำดับก่อนทั้งหมด เมื่อใดก็ตามที่ไม่ใช่กรณีที่^{[ 8 ]}${\displaystyle \,<,}$${\displaystyle \,\lesssim \,}$${\displaystyle x\lesssim y}$${\displaystyle y<x.}$${\displaystyle \,\lesssim ,}$${\displaystyle x<y}$${\displaystyle y\lesssim x.}$

ในลำดับก่อนใดๆ จะมีความสัมพันธ์สมมูลที่สอดคล้องกันโดยที่องค์ประกอบสองตัวและจะถูกกำหนดให้สมมูลกันก็ต่อเมื่อในกรณีของ ลำดับ ก่อนแบบสมบูรณ์ลำดับบางส่วนที่สอดคล้องกันบนเซตของชั้นสมมูลจะเป็นลำดับแบบสมบูรณ์ องค์ประกอบสองตัวจะสมมูลกันในลำดับก่อนแบบสมบูรณ์ก็ต่อเมื่อไม่สามารถเปรียบเทียบกันได้ในลำดับอ่อนแบบเข้มงวดที่สอดคล้องกัน ${\displaystyle x}$${\displaystyle y}$${\displaystyle x\lesssim y{\text{ and }}y\lesssim x.}$

การแบ่งส่วนของเซต คือตระกูลของเซตย่อยที่ไม่ว่างและไม่ทับซ้อนกันซึ่งมีผลรวมเป็นเซตย่อย การแบ่งส่วนร่วมกับลำดับทั้งหมดบนเซตของการแบ่งส่วนจะให้โครงสร้างที่ริชาร์ด พี. สแตนลีย์ เรียกว่า การแบ่งส่วนแบบเรียงลำดับ [ ^{9 ] และ}ธีโอดอร์ มอตซ์กินเรียก ว่า รายการของเซต^{[ 10 ]}การแบ่งส่วนแบบเรียงลำดับของเซตจำกัดอาจเขียนได้เป็นลำดับจำกัดของเซตในการแบ่งส่วน ตัวอย่างเช่น การแบ่งส่วนแบบเรียงลำดับสามส่วนของเซตคือ ${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle \{a,b\}}$$${\displaystyle \{a\},\{b\},}$$$${\displaystyle \{b\},\{a\},\;{\text{ and }}}$$$${\displaystyle \{a,b\}.}$$

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

สำหรับเซตที่มี ขนาดสมาชิกน้อยพอสมควรการกำหนดสัจพจน์แบบที่สี่เป็นไปได้ โดยอาศัยฟังก์ชันค่าจริง ถ้าเป็นเซตใดๆ ฟังก์ชันค่าจริงบนจะเหนี่ยวนำให้เกิดลำดับอ่อนที่เข้มงวดบนโดยการตั้งค่า ลำดับก่อนหน้าทั้งหมดที่เกี่ยวข้องจะได้รับจากการตั้งค่า และความสมมูลที่เกี่ยวข้องจะได้รับจากการตั้งค่า ${\displaystyle X}$${\displaystyle f:X\to \mathbb {R} }$${\displaystyle X}$${\displaystyle X}$$${\displaystyle a<b{\text{ if and only if }}f(a)<f(b).}$$${\displaystyle a{}\lesssim {}b{\text{ if and only if }}f(a)\leq f(b)}$${\displaystyle a{}\sim {}b{\text{ if and only if }}f(a)=f(b).}$

ความสัมพันธ์จะไม่เปลี่ยนแปลงเมื่อถูกแทนที่ด้วย( ฟังก์ชันประกอบ ) โดยที่เป็นฟังก์ชันค่าจริงที่เพิ่มขึ้นอย่างเคร่งครัด ซึ่งกำหนดไว้อย่างน้อยในช่วงของ ดังนั้น ตัวอย่างเช่นฟังก์ชันอรรถประโยชน์จะกำหนด ความสัมพันธ์ ความชอบในบริบทนี้ ลำดับที่อ่อนแอเรียกอีกอย่างว่า การจัด เรียงตามความชอบ^{[ 11 ]}${\displaystyle f}$${\displaystyle g\circ f}$${\displaystyle g}$${\displaystyle f.}$

ถ้าเป็นจำนวนจำกัดหรือจำนวนนับได้ ลำดับอ่อนทุกลำดับบนสามารถแสดงด้วยฟังก์ชันในลักษณะนี้ได้^{[ 12 ]}อย่างไรก็ตาม มีลำดับอ่อนที่เข้มงวดซึ่งไม่มีฟังก์ชันจริงที่สอดคล้องกัน ตัวอย่างเช่น ไม่มีฟังก์ชันดังกล่าวสำหรับลำดับพจนานุกรมบนดังนั้น ในขณะที่ในแบบจำลองความสัมพันธ์ความชอบส่วนใหญ่ ความสัมพันธ์จะกำหนดฟังก์ชันอรรถประโยชน์จนถึงการแปลงที่รักษาลำดับไว้ แต่ไม่มีฟังก์ชันดังกล่าวสำหรับความชอบ พจนานุกรม${\displaystyle X}$${\displaystyle X}$${\displaystyle \mathbb {R} ^{n}.}$

โดยทั่วไปแล้ว ถ้าเป็นเซตเป็นเซตที่มีลำดับอ่อนที่เข้มงวดและเป็นฟังก์ชัน แล้วจะเหนี่ยวนำให้เกิดลำดับอ่อนที่เข้มงวดบนโดยการตั้งค่า ดังที่กล่าวมาแล้ว ลำดับก่อนทั้งหมดที่เกี่ยวข้องจะกำหนดโดยการตั้งค่า และความสมมูลที่เกี่ยวข้องจะกำหนดโดยการตั้งค่า ในที่นี้ไม่ได้ถือว่าเป็นฟังก์ชันหนึ่งต่อหนึ่งดังนั้นคลาสของสมาชิกสองตัวที่เทียบเท่ากันบนอาจเหนี่ยวนำให้เกิดคลาสของสมาชิกที่เทียบเท่ากันที่ใหญ่กว่าบนนอกจากนี้ไม่ได้ถือว่า เป็นฟังก์ชันทั่วถึงดังนั้นคลาสของสมาชิกที่เทียบเท่ากันบนอาจเหนี่ยวนำให้เกิดคลาสที่เล็กกว่าหรือว่างเปล่าบนอย่างไรก็ตาม ฟังก์ชันเหนี่ยวนำให้เกิดฟังก์ชันหนึ่งต่อหนึ่งที่แมปพาร์ติชันบนไปยังพาร์ติชันบนดังนั้น ในกรณีของพาร์ติชันจำกัด จำนวนคลาสในจะน้อยกว่าหรือเท่ากับจำนวนคลาสบน${\displaystyle X}$${\displaystyle Y}$${\displaystyle \,<,\,}$${\displaystyle f:X\to Y}$${\displaystyle f}$${\displaystyle X}$$${\displaystyle a<b{\text{ if and only if }}f(a)<f(b).}$$${\displaystyle a{}\lesssim {}b{\text{ if and only if }}f(a){}\lesssim {}f(b),}$${\displaystyle a{}\sim {}b{\text{ if and only if }}f(a){}\sim {}f(b).}$${\displaystyle f}$${\displaystyle Y}$${\displaystyle X.}$${\displaystyle f}$${\displaystyle Y}$${\displaystyle X.}$${\displaystyle f}$${\displaystyle X}$${\displaystyle Y.}$${\displaystyle X}$${\displaystyle Y.}$

เซมิออร์เดอร์เป็นการขยายความของออร์เดอร์แบบอ่อนที่เข้มงวด แต่ไม่ถือว่าการถ่ายทอดของความไม่สามารถเปรียบเทียบ กันได้ ^{[ 13 ]}ออร์เดอร์แบบอ่อนที่เข้มงวดซึ่งเป็นแบบไตรภาคเรียกว่าออร์เดอร์แบบสมบูรณ์ที่เข้มงวด [ ^{14 ] พ}รีออร์เดอร์แบบสมบูรณ์ซึ่งเป็นส่วนกลับของส่วนเติมเต็มในกรณีนี้คือ ออร์เดอ ร์ แบบสมบูรณ์

สำหรับลำดับอ่อนที่เข้มงวดความสัมพันธ์สะท้อนกลับที่เกี่ยวข้องอีกอย่างหนึ่งคือการปิดสะท้อนกลับซึ่งเป็นลำดับบางส่วน (ที่ไม่เข้มงวด) ความสัมพันธ์สะท้อนกลับที่เกี่ยวข้องทั้งสองแตกต่างกันในแง่ของและซึ่งทั้งหรือ: ในลำดับก่อนหน้าทั้งหมดที่สอดคล้องกับลำดับอ่อนที่เข้มงวด เราจะได้และในขณะที่ในลำดับบางส่วนที่กำหนดโดยการปิดสะท้อนกลับ เราจะไม่ได้ ทั้งหรือสำหรับลำดับทั้งหมดที่เข้มงวด ความสัมพันธ์สะท้อนกลับที่เกี่ยวข้องทั้งสองนี้จะเหมือนกัน: ลำดับทั้งหมด (ที่ไม่เข้มงวด) ที่สอดคล้องกัน^{[ 14 ]} การปิดสะท้อนกลับของลำดับอ่อนที่เข้มงวด เป็น ลำดับบางส่วนแบบอนุกรม-ขนานชนิดหนึ่ง${\displaystyle \,<\,}$${\displaystyle \,\leq .}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a<b}$${\displaystyle b<a}$${\displaystyle a\lesssim b}$${\displaystyle b\lesssim a,}$${\displaystyle a\leq b}$${\displaystyle b\leq a.}$

จำนวนลำดับอ่อนที่แตกต่างกัน (แสดงได้ทั้งในรูปของลำดับอ่อนที่เข้มงวดหรือลำดับก่อนทั้งหมด) บนเซตที่มีสมาชิกจำนวนหนึ่ง จะกำหนดโดยลำดับต่อไปนี้ (ลำดับA000670ในOEIS ): ${\displaystyle n}$

โปรดทราบว่าS ( n , k )หมายถึงจำนวนสเตอร์ลิงชนิดที่สอง

ตัวเลขเหล่านี้เรียกอีกอย่างว่าตัวเลขฟูบินีหรือตัวเลขเบลล์แบบเรียงลำดับ

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

ต่างจากลำดับบางส่วน ตระกูลของลำดับอ่อนบนเซตจำกัดที่กำหนดนั้นโดยทั่วไปแล้วจะไม่เชื่อมต่อกันด้วยการเคลื่อนไหวที่เพิ่มหรือลบความสัมพันธ์ลำดับเดียวไปยังหรือจากลำดับที่กำหนด ตัวอย่างเช่น สำหรับสามองค์ประกอบ ลำดับที่องค์ประกอบทั้งสามถูกผูกไว้จะแตกต่างจากลำดับอ่อนอื่น ๆ บนเซตเดียวกันอย่างน้อยสองคู่ ไม่ว่าจะเป็นในลำดับอ่อนที่เข้มงวดหรือในสัจพจน์ลำดับก่อนหน้าทั้งหมด อย่างไรก็ตาม การเคลื่อนไหวอีกแบบหนึ่งเป็นไปได้ ซึ่งลำดับอ่อนบนเซตจะเชื่อมต่อกันมากขึ้น กำหนดให้การแบ่งแยกเป็นลำดับอ่อนที่มีชั้นสมมูลสองชั้น และกำหนดให้การแบ่งแยกเข้ากัน ได้ กับลำดับอ่อนที่กำหนด หากองค์ประกอบสองตัวใด ๆ ที่มีความสัมพันธ์กันในลำดับนั้นมีความสัมพันธ์กันในลักษณะเดียวกันหรือถูกผูกไว้ในการแบ่งแยก หรืออีกทางหนึ่ง การแบ่งแยกอาจถูกกำหนดให้เป็นการตัดของเดเดคินด์สำหรับลำดับอ่อน จากนั้นลำดับอ่อนอาจถูกกำหนดลักษณะโดยเซตของการแบ่งแยกที่เข้ากันได้ สำหรับเซตจำกัดของรายการที่มีป้ายกำกับ คู่ลำดับอ่อนทุกคู่สามารถเชื่อมต่อกันได้ด้วยลำดับการเคลื่อนไหวที่เพิ่มหรือลบการแบ่งแยกทีละหนึ่งรายการไปยังหรือจากเซตของการแบ่งแยกนี้ ยิ่งไปกว่านั้นกราฟที่ไม่มีทิศทางซึ่งมีลำดับอ่อนเป็นจุดยอด และการเคลื่อนไหวเหล่านี้เป็นขอบ จะก่อให้เกิดลูกบาศก์บางส่วน^{[ 15 ]}

ในทางเรขาคณิต ลำดับทั้งหมดของเซตจำกัดที่กำหนดอาจแสดงเป็นจุดยอดของเพอร์มูโตเฮดรอนและการแบ่งแยกบนเซตเดียวกันนี้แสดงเป็นหน้าของเพอร์มูโตเฮดรอน ในการแสดงทางเรขาคณิตนี้ ลำดับอ่อนบนเซตจะสอดคล้องกับหน้าของมิติที่แตกต่างกันทั้งหมดของเพอร์มูโตเฮดรอน (รวมถึงเพอร์มูโตเฮดรอนเอง แต่ไม่รวมเซตว่างเป็นหน้า) มิติร่วมของหน้าจะให้จำนวนชั้นสมมูลในลำดับอ่อนที่สอดคล้องกัน^{[ 16 ]}ในการแสดงทางเรขาคณิตนี้ ลูกบาศก์บางส่วนของการเคลื่อนย้ายบนลำดับอ่อนคือกราฟที่อธิบายความสัมพันธ์การครอบคลุมของแลตทิซหน้าของเพอร์มูโตเฮดรอน

ตัวอย่างเช่น สำหรับเพอร์มูโทเฮดรอนที่มีสามองค์ประกอบนั้นก็คือรูปหกเหลี่ยมปกติ แลตทิซของหน้าของรูปหกเหลี่ยม (โดยรวมรูปหกเหลี่ยมเองเป็นหน้า แต่ไม่รวมเซตว่าง) มีองค์ประกอบสิบสามอย่าง ได้แก่ รูปหกเหลี่ยมหนึ่งรูป ขอบหกอัน และจุดยอดหกจุด ซึ่งสอดคล้องกับการเรียงลำดับแบบอ่อนที่ผูกติดกันอย่างสมบูรณ์หนึ่งแบบ การเรียงลำดับแบบอ่อนที่มีการผูกติดกันหนึ่งแบบหกแบบ และการเรียงลำดับทั้งหมดหกแบบ กราฟของการเคลื่อนที่ในการเรียงลำดับแบบอ่อนทั้ง 13 แบบนี้แสดงอยู่ในรูป ${\displaystyle n=3,}$

ดังที่กล่าวไว้ข้างต้น ลำดับที่อ่อนแอมีการประยุกต์ใช้ในทฤษฎีอรรถประโยชน์^{[ 12 ]}ในการเขียนโปรแกรมเชิงเส้นและ ปัญหา การเพิ่มประสิทธิภาพเชิงการจัดเรียง ประเภทอื่นๆ ลำดับความสำคัญของโซลูชันหรือฐานมักจะกำหนดโดยลำดับที่อ่อนแอ ซึ่งกำหนดโดยฟังก์ชันวัตถุประสงค์ ค่าจริง ปรากฏการณ์ของการผูกมัดในลำดับเหล่านี้เรียกว่า "ความเสื่อม" และกฎการแก้ความผูกมัดหลายประเภทถูกนำมาใช้เพื่อปรับปรุงลำดับที่อ่อนแอนี้ให้เป็นลำดับทั้งหมดเพื่อป้องกันปัญหาที่เกิดจากความเสื่อม^{[ 17 ]}

ลำดับที่อ่อนแอยังถูกนำมาใช้ในวิทยาศาสตร์คอมพิวเตอร์ใน อัลกอริธึมที่ใช้ การปรับปรุงการแบ่งส่วนสำหรับการค้นหาแบบกว้างตามลำดับตัวอักษรและการจัดลำดับเชิงโทโพโลยีตามลำดับตัวอักษรในอัลกอริธึมเหล่านี้ ลำดับที่อ่อนแอบนจุดยอดของกราฟ (แสดงเป็นตระกูลของเซตที่แบ่งจุดยอด พร้อมกับรายการที่เชื่อมโยงแบบสองทางที่ให้ลำดับทั้งหมดบนเซต) จะได้รับการปรับปรุงอย่างค่อยเป็นค่อยไปตลอดการทำงานของอัลกอริธึม จนในที่สุดจะได้ลำดับทั้งหมดซึ่งเป็นผลลัพธ์ของอัลกอริธึม^{[ 18 ]}

ในไลบรารีมาตรฐานสำหรับภาษาการเขียนโปรแกรมC++ ชนิดข้อมูล set และ multisetจะเรียงลำดับอินพุตตามฟังก์ชันการเปรียบเทียบที่ระบุไว้ในขณะที่สร้างอินสแตนซ์เทมเพลต และถือว่าใช้การเรียงลำดับแบบอ่อนที่เข้มงวด^{[ 2 ]}

• ความสามารถในการเปรียบเทียบ  – คุณสมบัติขององค์ประกอบที่เกี่ยวข้องกันโดยความไม่เท่าเทียมกัน
• การสั่งซื้อล่วงหน้า  – ความสัมพันธ์ทวิภาคแบบสะท้อนและถ่ายทอด
• ส่วนประกอบอ่อน  – การแบ่งกลุ่มจุดยอดของกราฟทิศทาง − เซตย่อยที่เทียบเท่ากันในลำดับอ่อนที่ละเอียดที่สุดซึ่งสอดคล้องกับความสัมพันธ์ที่กำหนด