กลับไปหน้าบทความ

อ่าน 18 นาที

ชุดที่สั่งซื้อบางส่วน

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

ชุดที่สั่งซื้อบางส่วน

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

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

รูปที่ 1แผนภาพHasseของเซตย่อยทั้งหมดของเซตที่มีสามองค์ประกอบเรียงลำดับตามการรวมเซตที่เชื่อมต่อกันด้วยเส้นทางขึ้น เช่นและสามารถเปรียบเทียบกันได้ ในขณะที่ เช่นและไม่สามารถ เปรียบเทียบกันได้

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

ในทางทฤษฎี ลำดับบางส่วน (partial order) คือความสัมพันธ์ทวิภาคเอกพันธุ์ (homogeneous binary relation)ที่มีคุณสมบัติสะท้อนกลับ ( reflexive) สมมาตรผกผัน ( antisymmetric ) และถ่ายทอด (transitive ) เซตที่มีลำดับบางส่วน ( poset ) คือคู่ลำดับ ที่ประกอบด้วยเซต(เรียกว่าเซตพื้นฐานของ) และลำดับบางส่วนบนเซตนั้นเมื่อความหมายชัดเจนจากบริบทและไม่มีความกำกวมเกี่ยวกับลำดับบางส่วนบางครั้งเซตนั้นเองก็เรียกว่า poset ด้วย

ความสัมพันธ์ลำดับบางส่วน

โดยทั่วไป คำว่าลำดับบางส่วน (partial order)มักหมายถึงความสัมพันธ์ลำดับบางส่วนแบบสะท้อนกลับ (reflexive partial order relations) ซึ่งในบทความนี้เรียกว่า ลำดับบางส่วนแบบ ไม่เข้มงวด (non-strict partial orders) อย่างไรก็ตาม ผู้เขียนบางท่านใช้คำนี้กับความสัมพันธ์ลำดับบางส่วนอีกประเภทหนึ่งที่พบได้ทั่วไป คือ ความสัมพันธ์ลำดับบางส่วนแบบไม่สะท้อนกลับ (irreflexive partial order relations) หรือที่เรียกว่า ลำดับบางส่วนแบบเข้มงวด (strict partial orders) ลำดับบางส่วนแบบเข้มงวดและไม่เข้มงวดสามารถจับคู่แบบหนึ่งต่อหนึ่งได้ดังนั้นสำหรับทุกลำดับบางส่วนแบบเข้มงวด จะมีลำดับบางส่วนแบบไม่เข้มงวดที่สอดคล้องกันเพียงหนึ่งเดียว และในทางกลับกัน

คำสั่งซื้อบางส่วน

การสะท้อนกลับที่อ่อนแอ [ 1 ] หรือลำดับบางส่วน ที่ไม่เข้มงวด [ 2 ]ซึ่งโดยทั่วไปเรียกว่าลำดับบางส่วนคือความสัมพันธ์เอกพันธุ์≤ บนเซต ที่สะท้อน สมมาตรผกผันและถ่ายทอดได้กล่าวคือ สำหรับทุก ๆ เซตจะต้องเป็นไปตาม: [ 1 ]

  1. การสะท้อนกลับ : กล่าวคือ ทุกองค์ประกอบมีความสัมพันธ์กับตัวมันเอง
  2. ความไม่สมมาตร : ถ้าและแล้วกล่าวคือ ไม่มีองค์ประกอบที่แตกต่างกันสองอย่างอยู่ก่อนหน้ากัน
  3. คุณสมบัติการถ่ายทอด : ถ้าและแล้ว

ลำดับบางส่วนที่ไม่เข้มงวดเรียกอีกอย่างว่าลำดับก่อนหน้า แบบปฏิ สมมาตร

คำสั่งบางส่วนที่เข้มงวด

