Kann man maximale Antichains in Form von Verteilungsgittern charakterisieren?

Jan 26 2021

Dies ist inspiriert von der jüngsten Frage Überprüfung einer maximalen Antichain

Die berühmte Dualität zwischen endlichen Posets und endlichen Verteilungsgittern hat mehrere schöne Formulierungen. Einer von ihnen weist einen Poset zu$P$ das Gitter $\mathscr D\!P$von seinen Downdeals (ich mag dieses Wort, das, glaube ich, von Freyd erfunden wurde). Ein Downdeal von$P$ Eine Teilmenge $D\subseteq P$ befriedigend $p\leqslant q\in D$ $\Rightarrow$ $p\in D$. Dies ist ein (begrenztes) Verteilungsgitter in Bezug auf Vereinigungs- und Schnittoperationen. Umgekehrt zu einem endlichen Verteilungsgitter$L$ man weist den Poset zu $\Pi\!L$seiner Primzahlen . Ein Element$p\in L$ ist prim wenn $x\land y=p$ impliziert $x=p$ oder $y=p$und Primzahlen sind nach Teilbarkeit geordnet: $p\leqslant q$ iff $p$ teilt $q$bezeichnet $p|q$ dh $\exists x\ q=p\land x$oder gleichwertig nur $p\land q=q$. Dies scheint insofern eine Überkomplikation zu sein, als es die von geerbte Reihenfolge umkehrt$L$Dies ist jedoch nur eine Frage der Bequemlichkeit: Sie können jederzeit zu allen möglichen äquivalenten Definitionen wechseln, z. B. zum Umkehren der Reihenfolge in $P$ oder in $L$, Ersetzen von Primzahlen durch Join-Primzahlen oder Weitergeben an Ergänzungen von Downdeals, bei denen es sich um Aktualisierungen handelt , oder beides usw. usw.

Die Dualität sagt zwei Dinge. Erstens, dass jeder$L$ kann mit dem Gitter der Downdeals seiner Primzahlen identifiziert werden, dh mit einem Element $x\in L$ wird eindeutig durch seine Hauptteiler bestimmt, $D_x:=\{p\in\Pi\!L\mid\exists y\ x=p\land y\}$;; mit anderen Worten, jeder$x$ist das Treffen seiner Hauptteiler. Darüber hinaus jeder Downdeal$D$ von $\Pi\!L$ ist $D_x$ für ein einzigartiges $x\in L$nämlich für $x=\bigwedge D$.

Zweitens sagt die Dualität, dass jeder Poset $P$ kann mit dem Poset von Primzahlen von identifiziert werden $\mathscr D\!P$. Nämlich,$p\in P$ wird identifiziert mit $\not\uparrow\!\!p:=\{q\in P\mid p\not\leqslant q\}$ und jede Primzahl von $\mathscr D\!P$ ist $\not\uparrow p$ für ein einzigartiges $p\in P$. Außerdem$p\leqslant q$ iff $\not\uparrow\!\!p\subseteq\not\uparrow\!\!q$.

Nun zu einem endlichen Poset $P$, seine Downdeals stehen in einer Eins-zu-Eins-Entsprechung mit seinen Antichains: zu einem Downdeal $D$ man weist die Antichain zu $\max\!D$ von seinen maximalen Elementen und zu einer Antichain $\alpha\subseteq P$ der Downdeal $\downarrow\!\alpha$ von Elementen unten $\alpha$, $\{p\mid\exists\ q\in\alpha\ p\leqslant q\}$.

Meine Frage ist: Kann man diese Elemente eines endlichen Verteilungsgitters abstrakt, algebraisch charakterisieren, ohne diese Dualität anzusprechen? $L$welche entsprechen den maximalen Antichains seines Doppelposets?

Genauer gesagt (ich hoffe, ich habe bei der Übersetzung keine Fehler gemacht): Gibt es eine rein algebraische Charakterisierung dieser Primzahlen, ohne Primzahlen zu erwähnen? $a\in L$ mit der Eigenschaft, dass für jede Primzahl $p\notin D_a$ Es gibt eine Primzahl $p'\in\max D_a$ mit $p'|p$?

