ในทางคณิตศาสตร์โดยเฉพาะทฤษฎีลำดับ การเติมเต็มแบบ Dedekind –MacNeilleของเซตที่มีลำดับบางส่วนคือแลตทิซสมบูรณ์ ที่เล็กที่สุด ที่บรรจุเซตนั้นไว้ ชื่อนี้ตั้งตามHolbrook Mann MacNeilleผู้ซึ่งได้กำหนดและสร้างมันขึ้นมาเป็นครั้งแรกในบทความปี 1937 และตั้งตามRichard Dedekindเพราะการสร้างนี้เป็นการขยายการตัดแบบ Dedekindที่ Dedekind ใช้ในการสร้างจำนวนจริงจากจำนวนตรรกยะนอกจากนี้ยังเรียกว่าการเติมเต็มโดยการตัดหรือ การเติมเต็ม แบบปกติ^{[ 1 ]}

เซตที่มีลำดับบางส่วน (poset) ประกอบด้วยเซตขององค์ประกอบพร้อมกับความสัมพันธ์ทวิภาคx ≤ yบนคู่ขององค์ประกอบ ซึ่งเป็นแบบสะท้อน ( x ≤ xสำหรับทุกx ) แบบถ่ายทอด (ถ้าx ≤ yและy ≤ zแล้วx ≤ z ) และแบบปฏิสมมาตร (ถ้าทั้งx ≤ yและy ≤ xเป็นจริง แล้วx = y ) ลำดับตัวเลขปกติบนจำนวนเต็มหรือจำนวนจริงเป็นไปตามคุณสมบัติเหล่านี้ อย่างไรก็ตาม ต่างจากลำดับบนตัวเลข ลำดับบางส่วนอาจมีองค์ประกอบสองตัวที่ไม่สามารถเปรียบเทียบกันได้ กล่าว คือ ทั้งx ≤ yและy ≤ x ไม่ เป็นจริง ตัวอย่างที่คุ้นเคยอีกประการหนึ่งของลำดับบางส่วนคือ ลำดับการ รวม ⊆ บนคู่ของเซต^{[ 2 ]}

ถ้าSเป็นเซตที่มีลำดับบางส่วนการทำให้สมบูรณ์ของSหมายถึงแลตทิซที่สมบูรณ์Lที่มีการฝังลำดับของSลงในL ^{[ 3} ] แลตทิซที่สมบูรณ์คือแลตทิซที่ทุกเซตย่อยขององค์ประกอบของLมีค่าต่ำสุดและค่าสูงสุด^ซึ่งเป็นการขยายคุณสมบัติที่คล้ายคลึงกันของจำนวนจริงการฝังลำดับคือฟังก์ชันที่แมปองค์ประกอบที่แตกต่างกันของSไปยังองค์ประกอบที่แตกต่างกันของLโดยที่แต่ละคู่ขององค์ประกอบในSมีลำดับเดียวกันในLเช่นเดียวกับในSเส้นจำนวนจริงที่ขยาย (จำนวนจริงพร้อมกับ +∞ และ −∞) เป็นการทำให้สมบูรณ์ในความหมายนี้ของจำนวนตรรกยะ: เซตของจำนวนตรรกยะ{3, 3.1, 3.14, 3.141, 3.1415, 3.14159, ...}ไม่มีขอบเขตบนน้อยที่สุดที่เป็นตรรกยะ แต่ในจำนวนจริงมีขอบเขตบนน้อย^{ที่สุด} π [ ^{4 ]}

เซตที่มีลำดับบางส่วนที่กำหนดอาจมีการเติมเต็มที่แตกต่างกันได้หลายแบบ ตัวอย่างเช่น การเติมเต็มหนึ่งของเซตที่มีลำดับบางส่วนS ใดๆ ก็ คือเซตของเซตย่อยที่ปิดจากบนลงล่าง ซึ่ง เรียงลำดับตามการรวมSถูกฝังอยู่ในแลตทิซ (สมบูรณ์) นี้โดยการแมปแต่ละองค์ประกอบxไปยังเซตขององค์ประกอบที่ต่ำกว่าซึ่งน้อยกว่าหรือเท่ากับxผลลัพธ์ที่ได้คือแลตทิซแบบกระจายและใช้ในทฤษฎีบทการแสดงแทนของ Birkhoffอย่างไรก็ตาม อาจมีองค์ประกอบมากกว่าที่จำเป็นในการสร้างการเติมเต็มของS [ ^{5 ] ใน}บรรดาการเติมเต็มแลตทิซที่เป็นไปได้ทั้งหมด การเติมเต็มของ Dedekind–MacNeille เป็นแลตทิซสมบูรณ์ที่เล็กที่สุดที่มีSฝังอยู่^{[ 6 ]}

