Antyłańcuch

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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[edytuj | edytuj kod]

Definicja[edytuj | edytuj kod]

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[edytuj | edytuj kod]

  • 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[edytuj | edytuj kod]

Definicja[edytuj | edytuj kod]

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).

Należy zwrócić uwagę że 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

  • 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[edytuj | edytuj kod]

Definicja[edytuj | edytuj kod]

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ść[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]