Antyłańcuch

Antyłańcuch to termin w kilku dziedzinach matematyki na określenie obiektów o własnościach związanych z pewnymi praporządkami.

Antyłańcuchy w teorii porządków częściowych

Definicja

Przy określonym porządku $(P,\sqsubseteq )$ zbiór $A\subseteq P$ nazywamy antyłańcuchem wtedy i tylko wtedy, gdy

${\big (}\forall x,y\in A{\big )}{\big (}x\neq y\ \Rightarrow \ \neg (x\sqsubseteq y\vee y\sqsubseteq x){\big )}.$

Intuicyjnie, zbiór jest antyłańcuchem, gdy nie da się porównać żadnych dwóch różnych jego elementów.

Przykłady i własności

• Zauważmy, że każdy zbiór jednoelementowy jest antyłańcuchem (i jednocześnie jest też łańcuchem).
• Porządek częściowy $(P,\sqsubseteq )$ jest porządkiem liniowym wtedy i tylko wtedy, gdy każdy antyłańcuch w tym porządku jest jednoelementowy.
• Twierdzenie Dilwortha mówi, że częściowy porządek $(P,\sqsubseteq )$ nie zawiera $n+1$ elementowych antyłańcuchów $(n\in \mathbb {N} )$ wtedy i tylko wtedy, gdy $P$ jest sumą $n$ łańcuchów.
• Twierdzenie Spernera mówi, że jeśli $P$ jest rodziną wszystkich podzbiorów pewnego $n$ elementowego zbioru $X,$ a porządek $\sqsubseteq$ jest zawieraniem, to każdy antyłańcuch zawarty w $P$ ma co najwyżej $n \choose \lfloor {n/2}\rfloor$ elementów.

Antyłańcuchy w teorii forsingu

Definicja

Niech $(\mathbb {P} ,\leqslant )$ będzie pojęciem forsingu. Zbiór $A\subseteq \mathbb {P}$ jest antyłańcuchem w $\mathbb {P}$ wtedy i tylko wtedy, gdy każde dwa różne warunki $p,q\in A$ są sprzeczne, tzn.

${\big (}\forall p,q\in A{\big )}{\big (}p\neq q\ \Rightarrow \ \neg (\exists r\in {\mathbb {P} })(r\leqslant p\ \wedge r\leqslant q){\big )}.$

Pojęcie antyłańcucha w sensie forsingu jest różne od tegoż w sensie teorii posetów: nieporównywalność elementów jest tutaj zastąpiona sprzecznością warunków.

$\kappa$-cc

Niech $\kappa$ będzie liczbą kardynalną. Powiemy, że pojęcie forsingu $({\mathbb {P} },\leqslant )$ spełnia $\kappa$-cc, jeśli każdy antyłańcuch w $\mathbb {P}$ jest mocy mniejszej niż $\kappa .$ Jeśli $\mathbb {P}$ spełnia $\aleph _{1}$-cc, to mówimy wtedy też, że $\mathbb {P}$ spełnia warunek przeliczalnych antyłańcuchów albo $\mathbb {P}$ spełnia ccc.

Nazwa $\kappa$-cc jest skrótem angielskiego wyrażenia $\kappa$-chain condition (warunek $\kappa$-łańcucha). Użycie słowa łańcuch (chain) było pierwotnie spowodowane pewnym zamieszaniem w stosowanym nazewnictwie w początkowych latach rozwoju teorii.

Twierdzenie Erdősa-Tarskiego mówi, że najmniejsza liczba kardynalna $\kappa ,$ dla której pojęcie forsingu $\mathbb {P}$ spełnia warunek $\kappa$-cc, musi być regularna.

Przykłady i własności

• Pojęcie forsingu Cohena (zbiór skończonych ciągów liczb naturalnych uporządkowany przez odwrotną relację wydłużania ciągów) spełnia ccc.
• Pojęcie forsingu Solovaya (zbiór domkniętych podzbiorów $\mathbb {R}$ miary dodatniej uporządkowany przez inkluzję) spełnia ccc.
• Pojęcie forsingu Sacksa (zbiór doskonałych podzbiorów $\mathbb {R}$ uporządkowany przez inkluzję) nie spełnia ccc. Poniżej każdego warunku w tym forsingu można skonstruować antyłańcuch mocy continuum.
• Rozszerzenia generyczne modeli ZFC przy użyciu pojęć forsingu spełniających ccc zachowują liczby kardynalne. Rozszerzenia przy użyciu pojęć forsingu spełniających $\kappa$-cc zachowują liczby kardynalne większe lub równe $\kappa .$

Antyłańcuchy w algebrach Boole’a

Definicja

Ponieważ algebry Boole’a są też pojęciami forsingu, forsingowa definicja antyłańcuchów jest naturalnie przenoszona na algebry Boole’a. Niech $(\mathbb {B} ,\vee ,\wedge ,\neg ,0,1)$ będzie algebrą Boole’a. Zbiór $A\subseteq \mathbb {B} \setminus \{0\}$ jest antyłańcuchem w $\mathbb {B}$ wtedy i tylko wtedy, gdy każde dwa różne elementy $A$ są rozłączne, tzn.

${\big (}\forall a,b\in A{\big )}{\big (}a\neq b\ \Rightarrow \ a\wedge b=0{\big )}.$

Celularność

Celularność jest funkcją kardynalną określona na algebrach Boole’a. Celularność $c(\mathbb {B} )$ algebry Boole’a $\mathbb {B}$ jest to supremum mocy antyłańcuchów w $\mathbb {B} .$

Mówimy, że algebra Boole’a $\mathbb {B}$ spełnia ccc, jeśli $c(\mathbb {B} )\leqslant \aleph _{0}.$

Twierdzenie Erdősa-Tarskiego mówi, że jeśli celularność $c(\mathbb {B} )$ algebry Boole’a $\mathbb {B}$ jest liczbą singularną, to istnieje antyłańcuch $A\subseteq \mathbb {B} \setminus \{0\}$ mocy $c(\mathbb {B} ).$

Zobacz też

• łańcuch

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Antichain, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2024-03-07].