สำหรับแต่ละเซตย่อยAของเซตที่มีลำดับบางส่วนSให้A ^uแทนเซตของขอบเขตบนของA กล่าว คือ สมาชิกxของSอยู่ในA ^u ก็ต่อ เมื่อxมากกว่าหรือเท่ากับทุกสมาชิกในAในทำนองเดียวกัน ให้A ^ℓแทนเซตของขอบเขตล่างของAซึ่งก็คือสมาชิกที่น้อยกว่าหรือเท่ากับทุกสมาชิกในAดังนั้น การเติมเต็มแบบ Dedekind–MacNeille ของSประกอบด้วยเซตย่อยA ทั้งหมด ซึ่ง

( A ^u ) ^ℓ = A ,

เรียงลำดับตามการรวม: A ≤ Bในการเติมเต็มก็ต่อเมื่อA ⊆ Bเป็นเซต^{[ 7 ]}

องค์ประกอบxของSฝังตัวลงในส่วนเติมเต็มเป็นอุดมคติหลักเซต↓ ขององค์ประกอบที่น้อยกว่าหรือเท่ากับxจากนั้น(↓ ) ^uคือเซตขององค์ประกอบที่มากกว่าหรือเท่ากับxและ((↓ ) ^u ) ^ℓ = ↓ ซึ่งแสดงให้เห็นว่า↓ เป็นสมาชิกของส่วนเติมเต็มจริง ๆ การแมปจากxไปยัง↓ เป็นการฝังลำดับ^{[ 7 ]}

บางครั้งมีการใช้คำจำกัดความทางเลือกของการเติมเต็ม Dedekind–MacNeille ที่คล้ายกับคำจำกัดความของการตัด Dedekind มากขึ้น^{[ 8 ]}ในเซตที่มีลำดับบางส่วนSให้กำหนดการตัดเป็นคู่ของเซต( A , B )ซึ่งA ^u = BและA = B ^ℓถ้า( A , B )เป็นการตัดแล้วAจะสอดคล้องกับสมการ( A ^u ) ^ℓ = Aและในทางกลับกัน ถ้า( A ^u ) ^ℓ = Aแล้ว( A , A ^u )ก็เป็นการตัดเช่นกัน ดังนั้น เซตของการตัดที่มีลำดับบางส่วนโดยการรวมบนเซตล่างของการตัด (หรือความสัมพันธ์การรวมแบบย้อนกลับบนเซตบน) จะให้คำจำกัดความที่เทียบเท่าของการเติมเต็ม Dedekind–MacNeille ^{[ 9 ]}

ด้วยคำจำกัดความทางเลือก ทั้งการดำเนินการ join และ meet ของแลตทิซที่สมบูรณ์จะมีคำอธิบายสมมาตร: ถ้า( A , B )เป็นการตัดในตระกูลการตัดใดๆ แล้ว meet ของการตัดเหล่านี้คือการตัด( L , L ^u )โดยที่L = ∩ A และ join คือการตัด( U ^ℓ , U )โดยที่U = ∩ B . ^{[ 9 ]}

ถ้าเป็นเซตของจำนวนตรรกยะซึ่งมองว่าเป็นเซตที่มีลำดับสมบูรณ์ด้วยลำดับตัวเลขปกติ แล้วองค์ประกอบแต่ละตัวของการเติมเต็ม Dedekind–MacNeille ของอาจมองได้ว่าเป็นการตัด Dedekindและการเติมเต็ม Dedekind–MacNeille ของคือการเรียงลำดับสมบูรณ์บนจำนวนจริงพร้อมกับค่าเพิ่มเติมอีกสองค่า^{[ 10 ]}${\displaystyle \mathbb {Q} }$${\displaystyle \mathbb {Q} }$${\displaystyle \mathbb {Q} }$${\displaystyle \pm \infty }$

