ความสัมพันธ์ทวิภาคแบบถ่ายทอด  วี ที อี
สมมาตร แอนติสมมาตร เชื่อมต่อแล้ว มีเหตุผลที่ดี ได้เข้าร่วมแล้ว ได้พบปะแล้ว สะท้อนกลับ ไร้ปฏิกิริยาตอบสนอง ไม่สมมาตร โททอลเซมิคอนเน็กซ์ ต่อต้านปฏิกิริยาสะท้อน ความสัมพันธ์สมมูล วาย ✗ ✗ ✗ ✗ ✗ วาย ✗ ✗ สั่งซื้อล่วงหน้า(กึ่งสั่งซื้อ) ✗ ✗ ✗ ✗ ✗ ✗ วาย ✗ ✗ คำสั่งซื้อบางส่วน ✗ วาย ✗ ✗ ✗ ✗ วาย ✗ ✗ ยอดสั่งซื้อล่วงหน้าทั้งหมด ✗ ✗ วาย ✗ ✗ ✗ วาย ✗ ✗ คำสั่งซื้อทั้งหมด ✗ วาย วาย ✗ ✗ ✗ วาย ✗ ✗ การสั่งซื้อล่วงหน้า ✗ ✗ วาย วาย ✗ ✗ วาย ✗ ✗ การจัดลำดับแบบกึ่งดี ✗ ✗ ✗ วาย ✗ ✗ วาย ✗ ✗ การจัดระเบียบที่ดี ✗ วาย วาย วาย ✗ ✗ วาย ✗ ✗ โครงตาข่าย ✗ วาย ✗ ✗ วาย วาย วาย ✗ ✗ ข้อต่อเซมิแลตติซ ✗ วาย ✗ ✗ วาย ✗ วาย ✗ ✗ มีท-เซมิแลตติซ ✗ วาย ✗ ✗ ✗ วาย วาย ✗ ✗ ลำดับบางส่วนที่เข้มงวด ✗ วาย ✗ ✗ ✗ ✗ ✗ วาย วาย คำสั่งอ่อนที่เข้มงวด ✗ วาย ✗ ✗ ✗ ✗ ✗ วาย วาย ลำดับที่เข้มงวดทั้งหมด ✗ วาย วาย ✗ ✗ ✗ ✗ วาย วาย สมมาตร แอนติสมมาตร เชื่อมต่อแล้ว มีเหตุผลที่ดี ได้เข้าร่วมแล้ว ได้พบปะแล้ว สะท้อนกลับ ไร้ปฏิกิริยาตอบสนอง ไม่สมมาตร คำจำกัดความสำหรับทุกคน${\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{ or }}&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}}}$
Yแสดงว่าคุณสมบัติของคอลัมน์นั้นเป็นจริงเสมอสำหรับพจน์ของแถวนั้น (ทางซ้ายสุด) ในขณะที่✗แสดงว่าคุณสมบัตินั้นไม่ได้รับการรับประกันโดยทั่วไป (อาจเป็นจริงหรือไม่ก็ได้) ตัวอย่างเช่น ความสัมพันธ์สมมูลทุกความสัมพันธ์เป็นสมมาตร แต่ไม่จำเป็นต้องเป็นปฏิสมมาตรจะแสดงด้วยYในคอลัมน์ "สมมาตร" และ✗ในคอลัมน์ "ปฏิสมมาตร" ตามลำดับ นิยามทั้งหมดล้วนต้องการความสัมพันธ์ที่เป็นเนื้อเดียวกัน โดยปริยาย${\displaystyle R}$เป็นกริยาที่ต้องการกรรม : สำหรับทุกสิ่ง${\displaystyle a,b,c,}$ถ้า${\displaystyle aRb}$และ${\displaystyle bRc}$แล้ว${\displaystyle aRc.}$ คำจำกัดความของคำศัพท์บางคำอาจต้องการคุณสมบัติเพิ่มเติมที่ไม่ได้ระบุไว้ในตารางนี้

