Ł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[edytuj | edytuj kod]

Przy określonym częściowym porządku ${\displaystyle (P,\sqsubseteq )}$ zbiór ${\displaystyle A\subseteq P}$ nazywamy łańcuchem wtedy i tylko wtedy, gdy

${\displaystyle {\big (}\forall x,y\in A{\big )}{\big (}x\sqsubseteq y\vee y\sqsubseteq x{\big )}.}$

Innymi słowy zbiór ${\displaystyle A}$ jest łańcuchem wtedy i tylko wtedy, gdy relacja ${\displaystyle \sqsubseteq }$ porządkuje go liniowo, czyli jest ona relacją spójną w ${\displaystyle A.}$

Intuicyjnie, zbiór jest łańcuchem, gdy da się porównać każde dwa jego elementy.

Przykłady i własności[edytuj | edytuj kod]

• Zauważmy, że każdy zbiór jednoelementowy jest łańcuchem (i jednocześnie jest też antyłańcuchem).
• Rozważmy płaszczyznę ${\displaystyle \mathbb {R} ^{2}}$ z porządkiem częściowym zdefiniowanym przez

${\displaystyle \langle x_{1},y_{1}\rangle \leqslant _{0}\langle x_{2},y_{2}\rangle }$ wtedy i tylko wtedy, gdy ${\displaystyle x_{1}\leqslant x_{2}}$ i ${\displaystyle y_{1}\leqslant y_{2}.}$

(Powyżej, ${\displaystyle \leqslant }$ jest standardową nierównością na prostej rzeczywistej ${\displaystyle \mathbb {R} .}$) Wówczas każda prosta pionowa i każda prosta o nieujemnym współczynniku kierunkowym jest łańcuchem w ${\displaystyle (\mathbb {R} ^{2},\leqslant _{0}).}$ Także wykres dowolnej funkcji rosnącej jest łańcuchem w tym porządku.

• Rozważmy zbiór ${\displaystyle {}^{\omega >}2}$ wszystkich skończonych ciągów zero-jedynkowych uporządkowany (częściowo) przez relację ${\displaystyle \trianglelefteq }$ wydłużania ciągów. Dla ciągu nieskończonego ${\displaystyle \eta :\omega \longrightarrow 2}$ połóżmy ${\displaystyle A_{\eta }=\{\eta \upharpoonright n:n\in \omega \}.}$ Wówczas ${\displaystyle A_{\eta }}$ jest łańcuchem w ${\displaystyle (^{\omega >}2,\trianglelefteq ).}$ Ponadto każdy łańcuch w tym porządku częściowym jest zawarty w zbiorze ${\displaystyle A_{\eta }}$ dla pewnego ${\displaystyle \eta :\omega \longrightarrow 2.}$
• Twierdzenie Dilwortha mówi, że częściowy porządek ${\displaystyle (P,\sqsubseteq )}$ jest sumą ${\displaystyle n}$ łańcuchów ${\displaystyle (n\in \mathbb {N} )}$ wtedy i tylko wtedy, gdy ${\displaystyle P}$ nie zawiera ${\displaystyle n+1}$ elementowych antyłańcuchów (w sensie teorii posetów).

Warunki łańcucha[edytuj | edytuj kod]

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 ${\displaystyle (P,\sqsubseteq )}$ będzie zbiorem częściowo uporządkowanym.

• Powiemy, że ${\displaystyle P}$ spełnia warunek rosnących łańcuchów lub ACC (od ang. ascending chain condition), jeśli każdy rosnący łańcuch ${\displaystyle a_{0}\sqsubseteq a_{1}\sqsubseteq a_{2}\sqsubseteq \ldots }$ jest od pewnego miejsca stały.
• Podobnie mówimy, że ${\displaystyle P}$ spełnia warunek malejących łańcuchów lub DCC (od ang. descending chain condition), jeśli każdy malejący łańcuch ${\displaystyle 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 ${\displaystyle \mathbb {B} }$ jest zupełną algebrą Boole’a, to każdy antyłańcuch w ${\displaystyle \mathbb {B} ^{+}}$ jest przeliczalny wtedy i tylko wtedy, gdy w algebrze ${\displaystyle \mathbb {B} }$ nie istnieje nieprzeliczalny ściśle malejący ciąg ${\displaystyle a_{0}>a_{1}>\ldots >a_{\alpha }>\ldots }$ ${\displaystyle (\alpha <\omega _{1}).}$

Funkcje kardynalne[edytuj | edytuj kod]

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ść ${\displaystyle {\rm {depth}}}$ i długość ${\displaystyle {\rm {length}}}$ są bezpośrednio związane ze strukturą łańcuchów w rozważanej algebrze. Niech ${\displaystyle \mathbb {B} }$ będzie algebrą Boole’a. Określamy

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

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

Zobacz też[edytuj | edytuj kod]

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