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

ลำดับบางส่วน (Partial Order)คือ ความสัมพันธ์ แบบสะท้อนกลับถ่ายทอดและสมมาตรผกผันเมื่อกำหนดลำดับบางส่วนใดๆและบนเซตจะเป็นการขยายเชิงเส้นของก็ต่อเมื่อ ${\displaystyle \,\leq \,}$${\displaystyle \,\leq ^{*}\,}$${\displaystyle X,}$${\displaystyle \,\leq ^{*}\,}$${\displaystyle \,\leq \,}$

1. ${\displaystyle \,\leq ^{*}\,}$เป็นคำสั่งซื้อทั้งหมดและ
2. สำหรับทุกเงื่อนไขif แล้ว${\displaystyle x,y\in X,}$${\displaystyle x\leq y,}$${\displaystyle x\leq ^{*}y.}$

คุณสมบัติข้อที่สองนี้เองที่ทำให้นักคณิตศาสตร์อธิบายว่าเป็นการขยาย${\displaystyle \,\leq ^{*}\,}$${\displaystyle \,\leq .}$

อีกทางเลือกหนึ่ง การขยายเชิงเส้นอาจถูกมองว่าเป็นการจับคู่แบบหนึ่งต่อหนึ่งที่รักษา ลำดับ จากเซตที่มีลำดับบางส่วนไปยังโซ่บนเซตพื้นฐานเดียวกัน ${\displaystyle P}$${\displaystyle C}$

ลำดับก่อนหน้า (preorder)เป็นความสัมพันธ์แบบสะท้อนและถ่ายทอดได้ ความแตกต่างระหว่างลำดับก่อนหน้าและลำดับบางส่วน (partial order) คือ ลำดับก่อนหน้าอนุญาตให้สิ่งของสองอย่างที่แตกต่างกันถือว่า "เทียบเท่ากัน" ได้ กล่าวคือ ทั้งสองเงื่อนไขเป็นจริง ในขณะที่ลำดับบางส่วนอนุญาตเฉพาะเมื่อเงื่อนไขเป็นจริงเท่านั้นความสัมพันธ์เรียกว่าส่วนขยายเชิงเส้นของลำดับก่อนหน้า ถ้า: ${\displaystyle x\precsim y}$${\displaystyle y\precsim x}$${\displaystyle x=y}$${\displaystyle \precsim ^{*}}$${\displaystyle \precsim }$

1. ${\displaystyle \precsim ^{*}}$เป็นการสั่งซื้อล่วงหน้าทั้งหมดและ
2. สำหรับทุกเงื่อนไขif then และ${\displaystyle x,y\in X,}$${\displaystyle x\precsim y}$${\displaystyle x\precsim ^{*}y}$
3. สำหรับทุกเงื่อนไขif then . ในที่นี้หมายถึง " และไม่ใช่"${\displaystyle x,y\in X,}$${\displaystyle x\prec y}$${\displaystyle x\prec ^{*}y}$${\displaystyle x\prec y}$${\displaystyle x\precsim y}$${\displaystyle y\precsim x}$

ความแตกต่างระหว่างคำจำกัดความเหล่านี้อยู่ที่เงื่อนไขที่ 3 เท่านั้น เมื่อส่วนขยายเป็นลำดับบางส่วน เงื่อนไขที่ 3 ไม่จำเป็นต้องระบุอย่างชัดเจน เนื่องจากเป็นผลมาจากเงื่อนไขที่ 2 พิสูจน์ : สมมติว่าและไม่ใช่โดยเงื่อนไขที่ 2 โดยคุณสมบัติการสะท้อนกลับ "ไม่ใช่" หมายความว่าเนื่องจากเป็นลำดับบางส่วนและหมายความว่า "ไม่ใช่" ดังนั้น ${\displaystyle x\precsim y}$${\displaystyle y\precsim x}$${\displaystyle x\precsim ^{*}y}$${\displaystyle y\precsim x}$${\displaystyle y\neq x}$${\displaystyle \precsim ^{*}}$${\displaystyle x\precsim ^{*}y}$${\displaystyle y\neq x}$${\displaystyle y\precsim ^{*}x}$${\displaystyle x\prec ^{*}y}$