ในทางคณิตศาสตร์โดยเฉพาะอย่างยิ่งในทฤษฎีลำดับลำดับก่อน (preorder)หรือลำดับกึ่ง (quasiorder)คือความสัมพันธ์ทวิภาคที่มีคุณสมบัติสะท้อนและถ่ายทอดชื่อลำดับก่อน นั้น บ่งบอกว่าลำดับก่อนเกือบ จะเป็น ลำดับบางส่วน (partial order)แต่ก็ไม่เชิงเสียทีเดียว เพราะไม่จำเป็นต้องเป็นความสัมพันธ์แบบปฏิสมมาตร (antisymmetric )

ตัวอย่างที่เป็นธรรมชาติของลำดับก่อนหน้าคือความสัมพันธ์การหาร "x หาร y ลงตัว" ระหว่างจำนวนเต็มความสัมพันธ์นี้เป็นแบบสะท้อนกลับ เนื่องจากจำนวนเต็มทุกตัวหารตัวเองลงตัว นอกจากนี้ยังเป็นแบบถ่ายทอดด้วย แต่ไม่ใช่แบบปฏิสมมาตร เพราะเช่น${\displaystyle 1}$แบ่งแยก${\displaystyle -1}$และ${\displaystyle -1}$แบ่งแยก${\displaystyle 1}$, แต่${\displaystyle -1}$ไม่เท่ากับ${\displaystyle 1}$คำว่า "น้อยที่สุด" ในวลี " ตัวคูณร่วมน้อยที่สุด " หมายถึงลำดับเบื้องต้นนี้ (ตรงกันข้ามกับการใช้ลำดับตามธรรมชาติของจำนวนเต็ม เช่น${\displaystyle 4}$และ${\displaystyle 6}$มีตัวคูณร่วม${\displaystyle 24}$,${\displaystyle 12}$,${\displaystyle 0}$,${\displaystyle -12}$,${\displaystyle -24}$...แต่ไม่ใช่แม้แต่คนเดียว)

ลำดับก่อนหน้า (Preorders) เกี่ยวข้องอย่างใกล้ชิดกับความสัมพันธ์สมมูล (equivalence relations ) และลำดับบางส่วน (partial orders) (แบบไม่เข้มงวด) ทั้งสองอย่างนี้เป็นกรณีพิเศษของลำดับก่อนหน้า: ลำดับก่อนหน้าแบบปฏิสมมาตร (antisymmetric preorder) คือลำดับบางส่วน และ ลำดับก่อนหน้า แบบสมมาตร (symmetric preorder) คือความสัมพันธ์สมมูล ยิ่งไปกว่านั้น ลำดับก่อนหน้าบนเซต${\displaystyle X}$สามารถนิยามได้อย่างเทียบเท่าว่าเป็นความสัมพันธ์สมมูลบน${\displaystyle X}$พร้อมกับลำดับบางส่วนบนเซตของชั้นสมมูลดังภาพประกอบ เช่นเดียวกับลำดับบางส่วนและความสัมพันธ์สมมูล ลำดับก่อนหน้า (บนเซตที่ไม่ว่าง) จะไม่สมมาตรเลย

ลำดับก่อนหน้า (preorder) สามารถมองเห็นได้ในรูปของกราฟแบบมีทิศทางโดยที่องค์ประกอบของเซตจะสอดคล้องกับจุดยอด และความสัมพันธ์ของลำดับระหว่างคู่ขององค์ประกอบจะสอดคล้องกับขอบแบบมีทิศทางระหว่างจุดยอด แต่ในทางกลับกันนั้นไม่เป็นจริง: กราฟแบบมีทิศทางส่วนใหญ่ไม่ใช่ทั้งแบบสะท้อน (reflexive) และแบบถ่ายทอด (transitive) ลำดับก่อนหน้าที่เป็นแบบสมมาตร (antisymmetric) จะไม่มีวัฏจักรอีกต่อไป มันเป็นลำดับบางส่วน (partial order) และสอดคล้องกับกราฟแบบมีทิศทางที่ไม่มีวัฏจักร (directed acyclic graph ) ลำดับก่อนหน้าที่เป็นแบบสมมาตร (symmetric) คือความสัมพันธ์สมมูล (equivalence relation) อาจคิดได้ว่าได้สูญเสียเครื่องหมายบอกทิศทางบนขอบของกราฟไปแล้ว โดยทั่วไป กราฟแบบมีทิศทางที่สอดคล้องกับลำดับก่อนหน้าอาจมีส่วนประกอบที่ไม่เชื่อมต่อกันหลายส่วน

