Ł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,⊑)$ zbiór $A\subseteq P$ nazywamy łańcuchem wtedy i tylko wtedy, gdy

$(\mathrm{\forall }x,y\in A)(x⊑y\vee y⊑x).$

Innymi słowy zbiór $A$ jest łańcuchem wtedy i tylko wtedy, gdy relacja $⊑$ 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ę ${ℝ}^2$ z porządkiem częściowym zdefiniowanym przez

$⟨x_1,y_1⟩{⩽}_0⟨x_2,y_2⟩$ wtedy i tylko wtedy, gdy $x_1⩽x_2$ i $y_1⩽y_2.$

(Powyżej, $⩽$ jest standardową nierównością na prostej rzeczywistej $ℝ.$) Wówczas każda prosta pionowa i każda prosta o nieujemnym współczynniku kierunkowym jest łańcuchem w $({ℝ}^2,{⩽}_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ę $⊴$ wydłużania ciągów. Dla ciągu nieskończonego $\eta :\omega ⟶2$ połóżmy $A_{\eta }=\{\eta \upharpoonright n:n\in \omega \}.$ Wówczas $A_{\eta }$ jest łańcuchem w ${(}^{\omega >}2,⊴).$ Ponadto każdy łańcuch w tym porządku częściowym jest zawarty w zbiorze $A_{\eta }$ dla pewnego $\eta :\omega ⟶2.$
• Twierdzenie Dilwortha mówi, że częściowy porządek $(P,⊑)$ 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,⊑)$ 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⊑a_1⊑a_2⊑\dots$ 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⊒a_1⊒a_2⊒\dots$ 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 $𝔹$ jest zupełną algebrą Boole’a, to każdy antyłańcuch w ${𝔹}^{+}$ jest przeliczalny wtedy i tylko wtedy, gdy w algebrze $𝔹$ nie istnieje nieprzeliczalny ściśle malejący ciąg $a_0>a_1>\dots >a_{\alpha }>\dots$ $(\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ść $\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{t}\mathrm{h}$ i długość $\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}$ są bezpośrednio związane ze strukturą łańcuchów w rozważanej algebrze. Niech $𝔹$ będzie algebrą Boole’a. Określamy

$\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(𝔹)=\sup \{|A|:A\subseteq 𝔹$ jest łańcuchem $\}$

$\mathrm{d}\mathrm{e}\mathrm{p}\mathrm{t}\mathrm{h}(𝔹)=\sup \{|A|:A\subseteq 𝔹$ jest dobrze uporządkowanym łańcuchem $\}.$