Łańcuch (teoria mnogości)

Łańcuchy w teorii porządków

Łańcuchy to podzbiory porządku, na których relacja porządkująca jest spójna. W kontekście częściowego porządku $(P,\; \backslash sqsubseteq)$, zbiór $A\backslash subseteq\; P$ jest łańcuchem, gdy dla każdego $x,\; y\; \backslash in\; A$ zachodzi $x\; \backslash sqsubseteq\; y$ lub $y\; \backslash sqsubseteq\; x$. Oznacza to, że każdy element zbioru można porównać z innym.

Przykłady łańcuchów

• Każdy zbiór jednoelementowy jest łańcuchem.
• W płaszczyźnie $\backslash mathbb\{R\}^2$ z porządkiem częściowym zdefiniowanym przez nierówności, każda prosta pionowa oraz prosta o nieujemnym współczynniku kierunkowym stanowią łańcuch.
• Dla zbioru $\{\}^\{\backslash omega>\}2$ wszystkich skończonych ciągów zero-jedynkowych uporządkowanych przez relację wydłużania, każdy łańcuch jest zawarty w pewnym zbiorze $A\_\backslash eta$.

Warunki łańcucha

W teorii porządków wyróżnia się dwa istotne warunki:

• Warunek rosnących łańcuchów (ACC): Zbiór $P$ spełnia ten warunek, jeśli każdy rosnący łańcuch staje się stały od pewnego miejsca.
• Warunek malejących łańcuchów (DCC): Zbiór $P$ spełnia ten warunek, jeśli każdy malejący łańcuch staje się stały od pewnego miejsca.

W teorii forsingu występuje również warunek przeliczalnego łańcucha, który odnosi się do przeliczalności antyłańcuchów.

Funkcje kardynalne w porządkach skończonych

W porządkach skończonych definiuje się długość porządku, czyli liczbę elementów w najdłuższym łańcuchu. W algebrze Boole’a wyróżnia się dwie funkcje kardynalne:

• Długość (length): $\backslash mathrm\{length\}(\backslash mathbb\{B\})=\backslash sup\backslash big\backslash \{|A|:A\backslash subseteq\; \backslash mathbb\{B\}\; jest\; łańcuchem\backslash big\backslash \}$
• Głębokość (depth): $\backslash mathrm\{depth\}(\backslash mathbb\{B\})=\backslash sup\backslash big\backslash \{\; |A|:A\backslash subseteq\; \backslash mathbb\{B\}\; jest\; dobrze\; uporządkowanym\; łańcuchem\backslash big\backslash \}$