ไร้การสะท้อนกลับแข็งแกร่ง [ 1 ]หรือลำดับบางส่วนที่เข้มงวด (strict partial order)คือความสัมพันธ์เอกพันธุ์ (homogeneous relation) บนเซตที่ไม่สะท้อน (irreflexive(asymmetric)และถ่ายทอด (transitive) กล่าวคือ เป็นไปตามเงื่อนไขต่อไปนี้สำหรับทุก ๆ

  1. ความไม่สะท้อนกลับ : กล่าวคือ ไม่มีองค์ประกอบใดเกี่ยวข้องกับตัวมันเอง (เรียกอีกอย่างว่า การต่อต้านการสะท้อนกลับ)
  2. ความไม่สมมาตร : ถ้า เป็นเช่นนั้น ก็ไม่ใช่
  3. คุณสมบัติการถ่ายทอด : ถ้าและแล้ว

ความสัมพันธ์แบบถ่ายทอดจะเป็นแบบไม่สมมาตรก็ต่อเมื่อเป็นแบบไม่สะท้อนกลับ[ 3 ]ดังนั้นคำจำกัดความจึงเหมือนกันหากละเว้นความไม่สะท้อนกลับหรือความไม่สมมาตร (แต่ไม่ใช่ทั้งสองอย่าง)

การสั่งซื้อบางส่วนแบบเข้มงวดเรียกอีกอย่างว่า การ สั่งซื้อล่วงหน้า แบบ เข้มงวด

ความสอดคล้องกันของความสัมพันธ์ลำดับบางส่วนแบบเข้มงวดและไม่เข้มงวด

รูปที่ 2 แผนภาพการสลับที่แสดงถึงความเชื่อมโยงระหว่างความสัมพันธ์แบบเข้มงวด/ไม่เข้มงวดและความสัมพันธ์คู่ขนาน ผ่านการดำเนินการปิดแบบสะท้อนกลับ ( cls ) เคอร์เนลแบบไม่สะท้อนกลับ ( ker ) และความสัมพันธ์ผกผัน ( cnv ) แต่ละความสัมพันธ์แสดงด้วยเมทริกซ์ตรรกะสำหรับเซตลำดับที่มีแผนภาพ Hasseแสดงอยู่ตรงกลาง ตัวอย่างเช่นแถวที่ 3 คอลัมน์ที่ 4 ของเมทริกซ์ด้านล่างซ้ายว่างเปล่า

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

คำสั่งซื้อคู่

คู่(หรือตรงข้าม ) ของความสัมพันธ์ลำดับบางส่วนถูกกำหนดโดยการให้เป็นความสัมพันธ์ผกผันของ กล่าว คือถ้าและเฉพาะเมื่อคู่ ของลำดับบางส่วนที่ไม่เข้มงวดคือลำดับบางส่วนที่ไม่เข้มงวด[ 4 ] และคู่ ของลำดับบางส่วนที่เข้มงวดคือลำดับบางส่วนที่เข้มงวด คู่ ของคู่ ของความสัมพันธ์ คือความสัมพันธ์ดั้งเดิม

สัญกรณ์

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

บางครั้ง คำว่าเซตที่มีลำดับจะถูกใช้เป็นคำย่อสำหรับเซตที่มีลำดับบางส่วนตราบใดที่บริบทชัดเจนว่าไม่ได้หมายถึงลำดับประเภทอื่น โดยเฉพาะอย่างยิ่งเซตที่มีลำดับสมบูรณ์ก็สามารถเรียกว่า "เซตที่มีลำดับ" ได้เช่นกัน โดยเฉพาะในพื้นที่ที่โครงสร้างเหล่านี้พบได้บ่อยกว่าโพเซต ผู้เขียนบางคนใช้สัญลักษณ์ที่แตกต่างจากเช่น[ 6 ]หรือ[ 7 ]เพื่อแยกแยะลำดับบางส่วนออกจากลำดับสมบูรณ์

เมื่อกล่าวถึงลำดับบางส่วนไม่ควรถือว่าเป็นส่วนเติมเต็มของความสัมพันธ์นี้เป็นการผกผันของเคอร์เนลที่ไม่สะท้อนกลับของซึ่งเป็นเซตย่อยของส่วนเติมเต็มของ เสมอแต่จะเท่ากับส่วนเติมเต็มของก็ต่อเมื่อเป็นลำดับทั้งหมด[ a ]

คำจำกัดความทางเลือก

อีกวิธีหนึ่งในการกำหนดลำดับบางส่วนที่พบในวิทยาการคอมพิวเตอร์คือผ่านแนวคิดของการเปรียบเทียบโดยเฉพาะอย่างยิ่งตามที่ได้กำหนดไว้ก่อนหน้านี้ สามารถสังเกตได้ว่าองค์ประกอบสองตัวxและyอาจมีความสัมพันธ์แบบใดแบบหนึ่งจากสี่แบบที่ไม่ซ้ำกันระหว่างกัน ได้แก่x < yหรือx = yหรือx > yหรือxและy ไม่ สามารถเปรียบเทียบกันได้ซึ่งสามารถแสดงได้ด้วยฟังก์ชันที่ส่งคืนรหัสหนึ่งในสี่รหัสเมื่อได้รับองค์ประกอบสองตัว[ 8 ] [ 9 ]คำจำกัดความนี้เทียบเท่ากับลำดับบางส่วนบนเซตอยด์โดยที่ความเท่าเทียมกันถือเป็นความสัมพันธ์สมมูล ที่กำหนดไว้ แทนที่จะเป็นความเท่าเทียมกันของเซต[ 10 ]

Wallis นิยามแนวคิดทั่วไปของความสัมพันธ์ลำดับบางส่วนว่าเป็นความสัมพันธ์เอกพันธุ์ ใดๆ ที่เป็นทรานซิทีฟและแอนติสมมาตรซึ่งรวมถึงลำดับบางส่วนแบบสะท้อนและไม่สะท้อนเป็นประเภทย่อย[ 1 ]

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

ตัวอย่าง

ความสัมพันธ์ของการแบ่งส่วน สูงสุด 4
รูปที่ 3กราฟแสดงความสัมพันธ์ระหว่างจำนวนตั้งแต่ 1 ถึง 4 ชุดตัวเลขนี้เรียงลำดับบางส่วน แต่ไม่เรียงลำดับทั้งหมด เนื่องจากมีความสัมพันธ์ระหว่าง 1 กับจำนวนอื่นๆ แต่ไม่มีความสัมพันธ์ระหว่าง 2 กับ 3 หรือ 3 กับ 4

ตัวอย่างมาตรฐานของโพเซตที่เกิดขึ้นในวิชาคณิตศาสตร์ ได้แก่:

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

ลำดับบนผลคูณคาร์ทีเซียนของเซตที่มีลำดับบางส่วน

รูปที่ 4aลำดับตามพจนานุกรม
รูปที่ 4bคำสั่งซื้อสินค้า
รูปที่ 4cการปิดสะท้อนกลับของลำดับผลิตภัณฑ์โดยตรงที่เข้มงวดบนองค์ประกอบที่ครอบคลุมโดย(3, 3)และครอบคลุม(3, 3)จะถูกเน้นด้วยสีเขียวและสีแดงตามลำดับ

เรียงลำดับตามความแข็งแกร่งที่เพิ่มขึ้น กล่าวคือ จำนวนคู่ที่ลดลง ลำดับย่อยที่เป็นไปได้สามแบบบนผลคูณคาร์ทีเซียนของเซตที่มีลำดับย่อยสองเซต ได้แก่ (ดูรูปที่ 4):

ทั้งสามอย่างนี้สามารถนิยามได้ในทำนองเดียวกันสำหรับผลคูณคาร์ทีเซียนของเซตมากกว่าสองเซต

เมื่อนำไปใช้กับปริภูมิเวกเตอร์เรียงลำดับ บน ฟิลด์เดียวกันผลลัพธ์ในแต่ละกรณีก็จะเป็นปริภูมิเวกเตอร์เรียงลำดับเช่นกัน

ดูเพิ่มเติมเกี่ยวกับลำดับในผลคูณคาร์ทีเซียนของเซตที่มีลำดับสมบูรณ์

ผลรวมของเซตที่มีลำดับบางส่วน

อีกวิธีหนึ่งในการรวมโพเซตสองชุด (ที่ไม่ทับซ้อนกัน) คือผลรวมเชิงลำดับ[ 12 ] (หรือผลรวมเชิงเส้น ) [ 13 ] Z = XYซึ่งกำหนดบนการรวมกันของเซตพื้นฐานXและYโดยลำดับaZ bก็ต่อเมื่อ:

  • a , bXโดยที่aX bหรือ
  • a , bYโดยที่aY bหรือ
  • aXและbY

ถ้าโพเซตสองโพเซตมีลำดับที่ดี ผลรวมเชิงลำดับของโพเซตทั้งสองก็จะมีลำดับที่ดีเช่นกัน[ 14 ]

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

แนวคิดที่ได้มา

ตัวอย่างเหล่านี้ใช้เซตลำดับบางส่วนซึ่งประกอบด้วยเซตของเซตย่อยทั้งหมดของเซตที่มีสามสมาชิกโดยเรียงลำดับตามการรวมเซต (ดูรูปที่ 1)

  • aมีความสัมพันธ์กับbเมื่อabนี่ไม่ได้หมายความว่าbจะมีความสัมพันธ์กับa ด้วยเสมอไป เพราะความสัมพันธ์ไม่จำเป็นต้องสมมาตรตัวอย่างเช่น a มีความสัมพันธ์กับ b แต่ b ไม่มีความสัมพันธ์ในทางกลับกัน
  • aและbจะเปรียบเทียบกันได้ก็ต่อเมื่อabหรือbaมิฉะนั้นจะเปรียบเทียบกันไม่ได้ตัวอย่างเช่นและสามารถเปรียบเทียบกันได้ ในขณะที่และไม่สามารถ เปรียบเทียบกันได้
  • ลำดับสมบูรณ์หรือลำดับเชิงเส้นคือลำดับบางส่วนที่ทุกคู่ขององค์ประกอบสามารถเปรียบเทียบกันได้ กล่าวคือ เป็นไป ตามหลักไตรภาคตัวอย่างเช่น จำนวนธรรมชาติที่มีลำดับมาตรฐาน
  • เชน(Chain)คือเซตย่อยของโพเซต (Poset) ที่เป็นเซตที่มีลำดับสมบูรณ์ (Totally Ordered Set) ตัวอย่างเช่นเป็นเชน
  • แอนติเชน (Antichain)คือเซตย่อยของโพเซต (Poset) ที่ไม่มีสมาชิกสองตัวที่แตกต่างกันสามารถเปรียบเทียบกันได้ ตัวอย่างเช่น เซตของสมาชิกเดี่ยว (singletons)
  • กล่าวได้ว่าองค์ประกอบa น้อยกว่าองค์ประกอบb อย่างเคร่งครัด ถ้าabและตัวอย่างเช่นน้อยกว่าอย่างเคร่งครัด
  • กล่าวได้ว่าองค์ประกอบa ถูก ครอบคลุมโดยองค์ประกอบbเขียนแทนด้วยab (หรือa <: b ) ถ้าaน้อยกว่าb อย่างเคร่งครัด และไม่มีองค์ประกอบที่สามcแทรกอยู่ระหว่างทั้งสององค์ประกอบนั้น กล่าวอีกนัยหนึ่งคือ ถ้าทั้งabและเป็นจริง และacbเป็นเท็จสำหรับแต่ละcที่มี โดยใช้ลำดับที่เข้มงวด < ความสัมพันธ์abสามารถเขียนใหม่ได้อย่างเทียบเท่าว่า " a < bแต่ไม่ใช่a < c < bสำหรับc ใดๆ " ตัวอย่างเช่นถูกครอบคลุมโดยแต่ไม่ถูกครอบคลุมโดย

สุดขั้ว

รูปที่ 5รูปด้านบนที่ตัดองค์ประกอบที่มากที่สุดและน้อยที่สุดออกไป ในเซตลำดับที่ลดรูปนี้ แถวบนสุดขององค์ประกอบทั้งหมดเป็น องค์ประกอบ สูงสุดและแถวล่างสุดเป็น องค์ประกอบ ต่ำสุดแต่ไม่มีองค์ประกอบที่มากที่สุดและน้อยที่สุด

ในกลุ่มพยัญชนะคู่ (poset) มีแนวคิดเกี่ยวกับองค์ประกอบที่ "ใหญ่ที่สุด" และ "เล็กที่สุด" อยู่หลายประการดังนี้:

  • สมาชิกที่ใหญ่ที่สุดและสมาชิกที่เล็กที่สุด: สมาชิกหนึ่งๆจะเป็นสมาชิกที่ใหญ่ที่สุดก็ต่อเมื่อสำหรับทุกสมาชิกสมาชิกหนึ่งๆจะ เป็น สมาชิก ที่เล็กที่สุดก็ต่อ เมื่อสำหรับทุกสมาชิกเซตลำดับที่มีสมาชิกเพียงตัวเดียวจะมีสมาชิกที่ใหญ่ที่สุดหรือเล็กที่สุดได้เพียงตัวเดียวเท่านั้น ในตัวอย่างที่เราใช้ สมาชิกเป็นสมาชิกที่ใหญ่ที่สุด และเป็นสมาชิกที่เล็กที่สุด
  • องค์ประกอบสูงสุดและองค์ประกอบต่ำสุด: องค์ประกอบหนึ่งจะเป็นองค์ประกอบสูงสุดก็ต่อเมื่อไม่มีองค์ประกอบอื่นใดที่ทำให้ในทำนองเดียวกัน องค์ประกอบหนึ่งจะเป็นองค์ประกอบต่ำสุดก็ต่อเมื่อไม่มีองค์ประกอบอื่นใดที่ทำให้ถ้าเซตลำดับที่มีจำนวนสมาชิกมากที่สุดมีองค์ประกอบที่ใหญ่ที่สุด องค์ประกอบนั้นจะต้องเป็นองค์ประกอบสูงสุดเพียงหนึ่งเดียว แต่มิเช่นนั้นอาจมีองค์ประกอบสูงสุดมากกว่าหนึ่งตัว และในทำนองเดียวกันสำหรับองค์ประกอบที่เล็กที่สุดและองค์ประกอบต่ำสุด ในตัวอย่างที่เราใช้และคือองค์ประกอบสูงสุดและต่ำสุด เมื่อลบองค์ประกอบเหล่านี้ออก จะเหลือองค์ประกอบสูงสุด 3 ตัวและองค์ประกอบต่ำสุด 3 ตัว (ดูรูปที่ 5)
  • ขอบเขตบนและขอบเขตล่าง : สำหรับเซตย่อยAของPสมาชิกxในPเป็นขอบเขตบนของAถ้าa  ≤  xสำหรับแต่ละสมาชิกaในAโดยเฉพาะอย่างยิ่งxไม่จำเป็นต้องอยู่ในAเพื่อเป็นขอบเขตบนของA ใน ทำนองเดียวกัน สมาชิกxในPเป็นขอบเขตล่างของAถ้าa  ≥  xสำหรับแต่ละสมาชิกaในAสมาชิกที่มากที่สุดในPเป็นขอบเขตบนของPเอง และสมาชิกที่น้อยที่สุดเป็นขอบเขตล่างของPในตัวอย่างของเรา เซตเป็นขอบเขตบนสำหรับกลุ่มของสมาชิก
รูปที่ 6ส่วนหนึ่งของโครงข่ายจำนวนเต็มที่ไม่เป็นลบเรียงลำดับตามการหารลงตัว

ยกตัวอย่างอีกประการหนึ่ง ลองพิจารณาจำนวนเต็ม บวก ที่เรียงลำดับตามการหารลงตัว: 1 เป็นสมาชิกที่เล็กที่สุด เนื่องจากหารสมาชิกอื่นๆ ได้ทั้งหมด ในทางกลับกัน เซตลำดับบางส่วนนี้ไม่มีสมาชิกที่ใหญ่ที่สุด เซตลำดับบางส่วนนี้ไม่มีสมาชิกที่ใหญ่ที่สุดด้วยซ้ำ เนื่องจากg ใดๆ ก็ หาร 2g ได้ซึ่งแตกต่างจาก g ดังนั้นgจึงไม่ใช่สมาชิกที่ใหญ่ที่สุด หากตัดเลข 1 ออกไป โดยยังคงใช้การหารลงตัวเป็นลำดับของสมาชิกที่มากกว่า 1 เซตลำดับบางส่วนที่ได้จะไม่มีสมาชิกที่เล็กที่สุด แต่จำนวนเฉพาะ ใดๆ ก็เป็นสมาชิกที่เล็กที่สุดสำหรับเซตนี้ ในเซตลำดับบางส่วนนี้ 60 เป็นขอบเขตบน (แม้จะไม่ใช่ขอบเขตบนที่เล็กที่สุด) ของเซตย่อยที่ไม่มีขอบเขตล่าง (เนื่องจาก 1 ไม่อยู่ในเซตลำดับบางส่วน) ในทางกลับกัน 2 เป็นขอบเขตล่างของเซตย่อยของกำลังของ 2 ซึ่งไม่มีขอบเขตบน หากรวมเลข 0 เข้าไปด้วย เลข 0 จะเป็นองค์ประกอบที่มากที่สุด เนื่องจากเป็นพหุคูณของจำนวนเต็มทุกจำนวน (ดูรูปที่ 6)

การจับคู่ระหว่างเซตที่มีลำดับบางส่วน

รูปที่ 7aแผนที่รักษาลำดับ แต่ไม่สะท้อนลำดับ (เนื่องจากf ( u ) ≼ f ( v )แต่ไม่ใช่ u v)
รูปที่ 7bไอโซมอร์ฟิซึมลำดับระหว่างตัวหารของ 120 (เรียงลำดับบางส่วนตามการหารลงตัว) และเซตย่อยปิดตัวหารของ{2, 3, 4, 5, 8} (เรียงลำดับบางส่วนตามการรวมเซต)

กำหนดให้เซตที่มีลำดับบางส่วนสองเซต( S , ≤)และ( T , ≼)ฟังก์ชันจะเรียกว่าฟังก์ชันรักษาลำดับหรือฟังก์ชันโมโนโทน หรือฟังก์ชันไอโซโทนถ้าสำหรับ ทุกx ≥ แสดงว่าf ( x )f ( y )ถ้า ( U ,) เป็นเซตที่มีลำดับบางส่วนเช่นกัน และทั้งf ( x ) และ f ( y ) รักษาลำดับ การประกอบกันของฟังก์ชันทั้งสองก็จะรักษาลำดับด้วยฟังก์ชันจะเรียกว่าฟังก์ชันสะท้อนลำดับถ้าสำหรับทุกx f ( y ) แสดงว่าf ( x ) ...ถ้าการฝังลำดับเป็น ฟังก์ชัน หนึ่งต่อหนึ่งทั่วถึงจะเรียกว่าไอโซมอร์ฟิซึมลำดับและลำดับบางส่วน( S , ≤)และ( T , ≼)จะเรียกว่าเป็นไอโซม อร์ฟิก ลำดับไอโซมอร์ฟิกจะมี ไดอะแกรม Hasseที่มีโครงสร้างคล้ายกัน(ดูรูปที่ 7a) สามารถแสดงได้ว่าถ้ามีแผนที่รักษาลำดับและอยู่เช่นนั้นและให้ฟังก์ชันเอกลักษณ์บนSและTตามลำดับ แล้วSและTจะเป็นไอโซมอร์ฟิกลำดับ[ 15 ]

ตัวอย่างเช่น การแมปจากเซตของจำนวนธรรมชาติ (เรียงลำดับตามการหารลงตัว) ไปยังเซตกำลังของจำนวนธรรมชาติ (เรียงลำดับตามการรวมในเซต) สามารถกำหนดได้โดยการนำแต่ละจำนวนไปยังเซตของตัวหารเฉพาะ ของมัน การแมป นี้รักษาลำดับ: ถ้าxหารy ลงตัว ตัวหารเฉพาะของ xแต่ละตัวก็จะเป็นตัวหารเฉพาะของy ด้วย อย่างไรก็ตาม การแมปนี้ไม่เป็นทั้งฟังก์ชันหนึ่งต่อหนึ่ง (เนื่องจากมันแมปทั้ง 12 และ 6 ไปยังเซตกำลัง) และไม่สะท้อนลำดับ (เนื่องจาก 12 ไม่หาร 6 ลงตัว) การนำแต่ละจำนวนไปยังเซตของ ตัวหาร กำลังเฉพาะ ของมันแทน จะกำหนดการแมปที่รักษาลำดับ สะท้อนลำดับ และดังนั้นจึงเป็นการฝังลำดับ มันไม่ใช่ไอโซมอร์ฟิซึมลำดับ (เนื่องจากตัวอย่างเช่น มันไม่ได้แมปจำนวนใดๆ ไปยังเซต) แต่สามารถทำให้เป็นไอโซมอร์ฟิซึมลำดับได้โดยการจำกัดโคโดเมนของมันไว้ที่รูปที่ 7b แสดงเซตย่อยของ และภาพไอโซมอ ร์ฟิกของมันภายใต้gการสร้างไอโซมอร์ฟิซึมลำดับดังกล่าวลงในเซตกำลังสามารถขยายไปสู่ลำดับบางส่วนที่หลากหลาย ซึ่งเรียกว่าแลตทิซแบบกระจายดูทฤษฎีบทการแทนของเบิร์คฮอฟฟ์

จำนวนคำสั่งซื้อบางส่วน

ลำดับA001035ในOEISแสดงจำนวนลำดับย่อยบนเซตขององค์ประกอบที่มีป้ายกำกับ n รายการ:

จำนวนความสัมพันธ์ทวิภาค n องค์ประกอบประเภทต่างๆ
องค์ประกอบ ใดๆสกรรมกริยาสะท้อนกลับสมมาตรสั่งซื้อล่วงหน้าคำสั่งซื้อบางส่วนยอดสั่งซื้อล่วงหน้าทั้งหมดคำสั่งซื้อทั้งหมดความสัมพันธ์สมมูล
0111111111
1221211111
216134843322
3512171646429191365
465,5363,9944,0961,024355219752415
n2 n 22 n ( n −1)2 n ( n +1)/2n k =0k ! S ( n , k )n ! n k =0S ( n , k )
โออีไอเอสA002416A006905A053763A006125A000798A001035A000670A000142เอ000110

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

จำนวนคำสั่งย่อยที่เข้มงวดนั้นเท่ากับจำนวนคำสั่งย่อยทั่วไป

หากนับเฉพาะไอโซม อร์ฟิซึม จะได้ ลำดับ 1, 1, 2, 5, 16, 63, 318, ... (ลำดับA000112ในOEIS )

ชุดย่อย

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

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

ส่วนขยายเชิงเส้น

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

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

ในทฤษฎีหมวดหมู่

ทุก poset (และทุกเซตที่มีลำดับก่อนหน้า ) อาจถือได้ว่าเป็นหมวดหมู่ที่สำหรับวัตถุ x และyจะมีมอร์ฟิซึมจาก x ไปยัง y ได้อย่างมากที่สุดเพียงหนึ่งเดียว กล่าวให้ชัดเจนยิ่งขึ้น ให้hom( x , y ) = {( x , y )}ถ้าxy (และมิฉะนั้นจะเป็นเซตว่าง ) และหมวดหมู่ดังกล่าวบางครั้งเรียกว่า thin

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

ลำดับบางส่วนในปริภูมิเชิงทอพอโลยี

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

ช่วงเวลา

เซตแบบนูนในเซตลำดับบาง ส่วน Pคือเซตย่อยIของPที่มีคุณสมบัติว่า สำหรับxและy ใดๆ ในIและz ใดๆ ในPถ้าxzyแล้วzก็อยู่ในI ด้วย นิยามนี้เป็นการขยายความหมายของช่วงของจำนวนจริงเมื่ออาจเกิดความสับสนกับเซตแบบนูนในเรขาคณิตจะใช้คำว่า " เซต แบบนูนตามลำดับ " แทนคำว่า "เซตแบบนูน"

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

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

  • สำหรับabช่วงปิด[ a , b ]คือเซตของสมาชิกxที่สอดคล้องกับaxb (นั่นคือaxและxb ) โดยช่วงปิดนี้จะต้องมีสมาชิกอย่างน้อยคือaและb
  • โดยใช้ความสัมพันธ์ที่เข้มงวด "<" ช่วงเปิด( a , b )คือเซตของสมาชิกxที่สอดคล้องกับa < x < b (กล่าวคือa < xและx < b ) ช่วงเปิดอาจว่างเปล่าได้แม้ว่าa < bตัวอย่างเช่น ช่วงเปิด(0, 1)บนจำนวนเต็มนั้นว่างเปล่า เนื่องจากไม่มีจำนวนเต็มxใดที่0 < x < 1
  • ช่วงครึ่งเปิด[ a , b )และ( a , b ]ถูกกำหนดในลักษณะเดียวกัน

เมื่อใดก็ตาม ที่เงื่อนไข abไม่เป็นจริง ช่วงทั้งหมดเหล่านี้จะเป็นช่วงว่างเปล่า ทุกช่วงเป็นเซตแบบนูน แต่ข้อความกลับกันนั้นไม่เป็นจริง ตัวอย่างเช่น ในเซตลำดับของตัวหารของ 120 ที่เรียงลำดับตามการหารลงตัว (ดูรูปที่ 7b) เซต {1, 2, 4, 5, 8} เป็นเซตแบบนูน แต่ไม่ใช่ช่วง

ช่วงIจะเป็นช่วงที่มีขอบเขต ถ้ามีสมาชิกที่ทำให้I[ a , b ]ทุกช่วงที่สามารถแสดงได้ในรูปแบบสัญกรณ์ช่วง ย่อมเป็นช่วงที่มีขอบเขตอย่างชัดเจน แต่ข้อความกลับกันนั้นไม่เป็นจริง ตัวอย่างเช่น ให้P = (0, 1)(1, 2)(2, 3)เป็นเซตย่อยของจำนวนจริง เซตย่อย(1, 2)เป็นช่วงที่มีขอบเขต แต่ไม่มีค่าต่ำสุดหรือค่าสูงสุดใน  Pดังนั้นจึงไม่สามารถเขียนในรูปแบบสัญกรณ์ช่วงโดยใช้สมาชิกของ  Pได้

เซตลำดับบางส่วนเรียกว่าเซตจำกัดเฉพาะที่ถ้าช่วงจำกัดทุกช่วงเป็นเซตจำกัด ตัวอย่างเช่น จำนวนเต็มเป็นเซตจำกัดเฉพาะที่ภายใต้การเรียงลำดับตามธรรมชาติ ลำดับพจนานุกรมของผลคูณคาร์ทีเซียนไม่ใช่เซตจำกัดเฉพาะที่ เนื่องจาก(1, 2) ≤ (1, 3) ≤ (1, 4) ≤ (1, 5) ≤ ... ≤ (2, 1)โดยใช้สัญกรณ์ช่วง คุณสมบัติ " aถูกครอบคลุมโดยb " สามารถเขียนใหม่ได้เทียบเท่ากับ

แนวคิดเรื่องช่วงในลำดับบางส่วนนี้ไม่ควรสับสนกับลำดับบางส่วนประเภทเฉพาะที่เรียกว่าลำดับ ช่วง

ดูเพิ่มเติม

หมายเหตุ

  1. ^สามารถดูหลักฐานได้ที่นี่
  2. ^ซึ่งมีอยู่เสมอและเป็นเอกลักษณ์ เนื่องจากถือว่ามีจำนวนจำกัด
  3. ^ดูมพัทธภาพทั่วไป § การเดินทางข้ามเวลา

การอ้างอิง

  1. ^ a b c d Wallis, WD (14 มีนาคม 2013). คู่มือเบื้องต้นสำหรับคณิตศาสตร์เชิงดิสครีต . Springer Science & Business Media. หน้า 100. ISBN 978-1-4757-3826-1.
  2. ^ Simovici, Dan A. & Djeraba, Chabane (2008). "เซตที่มีลำดับบางส่วน" . เครื่องมือทางคณิตศาสตร์สำหรับการทำเหมืองข้อมูล: ทฤษฎีเซต ลำดับบางส่วน คณิตศาสตร์เชิงการจัดเรียง . Springer. ISBN 9781848002012.
  3. ^ Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). "Transitive Closures of Binary Relations I" . Acta Universitatis Carolinae. Mathematica et Physica . 48 (1). Prague: School of Mathematics – Physics Charles University: 55– 69.บทตั้ง 1.1 (iv) แหล่งข้อมูลนี้อ้างถึงความสัมพันธ์ที่ไม่สมมาตรว่าเป็น "ไม่สมมาตรอย่างเคร่งครัด"
  4. ^ Davey & Priestley ( 2002) , หน้า  14–15
  5. ^ Avigad, Jeremy; Lewis, Robert Y.; van Doorn, Floris (29 มีนาคม 2021). "13.2. เพิ่มเติมเกี่ยวกับลำดับ". ตรรกศาสตร์และการพิสูจน์ (ฉบับ 3.18.4). เก็บถาวรจากต้นฉบับเมื่อ 3 เมษายน 2023. สืบค้น เมื่อ 24 กรกฎาคม 2021. ดังนั้นเราจึงสามารถคิดว่าลำดับบางส่วนทุกอันเป็นคู่กัน ซึ่งประกอบด้วยลำดับบางส่วนแบบอ่อนและลำดับบาง ส่วนแบบเข้มงวดที่เกี่ยวข้อง
  6. ^ Rounds, William C. (7 มีนาคม 2002). "สไลด์บรรยาย" (PDF) . EECS 203: คณิตศาสตร์เชิงดิสครีต. สืบค้นเมื่อ23 กรกฎาคม 2021 .
  7. ^ Kwong, Harris (25 เมษายน 2561). "7.4: การเรียงลำดับบางส่วนและการเรียงลำดับทั้งหมด". แบบฝึกหัดแบบเกลียวสำหรับคณิตศาสตร์เชิงดิสครีต . สืบค้นเมื่อ23 กรกฎาคม 2564 .
  8. ^ "โพเซตจำกัด" . คู่มืออ้างอิง Sage 9.2.beta2: Combinatorics . สืบค้นเมื่อ5 มกราคม 2022 . compare_elements( x , y ): เปรียบเทียบxและyในโพเซต ถ้าx < yให้คืนค่า −1 ถ้าx = yให้คืนค่า 0 ถ้าx > yให้คืนค่า 1 ถ้าxและyเปรียบเทียบกันไม่ได้ ให้คืนค่า None
  9. ^ Chen, Peter; Ding, Guoli; Seiden, Steve. เกี่ยวกับการรวม Poset (PDF) (รายงานทางเทคนิค). หน้า 2. สืบค้นเมื่อ 5 มกราคม 2022. การเปรียบเทียบระหว่างสององค์ประกอบ s, t ใน S จะส่งคืนค่าที่แตกต่างกันสามค่า ได้แก่ s≤t, s>t หรือ s|t
  10. ^ Prevosto, Virgile; Jaume, Mathieu (11 กันยายน 2003). การสร้างบทพิสูจน์ในลำดับชั้นของโครงสร้างทางคณิตศาสตร์ CALCULEMUS-2003 – การประชุมวิชาการครั้งที่ 11 ว่าด้วยการบูรณาการการ คำนวณเชิงสัญลักษณ์และการให้เหตุผลเชิงกล โรม ประเทศอิตาลี: Aracne หน้า  89–100
  11. ^ Merrifield, Richard E.; Simmons, Howard E. (1989). วิธีการทางทอพอโลยีในเคมี . นิวยอร์ก: John Wiley & Sons.  หน้า28. ISBN 0-471-83817-9สืบค้นข้อมูลเมื่อ วัน ที่27 กรกฎาคม 2555 เซตที่มีลำดับบางส่วนสามารถแสดงได้อย่างสะดวกด้วยแผนภาพ Hasse ...
  12. ^ Neggers, J.; Kim, Hee Sik (1998), "4.2 ลำดับผลิตภัณฑ์และลำดับพจนานุกรม", Basic Posets , World Scientific, หน้า  62–63 , ISBN 9789810235895
  13. ^ Davey & Priestley ( 2002) , หน้า  17–18
  14. พีอาร์ ฮัลมอส (1974) ทฤษฎีเซตไร้เดียงสา สปริงเกอร์. พี  82 . ไอเอสบีเอ็น 978-1-4757-1645-0.
  15. ^ Davey & Priestley (2002) , หน้า 23–24.
  16. ^ Jech, Thomas (2008) [1973]. สัจพจน์แห่งการเลือก . สำนักพิมพ์โดเวอร์ . ISBN 978-0-486-46624-8.
  17. ^ Ward, LE Jr (1954). "Partially Ordered Topological Spaces" . Proceedings of the American Mathematical Society . 5 (1): 144– 161. doi : 10.1090/S0002-9939-1954-0063016-5 . hdl : 10338.dmlcz/101379 .

