สามารถระบุลักษณะของแอนติเชนสูงสุดในรูปแบบของการกระจายได้หรือไม่?

Jan 26 2021

สิ่งนี้ได้รับแรงบันดาลใจจากคำถามล่าสุดVerification of an maximal antichain

ความเป็นคู่ที่โด่งดังระหว่างตำแหน่ง จำกัด และการกระจายแบบ จำกัด มีสูตรที่ดีหลายประการ หนึ่งในนั้นกำหนดให้กับตำแหน่ง$P$ ตาข่าย $\mathscr D\!P$ของdowndeals (ฉันชอบคำนี้ที่ประดิษฐ์ขึ้นฉันคิดว่าโดย Freyd) downdeal ของ$P$ ชุดย่อย $D\subseteq P$ น่าพอใจ $p\leqslant q\in D$ $\Rightarrow$ $p\in D$. นี่คือโครงตาข่ายกระจาย (ล้อมรอบ) ที่เกี่ยวกับการรวมกันและการตัดกัน ตรงกันข้ามกับตาข่ายกระจายแบบ จำกัด$L$ หนึ่งกำหนดตำแหน่ง $\Pi\!L$ของช่วงเวลา องค์ประกอบ$p\in L$ เป็นนายกถ้า $x\land y=p$ หมายถึง $x=p$ หรือ $y=p$และราคาจะเรียงลำดับตามความสามารถในการหาร: $p\leqslant q$ iff $p$ หาร $q$, แสดง $p|q$ กล่าวคือ $\exists x\ q=p\land x$หรือเทียบเท่าเพียง $p\land q=q$. ดูเหมือนว่าจะมีความซับซ้อนมากเกินไปที่จะย้อนกลับลำดับที่ได้รับมา$L$แต่เป็นเพียงเรื่องของความสะดวก: คุณสามารถเปลี่ยนไปใช้คำจำกัดความเทียบเท่าทุกประเภทได้เสมอเช่นการย้อนกลับลำดับใน $P$ หรือใน $L$การแทนที่ไพรม์ด้วยการรวมไพรม์หรือการส่งผ่านไปยังการเติมเต็มของ downdeals ซึ่ง ได้แก่ การอัปเดตหรือทั้งสองอย่างเป็นต้น

ความเป็นคู่พูดได้สองอย่าง ประการแรกว่าทุกๆ$L$ สามารถระบุได้ด้วยตาข่ายของ downdeals ของช่วงเวลานั่นคือองค์ประกอบ $x\in L$ ถูกกำหนดโดยเฉพาะโดยตัวหารที่สำคัญ $D_x:=\{p\in\Pi\!L\mid\exists y\ x=p\land y\}$; กล่าวอีกนัยหนึ่งคือทุกๆ$x$คือการพบกันของตัวหารที่สำคัญ ยิ่งไปกว่านั้นทุก downdeal$D$ ของ $\Pi\!L$ คือ $D_x$ เพื่อความเป็นเอกลักษณ์ $x\in L$กล่าวคือสำหรับ $x=\bigwedge D$.

ประการที่สองความเป็นคู่บอกว่าทุกตำแหน่ง $P$ สามารถระบุได้ด้วยตำแหน่งของช่วงเวลาของ $\mathscr D\!P$. ได้แก่$p\in P$ จะถูกระบุด้วย $\not\uparrow\!\!p:=\{q\in P\mid p\not\leqslant q\}$ และแต่ละไพรม์ของ $\mathscr D\!P$ คือ $\not\uparrow p$ เพื่อความเป็นเอกลักษณ์ $p\in P$. ยิ่งไปกว่านั้น$p\leqslant q$ iff $\not\uparrow\!\!p\subseteq\not\uparrow\!\!q$.

ตอนนี้สำหรับตำแหน่งที่ จำกัด $P$downdeals ของมันอยู่ในการติดต่อแบบตัวต่อตัวกับแอนติเชน: ไปยัง downdeal $D$ หนึ่งกำหนดแอนติเชน $\max\!D$ ขององค์ประกอบสูงสุดและแอนติเชน $\alpha\subseteq P$ downdeal $\downarrow\!\alpha$ ขององค์ประกอบด้านล่าง $\alpha$, $\{p\mid\exists\ q\in\alpha\ p\leqslant q\}$.

คำถามของฉันคือเราสามารถอธิบายลักษณะนามธรรมเชิงพีชคณิตโดยไม่ต้องสนใจความเป็นคู่นี้องค์ประกอบเหล่านั้นของโครงตาข่ายการกระจายแบบ จำกัด $L$ซึ่งสอดคล้องกับantichains สูงสุดของ dual poset?

อย่างชัดเจนมากขึ้น (ฉันหวังว่าฉันจะไม่ผิดพลาดเมื่อแปล): มีการระบุลักษณะทางพีชคณิตอย่างหมดจดโดยไม่กล่าวถึงช่วงเวลาเหล่านั้นหรือไม่ $a\in L$ ด้วยคุณสมบัติที่ว่าสำหรับไพรม์ใด ๆ $p\notin D_a$ มีนายก $p'\in\max D_a$ ด้วย $p'|p$เหรอ?

