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 ${\displaystyle (P,\sqsubseteq )}$ zbiór ${\displaystyle A\subseteq P}$ nazywamy antyłańcuchem wtedy i tylko wtedy, gdy

${\displaystyle {\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 ${\displaystyle (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 ${\displaystyle (P,\sqsubseteq )}$ nie zawiera ${\displaystyle n+1}$ elementowych antyłańcuchów ${\displaystyle (n\in \mathbb {N} )}$ wtedy i tylko wtedy, gdy ${\displaystyle P}$ jest sumą ${\displaystyle n}$ łańcuchów.
• Twierdzenie Spernera mówi, że jeśli ${\displaystyle P}$ jest rodziną wszystkich podzbiorów pewnego ${\displaystyle n}$ elementowego zbioru ${\displaystyle X,}$ a porządek ${\displaystyle \sqsubseteq }$ jest zawieraniem, to każdy antyłańcuch zawarty w ${\displaystyle P}$ ma co najwyżej ${\displaystyle n \choose \lfloor {n/2}\rfloor }$ elementów.

Antyłańcuchy w teorii forsingu

Definicja

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

${\displaystyle {\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.

${\displaystyle \kappa }$-cc

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

Nazwa ${\displaystyle \kappa }$-cc jest skrótem angielskiego wyrażenia ${\displaystyle \kappa }$-chain condition (warunek ${\displaystyle \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 ${\displaystyle \kappa ,}$ dla której pojęcie forsingu ${\displaystyle \mathbb {P} }$ spełnia warunek ${\displaystyle \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 ${\displaystyle \mathbb {R} }$ miary dodatniej uporządkowany przez inkluzję) spełnia ccc.
• Pojęcie forsingu Sacksa (zbiór doskonałych podzbiorów ${\displaystyle \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 ${\displaystyle \kappa }$-cc zachowują liczby kardynalne większe lub równe ${\displaystyle \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 ${\displaystyle (\mathbb {B} ,\vee ,\wedge ,\neg ,0,1)}$ będzie algebrą Boole’a. Zbiór ${\displaystyle A\subseteq \mathbb {B} \setminus \{0\}}$ jest antyłańcuchem w ${\displaystyle \mathbb {B} }$ wtedy i tylko wtedy, gdy każde dwa różne elementy ${\displaystyle A}$ są rozłączne, tzn.

${\displaystyle {\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ść ${\displaystyle c(\mathbb {B} )}$ algebry Boole’a ${\displaystyle \mathbb {B} }$ jest to supremum mocy antyłańcuchów w ${\displaystyle \mathbb {B} .}$

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

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