ถ้าSเป็นแอนติเชน (เซตขององค์ประกอบที่ไม่มีสององค์ประกอบใดเปรียบเทียบกันได้) การเติมเต็ม Dedekind–MacNeille ของSจะประกอบด้วยSเองพร้อมกับองค์ประกอบเพิ่มเติมอีกสององค์ประกอบ คือ องค์ประกอบล่างที่อยู่ต่ำกว่าทุกองค์ประกอบใน^Sและองค์ประกอบบนที่อยู่เหนือทุกองค์ประกอบในS ^{[ 11} ]

ถ้าOเป็นเซตจำกัดของวัตถุ และAเป็นเซตจำกัดของคุณลักษณะเอกภาคสำหรับวัตถุในOแล้วสามารถสร้างลำดับบางส่วนที่มีความสูงสองได้ โดยที่องค์ประกอบของลำดับบางส่วนคือวัตถุและคุณลักษณะ และx ≤ yเมื่อxเป็นวัตถุที่มีคุณลักษณะ  yสำหรับลำดับบางส่วนที่กำหนดในลักษณะนี้ การเติมเต็ม Dedekind–MacNeille ของSเรียกว่าแลตทิซแนวคิดและมีบทบาทสำคัญในสาขาการวิเคราะห์แนวคิดเชิงรูปธรรม^{[ 12 ]}

การเติมเต็มแบบ Dedekind–MacNeille ของเซตที่มีลำดับบางส่วนSคือแลตทิซที่สมบูรณ์ที่เล็กที่สุดที่มีSฝังอยู่ภายใน ในแง่ที่ว่า ถ้าLเป็นการเติมเต็มแลตทิซใดๆ ของS แล้ว การเติมเต็มแบบ Dedekind–MacNeille จะเป็นเซตย่อยที่มีลำดับบางส่วนของL ^{[ 6 ]}เมื่อS เป็นเซตจำกัด การเติมเต็มของมันก็จะเป็นเซตจำกัดเช่นกัน และมีจำนวนองค์ประกอบน้อยที่สุดในบรรดาแลตทิซ ที่สมบูรณ์จำกัดทั้งหมดที่มีS อยู่ ^{[ 12 ]}

เซตลำดับบางส่วนSมีความหนาแน่นของการรวมและความหนาแน่นของการพบกันในการเติมเต็มของ Dedekind–MacNeille กล่าวคือ ทุกองค์ประกอบของการเติมเต็มเป็นการรวมกันของกลุ่มองค์ประกอบบางกลุ่มของSและยังเป็นการพบกันของกลุ่มองค์ประกอบบางกลุ่มในSด้วย^{[ 13 ]}การเติมเต็มของ Dedekind–MacNeille มีลักษณะเฉพาะในกลุ่มการเติมเต็มของSด้วยคุณสมบัตินี้^{[ 14 ]}

การเติมเต็ม Dedekind–MacNeille ของพีชคณิตบูลีนคือพีชคณิตบูลีนที่สมบูรณ์ผลลัพธ์นี้เรียกว่าทฤษฎีบท Glivenko–Stoneตามชื่อของValery Ivanovich GlivenkoและMarshall Stone [ ^{15 ] ใน}ทำนองเดียวกัน การเติมเต็ม Dedekind–MacNeille ของแลตทิซตกค้างคือแลตทิซตกค้างที่สมบูรณ์^{[ 16 ]}อย่างไรก็ตาม การเติมเต็มของแลตทิซแบบกระจายไม่จำเป็นต้องเป็นแบบกระจาย และการเติมเต็มของแลตทิซแบบโมดูลาร์อาจไม่ยังคงเป็นแบบโมดูลาร์^{[ 17 ]}

การเติมเต็มของ Dedekind–MacNeille เป็นแบบคู่ตัวเอง: การเติมเต็มของคู่ของลำดับบางส่วนจะเหมือนกับคู่ของการเติมเต็ม^{[ 18 ]}

การเติมเต็ม Dedekind–MacNeille ของS มี มิติลำดับเดียวกับSเอง^{[ 19 ]}