สำหรับคำถามที่สร้างแรงบันดาลใจนั้นจริงๆแล้วเราจำเป็นต้องพิจารณาการกระจายแบบ จำกัดฟรีซึ่งหมายถึงการพิจารณาเฉพาะตำแหน่ง$P$ซึ่งเป็นชุดพาวเวอร์แบบเต็มของชุด จำกัด บางชุดเรียงลำดับโดยการรวม ดูเหมือนจะไม่ค่อยมีใครรู้เกี่ยวกับจำนวนหัวใจของชุดของแอนติเชนสูงสุดทั้งหมดในชุดพาวเวอร์เซ็ต ตามOEISลำดับของสิ่งเหล่านี้เริ่มต้นเช่น$1,2,3,7,29,376,31764,...$

คำถามแผนที่ในคลาสของโพเซ็ต จำกัด ทั้งหมดที่มาจากแอนติเชนที่มีขนาดสูงสุดดูเหมือนจะมีความสัมพันธ์กันอย่างใกล้ชิด แต่สิ่งที่เกี่ยวข้องกับแอนติเชนที่มีขนาดใหญ่ที่สุดเท่าที่จะเป็นไปได้ในขณะที่ของฉันเกี่ยวกับแอนติเชนสูงสุดทั้งหมดนั่นคือแอนติเชนที่ไม่มีอยู่ในแอนติเชนอื่น ๆ เห็นได้ชัดว่าแอนติเชนดังกล่าวอาจมีหลายขนาดโดยทั่วไปโดยเฉพาะอย่างยิ่งในชุดพาวเวอร์เซ็ต ตัวอย่างเช่นแอนติเชนทั้งสององค์ประกอบ$\{\{1\},\{2\}\}$ และแอนติเชนองค์ประกอบเดียว $\{\{1,2\}\}$ เป็นแอนตี้เชนสูงสุดในชุดพลังของ $\{1,2\}$.

คำตอบ

მამუკაჯიბლაძე Jan 28 2021 at 02:06

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

Richard Stanley อธิบายในความคิดเห็นว่า antichains สูงสุด $A$ ของ $P$ อยู่ในการติดต่อแบบหนึ่งต่อหนึ่งโดยมีช่วงเวลาบูลีนสูงสุดของ $\mathscr D\!P$.

โดยทั่วไปให้ $D'\subseteq D$ ด้วย $D,D'\in\mathscr D\!P$มันเป็นเรื่องง่ายที่จะเห็นว่าช่วงเวลา $[D',D]$ คือแลตทิซไอโซมอร์ฟิกถึง $\mathscr D(D\setminus D')$, ที่ไหน $D\setminus D'$ เป็นรายการย่อยของ $P$ด้วยคำสั่งบางส่วนที่เกิดขึ้น ดังนั้น$[D',D]$ เป็นบูลีนถ้าและต่อเมื่อ $D\setminus D'$ เป็นแอนติเชน

ตรงกันข้ามแอนติเชนใด ๆ $A\subseteq P$ ก่อให้เกิดช่วงเวลาบูลีนดังกล่าวด้วย $D=\downarrow\!A$ และ $D'=D\setminus A$. และ (ชัดเจน?) แอนติเชนสูงสุดสอดคล้องกับช่วงเวลาบูลีนสูงสุด

ตอนนี้มีการก่อสร้างซึ่งฉันได้เห็นครั้งแรกโดย Harold Simmons สำหรับองค์ประกอบ$a$ ในพีชคณิต Heyting ที่สมบูรณ์ให้ $$ \tau a=\bigwedge\{b\geqslant a\mid b\to a=a\}. $$ แล้ว $[a,\tau a]$ เป็นช่วงเวลาบูลีนที่ใหญ่ที่สุดโดยมีด้านล่าง $a$.

เห็นได้ชัดว่าในพีชคณิต Co-Heyting ที่สมบูรณ์มีตัวดำเนินการที่กำหนดด้วย dually $\delta$ ดังนั้น $[\delta b,b]$ เป็นช่วงเวลาบูลีนที่ใหญ่ที่สุดที่มีด้านบน $b$.

ตัวอย่าง. ในโครงตาข่ายของพื้นที่โทโพโลยีปิด$\delta$คืออนุพันธ์ของ Cantor-Bendixson นั่นคือสำหรับชุดปิด$C$, $\delta C$ คือชุดของจุด จำกัด

ดังนั้นถ้าเราอยู่ในพีชคณิตไบ - เฮ้งที่สมบูรณ์ตัวดำเนินการทั้งสองจะพร้อมใช้งานและช่วงเวลา $[a,b]$ เป็นบูลีนสูงสุดถ้าและต่อเมื่อ $a=\delta b$ และ $b=\tau a$.

จากนั้นก็มีนัยว่าทั้งสององค์ประกอบ $a$ น่าพอใจ $\delta\tau a=a$ และองค์ประกอบ $b$ น่าพอใจ $\tau\delta b=b$ควรสอดคล้องกับ antichains สูงสุด โดยเฉพาะอย่างยิ่งในกรณีที่พีชคณิตของเราคือ$\mathscr D\!P$ สำหรับบางตำแหน่ง $P$แล้ว $\tau\delta D=D$ สำหรับ $D\in\mathscr D\!P$ น่าจะหมายความว่า $\max D$ เป็นแอนติเชนสูงสุดในขณะที่ $\delta\tau D=D$ น่าจะหมายความว่า $\min(P\setminus D)$ เป็นแอนติเชนสูงสุด