Łańcuch (teoria mnogości)

Łańcuchy – w teorii częściowych porządków i w teorii mnogości podzbiory porządku, na których relacja porządkująca jest spójna.

Definicja

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

{\big (}\forall x,y\in A{\big )}{\big (}x\sqsubseteq y\vee y\sqsubseteq x{\big )}.

Innymi słowy zbiór $A$ jest łańcuchem wtedy i tylko wtedy, gdy relacja $\sqsubseteq$ porządkuje go liniowo, czyli jest ona relacją spójną w $A.$

Intuicyjnie, zbiór jest łańcuchem, gdy da się porównać każde dwa jego elementy.

Przykłady i własności

Zauważmy, że każdy zbiór jednoelementowy jest łańcuchem (i jednocześnie jest też antyłańcuchem).
Rozważmy płaszczyznę $\mathbb {R} ^{2}$ z porządkiem częściowym zdefiniowanym przez

\langle x_{1},y_{1}\rangle \leqslant _{0}\langle x_{2},y_{2}\rangle

wtedy i tylko wtedy, gdy

x_{1}\leqslant x_{2}

i

y_{1}\leqslant y_{2}.

(Powyżej,

\leqslant

jest standardową nierównością na prostej rzeczywistej

\mathbb {R} .

) Wówczas każda prosta pionowa i każda prosta o nieujemnym współczynniku kierunkowym jest łańcuchem w

(\mathbb {R} ^{2},\leqslant _{0}).

Także wykres dowolnej funkcji rosnącej jest łańcuchem w tym porządku.

Rozważmy zbiór ${}^{\omega >}2$ wszystkich skończonych ciągów zero-jedynkowych uporządkowany (częściowo) przez relację $\trianglelefteq$ wydłużania ciągów. Dla ciągu nieskończonego $\eta :\omega \longrightarrow 2$ połóżmy $A_{\eta }=\{\eta \upharpoonright n:n\in \omega \}.$ Wówczas $A_{\eta }$ jest łańcuchem w $(^{\omega >}2,\trianglelefteq ).$ Ponadto każdy łańcuch w tym porządku częściowym jest zawarty w zbiorze $A_{\eta }$ dla pewnego $\eta :\omega \longrightarrow 2.$
Twierdzenie Dilwortha mówi, że częściowy porządek $(P,\sqsubseteq )$ jest sumą $n$ łańcuchów $(n\in \mathbb {N} )$ wtedy i tylko wtedy, gdy $P$ nie zawiera $n+1$ elementowych antyłańcuchów (w sensie teorii posetów).

Warunki łańcucha

W teorii porządków częściowych rozważa się czasami dwie własności porządków bezpośrednio związane z łańcuchami. Niech $(P,\sqsubseteq )$ będzie zbiorem częściowo uporządkowanym.

Powiemy, że $P$ spełnia warunek rosnących łańcuchów lub ACC (od ang. ascending chain condition), jeśli każdy rosnący łańcuch $a_{0}\sqsubseteq a_{1}\sqsubseteq a_{2}\sqsubseteq \ldots$ jest od pewnego miejsca stały.
Podobnie mówimy, że $P$ spełnia warunek malejących łańcuchów lub DCC (od ang. descending chain condition), jeśli każdy malejący łańcuch $a_{0}\sqsupseteq a_{1}\sqsupseteq a_{2}\sqsupseteq \ldots$ jest od pewnego miejsca stały.

W teorii forsingu rozważa się własność określaną czasami jako warunek przeliczalnego łańcucha. Własność ta bezpośredniego związku z łańcuchami nie ma i lepszą nazwą dla niej jest warunek przeliczalnych antyłańcuchów (jako że ta własność postuluje że każdy antyłańcuch w rozważanym pojęciu forcingu jest przeliczalny). Użycie słowa łańcuch było prawdopodobnie spowodowane pewnym zamieszaniem w stosowanym nazewnictwie w początkowych latach rozwoju teorii. Innym możliwym wytłumaczeniem jest fakt, że jeśli $\mathbb {B}$ jest zupełną algebrą Boole’a, to każdy antyłańcuch w $\mathbb {B} ^{+}$ jest przeliczalny wtedy i tylko wtedy, gdy w algebrze $\mathbb {B}$ nie istnieje nieprzeliczalny ściśle malejący ciąg $a_{0}>a_{1}>\ldots >a_{\alpha }>\ldots$ $(\alpha <\omega _{1}).$

Funkcje kardynalne

W porządkach skończonych wprowadza się długość porządku (czasami zwaną też wysokością porządku) jako ilość elementów w najdłuższym łańcuchu w tym porządku. Dwie funkcje kardynalne na algebrach Boole’a, głębokość ${\rm {depth}}$ i długość ${\rm {length}}$ są bezpośrednio związane ze strukturą łańcuchów w rozważanej algebrze. Niech $\mathbb {B}$ będzie algebrą Boole’a. Określamy