ในหมวดหมู่ของเซตที่มีลำดับบางส่วนและฟังก์ชันโมโนโทนิกระหว่างเซตที่มีลำดับบางส่วน แลตทิซที่สมบูรณ์จะสร้างวัตถุแบบฉีดสำหรับการฝังลำดับและการเติมเต็ม Dedekind–MacNeille ของSคือ เปลือก แบบฉีดของ  S ^{[ 20 ]}

นักวิจัยหลายคนได้ตรวจสอบอัลกอริธึมสำหรับการสร้างการเติมเต็ม Dedekind–MacNeille ของเซตที่มีลำดับบางส่วนแบบจำกัด การเติมเต็ม Dedekind–MacNeille อาจมีขนาดใหญ่กว่าลำดับบางส่วนที่มาจากเลขชี้กำลัง^{[ 12 ]}และขอบเขตเวลาสำหรับอัลกอริธึมดังกล่าวโดยทั่วไปจะระบุในลักษณะที่ไวต่อผลลัพธ์โดยขึ้นอยู่กับทั้งจำนวนnขององค์ประกอบของลำดับบางส่วนที่ป้อนเข้า และจำนวนcขององค์ประกอบของการเติมเต็ม

Ganter & Kuznetsov (1998)อธิบายอัลกอริทึมแบบเพิ่มทีละขั้น โดยที่ลำดับบางส่วนที่ป้อนเข้ามาจะถูกสร้างขึ้นโดยการเพิ่มองค์ประกอบทีละหนึ่งรายการ ในแต่ละขั้นตอน ความสมบูรณ์ของลำดับบางส่วนที่เล็กกว่าจะถูกขยายเพื่อสร้างความสมบูรณ์ของลำดับบางส่วนที่ใหญ่กว่า ในวิธีการของพวกเขา ความสมบูรณ์จะถูกแทนด้วยรายการของส่วนตัดที่ชัดเจน ส่วนตัดแต่ละส่วนของลำดับบางส่วนที่เพิ่มขึ้น ยกเว้นส่วนที่เซตทั้งสองตัดกันในองค์ประกอบใหม่ จะเป็นส่วนตัดจากลำดับบางส่วนก่อนหน้า หรือเกิดจากการเพิ่มองค์ประกอบใหม่ไปยังด้านใดด้านหนึ่งของส่วนตัดจากลำดับบางส่วนก่อนหน้า ดังนั้นอัลกอริทึมของพวกเขาจึงต้องการเพียงคู่ทดสอบของเซตในรูปแบบนี้เพื่อพิจารณาว่าเซตใดเป็นส่วนตัด เวลาสำหรับการใช้วิธีการของพวกเขาในการเพิ่มองค์ประกอบเดียวให้กับความสมบูรณ์ของลำดับบางส่วนคือO ( cnw )โดยที่wคือความกว้างของลำดับบางส่วน นั่นคือขนาดของแอนติเชนที่ ใหญ่ที่สุด ดังนั้น เวลาในการคำนวณความสมบูรณ์ของคำสั่งซื้อบางส่วนที่กำหนดคือO ( cn ² w ) = O( cn ³ ) . ^{[ 12 ]}