อย่างไรก็ตาม สำหรับลำดับเบื้องต้นทั่วไป จำเป็นต้องมีเงื่อนไขที่ 3 เพื่อตัดความเป็นไปได้ของการขยายที่ไม่สำคัญออกไป หากไม่มีเงื่อนไขนี้ ลำดับเบื้องต้นที่องค์ประกอบทั้งหมดเท่ากัน ( และใช้ได้กับทุกคู่x , y ) จะเป็นการขยายของลำดับเบื้องต้นทุกอัน ${\displaystyle y\precsim x}$${\displaystyle x\precsim y}$

ข้อความที่ระบุว่าลำดับบางส่วนทุกอันสามารถขยายไปสู่ลำดับทั้งหมดได้นั้น เรียกว่าหลักการขยายลำดับ การพิสูจน์โดยใช้สัจพจน์ของการเลือกได้รับการตีพิมพ์ครั้งแรกโดยEdward Marczewski (Szpilrajin)ในปี 1930 Marczewski เขียนว่าทฤษฎีบทนี้ได้รับการพิสูจน์มาก่อนแล้วโดยStefan Banach , Kazimierz KuratowskiและAlfred Tarskiโดยใช้สัจพจน์ของการเลือกเช่นกัน แต่การพิสูจน์เหล่านั้นไม่ได้รับการตีพิมพ์^{[ 1 ]}

มีข้อความที่คล้ายกันสำหรับการสั่งซื้อล่วงหน้า: การสั่งซื้อล่วงหน้าทุกรายการสามารถขยายไปสู่การสั่งซื้อล่วงหน้าทั้งหมดได้ ข้อความนี้ได้รับการพิสูจน์โดย Hansson ^{[ 2 ] : Lemma 3}

ในทฤษฎีเซตเชิงสัจพจน์ สมัยใหม่ หลักการขยายลำดับถือเป็นสัจพจน์ที่มีสถานะทางออนโทโลยีเทียบเท่ากับสัจพจน์ของการเลือก หลักการขยายลำดับนั้นอนุมานได้จากทฤษฎีบทอุดมคติเฉพาะของบูลีน^หรือทฤษฎีบทความกะทัดรัด ที่เทียบเท่ากัน [ ^{3 ]}แต่การอนุมานย้อนกลับไม่เป็นจริง^{[ 4 ]}

การใช้หลักการขยายลำดับกับลำดับบางส่วนซึ่งองค์ประกอบสองตัวใดๆ ก็ไม่สามารถเปรียบเทียบกันได้ แสดงให้เห็นว่า (ภายใต้หลักการนี้) ทุกเซตสามารถเรียงลำดับเชิงเส้นได้ การยืนยันที่ว่าทุกเซตสามารถเรียงลำดับเชิงเส้นได้นี้เรียกว่า หลักการจัดลำดับ ( Ordering Principle , OP) และเป็นการลดทอนทฤษฎีบทการจัดลำดับที่ดี (Well-Ordering Theorem) อย่างไรก็ตาม มีแบบจำลองของทฤษฎีเซตที่หลักการจัดลำดับใช้ได้ในขณะที่หลักการขยายลำดับใช้ไม่ได้^{[ 5 ]}