การสั่งซื้อล่วงหน้ามักจะระบุไว้ว่า${\displaystyle \,\lesssim \,}$หรือ${\displaystyle \,\leq \,}$.

ความสัมพันธ์แบบไบนารี${\displaystyle \,\lesssim \,}$ในฉาก${\displaystyle X}$เรียกว่าลำดับก่อนหน้าหรือลำดับเสมือนถ้าเป็นกรรมสะท้อนและกรรมถ่ายทอด กล่าวคือ ถ้ามันเป็นไปตามเงื่อนไขต่อไปนี้:

1. การสะท้อนกลับ :${\displaystyle a\lesssim a}$สำหรับทุกคน${\displaystyle a\in X,}$และ
2. คุณสมบัติการถ่ายทอด : ถ้า${\displaystyle a\lesssim b{\text{ and }}b\lesssim c{\text{ then }}a\lesssim c}$สำหรับทุกคน${\displaystyle a,b,c\in X.}$

ชุดที่มีการสั่งซื้อล่วงหน้าเรียกว่าชุดสั่งซื้อล่วงหน้า (หรือproset ) ^{[ 1 ]}

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

โดยใช้ความสัมพันธ์นี้ เราสามารถสร้างลำดับบางส่วนบนเซตผลหาร ได้${\displaystyle X/\sim }$ของความเท่าเทียมกัน โดยการกำหนด${\displaystyle [x]\leq [y]}$ถ้า${\displaystyle x\lesssim y.}$ เรื่องนี้ได้รับการกำหนดไว้อย่างชัดเจนหมายความว่าไม่ขึ้นอยู่กับการเลือกตัวแทนโดยเฉพาะ${\displaystyle x}$และ${\displaystyle y}$ซึ่งเป็นผลมาจากนิยามของ${\displaystyle \,\sim \,}$.

ในทางกลับกัน จากลำดับบางส่วนใดๆ บนการแบ่งส่วนของเซต${\displaystyle X,}$สามารถสร้างคำสั่งซื้อล่วงหน้าได้บน${\displaystyle X}$ตัวมันเอง มีความสัมพันธ์แบบหนึ่งต่อหนึ่งระหว่างลำดับก่อนหน้าและคู่ (การแบ่งกลุ่ม ลำดับบางส่วน)

ตัวอย่าง : ให้${\displaystyle X}$เป็นเซตของประโยค ทั้งหมด (ไม่ว่าจะถูกต้องหรือไม่ถูกต้อง) ในสาขาย่อยใดสาขาหนึ่งของคณิตศาสตร์ เช่นเรขาคณิตนิยาม${\displaystyle p\Leftarrow q}$ถ้า${\displaystyle p}$เป็นผลลัพธ์เชิงตรรกะของ${\displaystyle q}$. แล้ว${\displaystyle \Leftarrow }$เป็นการสั่งซื้อล่วงหน้าบน${\displaystyle X}$ทุกประโยค${\displaystyle p}$สามารถพิสูจน์ได้จากตัวมันเอง (สมบัติสะท้อนกลับ) และถ้า${\displaystyle p}$สามารถพิสูจน์ได้จาก${\displaystyle q}$, และ${\displaystyle q}$จาก${\displaystyle r}$, แล้ว${\displaystyle p}$สามารถพิสูจน์ได้จาก${\displaystyle r}$(สมบัติการถ่ายทอด) ความสัมพันธ์สมมูลที่สอดคล้องกันมักจะแสดงด้วยสัญลักษณ์${\displaystyle p\Leftrightarrow q}$และกำหนดไว้ดังนี้${\displaystyle p\Leftarrow q}$และ${\displaystyle q\Leftarrow p}$ในกรณีนี้${\displaystyle p}$และ${\displaystyle q}$เรียกว่า " สมมูลกันทางตรรกะ " กลุ่มสมมูลของประโยค${\displaystyle p}$คือเซตของประโยคทั้งหมด${\displaystyle q\in X}$ซึ่งเทียบเท่ากันในเชิงตรรกะกับ${\displaystyle p}$อย่างเป็นทางการ:${\displaystyle [p]=\{q\mid p\Leftrightarrow q\}}$ชุดที่สั่งจองล่วงหน้า${\displaystyle (X,\Leftarrow )}$เป็นเซตแบบมีทิศทาง : เมื่อกำหนดประโยคสองประโยค${\displaystyle p,q\in X}$การเชื่อมโยงเชิงตรรกะของพวกเขา${\displaystyle p\wedge q}$ออกเสียงว่า "ทั้งคู่"${\displaystyle p}$และ${\displaystyle q}$"เป็นขอบเขตบนทั่วไปของพวกมัน เนื่องจาก${\displaystyle p}$เป็นผลสืบเนื่องมาจาก${\displaystyle p\wedge q}$และเช่นเดียวกัน${\displaystyle q}$ชุดที่เรียงลำดับบางส่วน${\displaystyle \left(X/\Leftrightarrow ,\Leftarrow \right)}$ดังนั้น จึงเป็นเซตที่มีทิศทางด้วยเช่นกัน ดูพีชคณิตลินเดนบอม-ทาร์สกีสำหรับตัวอย่างที่เกี่ยวข้อง

