Ł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ą łańcuchó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