Łańcuch (teoria mnogości)

W teorii częściowych porządków i w teorii mnogości, łańcuchy to 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 \leq _{0}\langle x_{2},y_{2}\rangle$ wtedy i tylko wtedy gdy $x_{1}\leq x_{2}$ i $y_{1}\leq y_{2}$.

(Powyżej, $\leq$ 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},\leq _{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ż

• przegląd zagadnień z zakresu matematyki
• częściowy porządek
• antyłańcuch