หลักการขยายลำดับสามารถพิสูจน์ได้เชิงสร้างสรรค์สำหรับเซตจำกัด โดยใช้อัลกอริทึม การเรียงลำดับเชิงโทโพโลยีโดยที่ลำดับบางส่วนแสดงด้วยกราฟแบบไม่มีวงจรทิศทางที่มีองค์ประกอบของเซตเป็นจุดยอดอัลกอริทึมหลายตัวสามารถค้นหาการขยายได้ในเวลาเชิงเส้น [ ^{6 ] แม้ว่า}การค้นหาการขยายเชิงเส้นเพียงครั้งเดียวจะทำได้ง่าย แต่ปัญหาของการนับการขยายเชิงเส้นทั้งหมดของลำดับบางส่วนจำกัดนั้นเป็นปัญหา#P-completeอย่างไรก็ตาม อาจประมาณได้ด้วยแผนการประมาณแบบสุ่มในเวลาพหุนามอย่างสมบูรณ์ [ ^{7 ] [ 8 ] ใน}บรรดาลำดับบางส่วนทั้งหมดที่มีจำนวนองค์ประกอบคงที่และจำนวนคู่ที่เปรียบเทียบได้คงที่ ลำดับบางส่วนที่มีจำนวนการขยายเชิงเส้นมากที่สุดคือเซมิออร์เดอร์^{[ 9 ]}

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

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

พื้นที่นี้ยังรวมถึงปัญหาเปิดที่มีชื่อเสียงที่สุดข้อหนึ่งของทฤษฎีลำดับ นั่นคือข้อสันนิษฐาน 1/3–2/3ซึ่งระบุว่าในเซตที่มีลำดับบางส่วนจำกัดใดๆที่ไม่มีลำดับสมบูรณ์จะมีคู่ขององค์ประกอบสำหรับซึ่งส่วนขยายเชิงเส้นของในจำนวนระหว่าง 1/3 และ 2/3 ของจำนวนส่วนขยายเชิงเส้นทั้งหมดของ^{[ 11 ] [ 12 ]}วิธีการเทียบเท่าในการกล่าวถึงข้อสันนิษฐานคือ หากเลือกส่วนขยายเชิงเส้นของแบบสุ่มอย่างสม่ำเสมอ จะมีคู่ที่มีความน่าจะเป็นระหว่าง 1/3 และ 2/3 ที่จะมีลำดับเป็นอย่างไรก็ตาม สำหรับเซตที่มีลำดับบางส่วนอนันต์บางเซต โดยมีความน่าจะเป็นแบบแคนอนิกที่กำหนดไว้บนส่วนขยายเชิงเส้นเป็นลิมิตของความน่าจะเป็นสำหรับลำดับบางส่วนจำกัดที่ครอบคลุมลำดับบางส่วนอนันต์ ข้อสันนิษฐาน 1/3–2/3 จะไม่เป็นจริง^{[ 13 ]}${\displaystyle P}$${\displaystyle (x,y)}$${\displaystyle P}$${\displaystyle P}$${\displaystyle x<y}$${\displaystyle P.}$${\displaystyle P}$${\displaystyle (x,y)}$${\displaystyle x<y.}$

การนับจำนวนส่วนขยายเชิงเส้นของโพเซตจำกัดเป็นปัญหาทั่วไปในพีชคณิตเชิง การจัดเรียง จำนวนนี้กำหนดโดยสัมประสิทธิ์นำหน้าของพหุนามอันดับคูณด้วย${\displaystyle |P|!.}$

ไดอะแกรม Youngสามารถถือได้ว่าเป็นไอเดียลลำดับ จำกัด ในโพเซตอนันต์ ในทำนอง เดียวกันตาราง Young มาตรฐานสามารถถือได้ว่าเป็นส่วนขยายเชิงเส้นของโพเซตที่สอดคล้องกับไดอะแกรม Young สำหรับไดอะแกรม Young (ทั่วไป) ส่วนขยายเชิงเส้นจะนับโดยใช้สูตรความยาวตะขอสำหรับไดอะแกรม Young แบบเฉียง ส่วนขยายเชิงเส้นจะนับโดยใช้สูตรดีเทอร์มิแนนต์^{[ 14 ]}${\displaystyle \mathbb {N} \times \mathbb {N} }$