Für diese inspirierende Frage müssen wir eigentlich nur freie endliche Verteilungsgitter berücksichtigen, was bedeutet, dass nur die Posets berücksichtigt werden$P$Dies sind vollständige Potenzsätze einer endlichen Menge, geordnet nach Einbeziehung. Über die Kardinalität der Menge aller maximalen Antichains in einem Powerset scheint nicht viel bekannt zu sein. Laut OEIS beginnt die Reihenfolge dieser wie$1,2,3,7,29,376,31764,...$

Die Frage Karte über die Klasse aller endlichen Posets, die von Antichains maximaler Größe stammen, scheint sehr eng verwandt zu sein, aber es handelt sich um Antichains mit größtmöglicher Größe, während es sich bei meiner um alle maximalen Antichains handelt, dh um Antichains, die in keiner anderen Antichain enthalten sind. Offensichtlich können solche Antichains im Allgemeinen verschiedene Größen haben, insbesondere in Powersets. Zum Beispiel beide Antichain-Elemente$\{\{1\},\{2\}\}$ und das eine Element Antichain $\{\{1,2\}\}$ sind maximale Antichains im Powerset von $\{1,2\}$.

Antworten

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

Dies ist eine (Community-Wiki) Beschreibung einer möglichen Antwort und nicht die Antwort selbst. Jeder ist eingeladen, dies in eine echte Antwort zu verwandeln. Oder (offensichtlich) aufgeben und die wirklich echte Antwort schreiben.

Richard Stanley erklärt in einem Kommentar, dass die maximalen Antichains $A$ von $P$ sind in Eins-zu-Eins-Entsprechung mit maximalen booleschen Intervallen von $\mathscr D\!P$.

Im Allgemeinen gegeben $D'\subseteq D$ mit $D,D'\in\mathscr D\!P$ist es leicht zu erkennen, dass das Intervall $[D',D]$ ist gitterisomorph zu $\mathscr D(D\setminus D')$, wo $D\setminus D'$ ist die Untermenge von $P$mit der induzierten Teilordnung. So$[D',D]$ ist genau dann boolesch, wenn $D\setminus D'$ ist ein Antichain.

Umgekehrt jede Antichain $A\subseteq P$ führt zu einem solchen booleschen Intervall mit $D=\downarrow\!A$ und $D'=D\setminus A$. Und (eindeutig?) Maximale Antichains entsprechen maximalen Booleschen Intervallen.

Jetzt gibt es eine Konstruktion, die ich zum ersten Mal von Harold Simmons gesehen habe. Für ein Element$a$ in jeder vollständigen Heyting-Algebra, lass $$ \tau a=\bigwedge\{b\geqslant a\mid b\to a=a\}. $$ Dann $[a,\tau a]$ ist das größte boolesche Intervall mit unten $a$.

In einer vollständigen Co-Heyting-Algebra gibt es eindeutig einen doppelt definierten Operator $\delta$ so dass $[\delta b,b]$ ist das größte boolesche Intervall mit top $b$.

Beispiel. Im Gitter geschlossener Mengen eines topologischen Raumes,$\delta$ist das Cantor-Bendixson-Derivat. Das heißt, für einen geschlossenen Satz$C$, $\delta C$ ist die Menge seiner Grenzpunkte.

Wenn wir uns also in einer vollständigen Bi-Heyting-Algebra befinden, sind beide Operatoren und ein Intervall verfügbar $[a,b]$ ist genau dann maximal boolesch, wenn $a=\delta b$ und $b=\tau a$.

Dies impliziert dann scheinbar, dass beide Elemente $a$ befriedigend $\delta\tau a=a$ und Elemente $b$ befriedigend $\tau\delta b=b$sollte irgendwie maximalen Antichains entsprechen. Insbesondere für den Fall, dass unsere Algebra ist$\mathscr D\!P$ für einige Poset $P$, dann $\tau\delta D=D$ zum $D\in\mathscr D\!P$ sollte das bedeuten $\max D$ ist eine maximale Antichain, während $\delta\tau D=D$ sollte das bedeuten $\min(P\setminus D)$ ist eine maximale Antichain.