ถ้าเราเปลี่ยนคุณสมบัติการสะท้อนกลับเป็นคุณสมบัติการไม่สะท้อนกลับ (โดยยังคงคุณสมบัติการถ่ายทอดไว้) เราก็จะได้นิยามของลำดับบางส่วนที่เข้มงวดบน${\displaystyle X}$ด้วยเหตุนี้ คำว่า " ลำดับก่อนหน้าอย่างเคร่งครัด"จึงบางครั้งถูกนำมาใช้แทน "ลำดับบางส่วนอย่างเคร่งครัด" กล่าวคือ นี่คือความสัมพันธ์แบบทวิภาค${\displaystyle \,<\,}$บน${\displaystyle X}$ที่ตรงตามความต้องการ:

1. ภาวะไร้ปฏิกิริยาตอบสนองหรือ ภาวะต่อต้านปฏิกิริยาตอบสนอง: ไม่ใช่${\displaystyle a<a}$สำหรับทุกคน${\displaystyle a\in X;}$นั่นคือ${\displaystyle \,a<a}$เป็นเท็จสำหรับทุกคน${\displaystyle a\in X,}$และ
2. คุณสมบัติการถ่ายทอด : ถ้า${\displaystyle a<b{\text{ and }}b<c{\text{ then }}a<c}$สำหรับทุกคน${\displaystyle a,b,c\in X.}$

ความสัมพันธ์แบบไบนารีทุกรูปแบบ${\displaystyle R}$ในฉาก${\displaystyle X}$สามารถขยายไปสู่การสั่งซื้อล่วงหน้าได้${\displaystyle X}$โดยการใช้การปิดแบบถ่ายทอดและการปิดแบบสะท้อนกลับ${\displaystyle R^{+=}.}$ การปิดแบบส่งผ่านบ่งชี้ถึงการเชื่อมต่อเส้นทางใน${\displaystyle R:xR^{+}y}$ก็ต่อเมื่อมี${\displaystyle R}$- เส้นทางจาก${\displaystyle x}$ถึง${\displaystyle y.}$

ลำดับก่อนหน้าตกค้างซ้ายที่เกิดจากความสัมพันธ์แบบไบนารี

เมื่อกำหนดความสัมพันธ์แบบไบนารี${\displaystyle R,}$องค์ประกอบเสริม${\displaystyle R\backslash R={\overline {R^{\textsf {T}}\circ {\overline {R}}}}}$สร้างลำดับก่อนหน้าที่เรียกว่า^ส่วนที่เหลือด้านซ้าย [ ^{5 ]}โดยที่${\displaystyle R^{\textsf {T}}}$แสดงถึงความสัมพันธ์ผกผันของ${\displaystyle R,}$และ${\displaystyle {\overline {R}}}$แสดงถึง ความสัมพันธ์ ส่วนเติมเต็มของ${\displaystyle R,}$ในขณะที่${\displaystyle \circ }$แสดงถึงการประกอบความสัมพันธ์