ดังที่Jourdan, Rampon & Jard (1994)สังเกต ปัญหาของการแสดงรายการตัดทั้งหมดในเซตที่มีลำดับบางส่วนสามารถกำหนดได้เป็นกรณีพิเศษของปัญหาที่ง่ายกว่า นั่นคือ การแสดงรายการแอนติเชน สูงสุดทั้งหมด ในเซตที่มีลำดับบางส่วนที่แตกต่างกัน ถ้าPเป็นเซตที่มีลำดับบางส่วนใดๆ ให้Qเป็นลำดับบางส่วนที่มีองค์ประกอบที่ประกอบด้วยสำเนาสองชุดของP : สำหรับแต่ละองค์ประกอบxของPนั้นQจะมีองค์ประกอบสองตัว คือ x และx โดยที่x < y ก็ต่อ เมื่อx < yและi < j เท่านั้น จากนั้นการตัดในPจะสอดคล้องกันแบบหนึ่งต่อหนึ่งกับแอนติเชนสูงสุดในQ : องค์ประกอบในเซตล่างของการตัดจะสอดคล้องกับองค์ประกอบที่มีตัวห้อย 0 ในแอนติเชน และองค์ประกอบในเซตบนของการตัดจะสอดคล้องกับองค์ประกอบที่มีตัวห้อย 1 ในแอนติเชน Jourdan et al. อธิบายอัลกอริทึมสำหรับการค้นหาแอนติเชนสูงสุด ซึ่งเมื่อนำไปใช้กับปัญหาการแสดงรายการตัดทั้งหมดในPจะใช้เวลาO ( c ( nw + w ³ ))ซึ่งเป็นการปรับปรุงอัลกอริทึมของGanter & Kuznetsov (1998)เมื่อความกว้างwมีขนาดเล็ก^{[ 21 ]}หรืออีกทางหนึ่ง แอนติเชนสูงสุดในQก็เหมือนกับเซตอิสระสูงสุดในกราฟเปรียบเทียบของQหรือคลิกสูงสุดในส่วนเติมเต็มของกราฟเปรียบเทียบ ดังนั้นอัลกอริทึมสำหรับปัญหาคลิกหรือปัญหาเซตอิสระจึงสามารถนำไปใช้กับปัญหาการเติมเต็ม Dedekind–MacNeille เวอร์ชันนี้ได้เช่นกัน^{[ 22 ]}

กราฟการลดรูปหรือกราฟปกคลุมแบบถ่ายทอดของความสมบูรณ์แบบของ Dedekind–MacNeille อธิบายความสัมพันธ์ลำดับระหว่างองค์ประกอบต่างๆ ได้อย่างกระชับ: เพื่อนบ้าน แต่ละแห่ง ของการตัดจะต้องลบองค์ประกอบของลำดับบางส่วนดั้งเดิมออกจากเซตบนหรือเซตล่างของการตัด ดังนั้นแต่ละจุดยอดจึงมีเพื่อนบ้านอย่างมากที่สุดn ตัว ดังนั้น กราฟปกคลุมจึงมี จุดยอด cจุด และมีเพื่อนบ้านอย่างมากที่สุดcn /2 ^ตัวซึ่งอาจน้อยกว่า ค่า c²ในเมทริกซ์ที่ระบุการเปรียบเทียบแบบคู่ระหว่างองค์ประกอบทั้งหมดNourine & Raynaud (1999)แสดงวิธีการคำนวณกราฟปกคลุมนี้อย่างมีประสิทธิภาพ โดยทั่วไปแล้ว หากBเป็นตระกูลของเซตใดๆ พวกเขาแสดงวิธีการคำนวณกราฟปกคลุมของแลตทิซของการรวมกันของเซตย่อยของBในกรณีของแลตทิซ Dedekind–MacNeille นั้นBอาจถือได้ว่าเป็นตระกูลของเซตส่วนเติมเต็มของอุดมคติหลัก และการรวมกันของเซตย่อยของBเป็นส่วนเติมเต็มของเซตล่างของการตัด แนวคิดหลักของอัลกอริทึมของพวกเขาคือการสร้างยูเนียนของเซตย่อยของBทีละน้อย (สำหรับแต่ละเซตในBจะสร้างยูเนียนกับยูเนียนที่สร้างไว้ก่อนหน้านี้ทั้งหมด) แสดงตระกูลของเซตที่ได้ในไทรและใช้การแสดงไทรเพื่อทดสอบคู่เซตที่เป็นไปได้บางคู่สำหรับความสัมพันธ์แบบประชิดกันในความสัมพันธ์แบบครอบคลุม ซึ่งใช้เวลาO ( cn ² )ในงานต่อมา ผู้เขียนกลุ่มเดียวกันได้แสดงให้เห็นว่าอัลกอริทึมสามารถทำให้เป็นแบบเพิ่มขึ้นได้อย่างสมบูรณ์ (สามารถเพิ่มองค์ประกอบลงในลำดับบางส่วนทีละหนึ่งรายการ) ด้วยขอบเขตเวลารวมเดียวกัน^{[ 23 ]}

• การคำนวณแบบ MacNeilleในPlanetMath
• การสำเร็จการศึกษาของ MacNeilleที่n Lab