Łańcuch (teoria mnogości)

Łańcuchy to 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ą łancuchów w rozważanej algebrze. Niech $\mathbb{B}$ będzie algebrą Boole'a. Określamy

${\rm length}(\mathbb{B})=\sup\big\{|A|:A\subseteq \mathbb{B}$ jest łańcuchem $\big\}$

${\rm depth}(\mathbb{B})=\sup\big\{ |A|:A\subseteq \mathbb{B}$ jest dobrze uporządkowanym łańcuchem $\big\}$.

Zobacz też

• częściowy porządek
• antyłańcuch