ถ้าการสั่งซื้อล่วงหน้าเป็นแบบสมมาตรผกผัน ด้วย นั่นคือ${\displaystyle a\lesssim b}$และ${\displaystyle b\lesssim a}$หมายความว่า${\displaystyle a=b,}$ดังนั้นจึงเป็นการ สั่งซื้อ บางส่วน

ในทางกลับกัน ถ้ามันสมมาตรนั่นคือ ถ้า${\displaystyle a\lesssim b}$หมายความว่า${\displaystyle b\lesssim a,}$ดังนั้น มันจึงเป็น ความ สัมพันธ์สมมูล

การสั่งซื้อล่วงหน้าจะเสร็จสมบูรณ์หาก${\displaystyle a\lesssim b}$หรือ${\displaystyle b\lesssim a}$สำหรับทุกคน${\displaystyle a,b\in X.}$

คลาสที่สั่งจองล่วงหน้าคือคลาสที่มีสินค้าสั่งจองล่วงหน้าติดอยู่ ทุกชุดสินค้าถือเป็นคลาส และดังนั้น ทุกชุดสินค้าที่สั่งจองล่วงหน้า ก็ถือเป็นคลาสที่สั่งจองล่วงหน้าเช่นกัน

การสั่งซื้อล่วงหน้ามีบทบาทสำคัญในหลายสถานการณ์:

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

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

ดังที่ได้อธิบายไว้ข้างต้น มีความสัมพันธ์แบบ 1 ต่อ 1 ระหว่างลำดับเบื้องต้นและคู่ (พาร์ติชัน ลำดับบางส่วน) ดังนั้น จำนวนลำดับเบื้องต้นจึงเป็นผลรวมของจำนวนลำดับบางส่วนในแต่ละพาร์ติชัน ตัวอย่างเช่น:

สำหรับ${\displaystyle a\lesssim b,}$ช่วงเวลา${\displaystyle [a,b]}$คือเซตของจุดxที่สอดคล้องกับเงื่อนไข${\displaystyle a\lesssim x}$และ${\displaystyle x\lesssim b,}$เขียนด้วย${\displaystyle a\lesssim x\lesssim b.}$ประกอบด้วยจุดอย่างน้อยที่สุดคือจุดaและbเราอาจเลือกที่จะขยายคำจำกัดความไปยังทุกคู่ก็ได้${\displaystyle (a,b)}$ช่วงเวลาพิเศษทั้งหมดว่างเปล่า

โดยใช้ความสัมพันธ์ที่เข้มงวดที่สอดคล้องกัน "${\displaystyle <}$นอกจากนี้ยังสามารถกำหนดช่วงเวลาได้อีกด้วย${\displaystyle (a,b)}$เนื่องจากเซตของจุดxเป็นไปตามเงื่อนไข${\displaystyle a<x}$และ${\displaystyle x<b,}$เขียนด้วย${\displaystyle a<x<b.}$ช่วงเปิดอาจว่างเปล่าได้แม้ว่า${\displaystyle a<b.}$

อีกด้วย${\displaystyle [a,b)}$และ${\displaystyle (a,b]}$สามารถนิยามได้ในลักษณะเดียวกัน

• ลำดับบางส่วน – ลำดับก่อนหน้าที่ไม่สมมาตร
• ความสัมพันธ์สมมูล – ลำดับก่อนหน้าที่สมมาตร
• ยอดสั่งซื้อล่วงหน้าทั้งหมด – ยอดสั่งซื้อล่วงหน้าที่รวมทั้งหมด
• คำสั่งซื้อทั้งหมด – คำสั่งซื้อล่วงหน้าที่มีลักษณะสมมาตรและสมบูรณ์
• ชุดกำกับ
• หมวดหมู่ของชุดที่สั่งจองล่วงหน้า
• การสั่งซื้อล่วงหน้า
• การจัดลำดับแบบกึ่งดี