분배 격자의 관점에서 최대 안티 체인을 특성화 할 수 있습니까?
이것은 최대 안티 체인 검증의 최근 질문에서 영감을 얻었습니다.
유한 포셋과 유한 분배 격자 사이의 유명한 이중성은 몇 가지 멋진 공식을 가지고 있습니다. 그들 중 하나는 포셋에 할당$P$ 격자 $\mathscr D\!P$그것의 downdeals (나는이 단어는 내가 Freyd에 의해, 생각, 발명 등). 다운 딜$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의 보완에 전달 updeals 또는 둘 등 등
이중성은 두 가지를 말합니다. 첫째, 모든$L$ 소수, 즉 요소의 하락 격자로 식별 할 수 있습니다. $x\in L$ 소수에 의해 고유하게 결정됩니다. $D_x:=\{p\in\Pi\!L\mid\exists y\ x=p\land y\}$; 즉, 모든$x$소수의 만남입니다. 또한 모든 다운 딜$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$, 다운 딜은 안티 체인과 일대일로 대응합니다. $D$ 하나는 안티 체인을 할당합니다 $\max\!D$ 최대 요소와 안티 체인 $\alpha\subseteq P$ 다운 딜 $\downarrow\!\alpha$ 아래 요소 수 $\alpha$, $\{p\mid\exists\ q\in\alpha\ p\leqslant q\}$.
내 질문은 :이 이중성에 호소하지 않고 유한 분배 격자의 요소를 추상적으로, 대수적으로 특성화 할 수 있습니까? $L$이중 포셋의 최대 안티 체인에 해당하는 것은 무엇입니까?
좀 더 명확하게 (나는 그것을 번역 할 때 실수하지 않았 으면 좋겠다) : 소수를 언급하지 않고 순전히 대수적 특성화가 있는가? $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\}$.
답변
이것은 답변 자체가 아니라 가능한 답변에 대한 (커뮤니티 위키) 설명입니다. 모두가 이것을 실제 답변으로 바꾸도록 초대 받았습니다. 또는 (분명히) 그것을 버리고 진짜 답을 쓰십시오.
Richard Stanley는 최대 안티 체인이 $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 대수에는 이중으로 정의 된 연산자가 있습니다. $\delta$ 그런 $[\delta b,b]$ top이있는 가장 큰 부울 간격입니다. $b$.
예. 위상 공간의 닫힌 집합 격자에서$\delta$Cantor-Bendixson 파생 상품입니다. 즉, 닫힌 세트의 경우$C$, $\delta C$ 한계점의 집합입니다.
따라서 완전한 bi-Heyting 대수를 사용하는 경우 두 연산자를 모두 사용할 수 있으며 구간 $[a,b]$ 다음과 같은 경우에만 최대 부울입니다. $a=\delta b$ 과 $b=\tau a$.
이것은 겉보기에는 두 요소 모두 $a$ 만족스러운 $\delta\tau a=a$ 및 요소 $b$ 만족스러운 $\tau\delta b=b$어떻게 든 최대의 안티 체인과 일치해야합니다. 특히 우리 대수가$\mathscr D\!P$ 일부 포셋을 위해 $P$, 다음 $\tau\delta D=D$ ...에 대한 $D\in\mathscr D\!P$ 그것을 의미해야한다 $\max D$ 최대 안티 체인 인 반면 $\delta\tau D=D$ 그것을 의미해야한다 $\min(P\setminus D)$ 최대 안티 체인입니다.