โลโก้ Wikimedia Commonsสื่อที่เกี่ยวข้องกับแผนภาพ Hasseใน Wikimedia Commons ซึ่งแต่ละภาพแสดงตัวอย่างของลำดับบางส่วน

  • ลำดับ OEIS A001035 (จำนวนโพเซ็ตที่มี องค์ประกอบที่ติดป้ายกำกับ nตัว)
  • ลำดับ OEIS A000112 (จำนวนเซตที่มีลำดับบางส่วน ("posets") ที่มีองค์ประกอบที่ไม่มีป้ายกำกับจำนวน n ตัว)
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Partially_ordered_set&oldid=1360404056 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ชุดที่สั่งซื้อบางส่วน

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

ความสัมพันธ์ลำดับบางส่วน

โดยทั่วไป คำว่า ลำดับบางส่วน (partial order) มักหมายถึงความสัมพันธ์ลำดับบางส่วนแบบสะท้อนกลับ (reflexive partial order relations) ซึ่งในบทความนี้เรียกว่า ลำดับบางส่วนแบบ ไม่เข้มงวด (non-strict partial orders) อย่างไรก็ตาม...

คำสั่งซื้อบางส่วน

การสะท้อน กลับ ที่ อ่อนแอ [ 1 ] หรือ ลำดับบางส่วน ที่ ไม่เข้มงวด [ 2 ] ซึ่งโดยทั่วไปเรียกว่า ลำดับบางส่วน คือ ความสัมพันธ์เอกพันธุ์ ≤ บน เซต ที่ สะท้อน สมมาตร ผกผัน และ ถ่ายทอด ได้ กล่าวคือ สำหรับทุก ๆ เซตจะต้องเป็นไปตาม: [ 1 ] P {\displaystyle P} a , b , c ∈...

คำสั่งบางส่วนที่เข้มงวด

ไร้การ สะท้อน กลับ แข็งแกร่ง [ 1 ] หรือ ลำดับบางส่วนที่เข้มงวด (strict partial order) คือความสัมพันธ์เอกพันธุ์ (homogeneous relation) บนเซตที่ ไม่สะท้อน (irreflexive ( asymmetric) และ ถ่ายทอด (transitive ) กล่าวคือ เป็นไปตามเงื่อนไขต่อไปนี้สำหรับทุก ๆ P...