Tekst źródłowy strony Łańcuch (teoria mnogości)

'''Łańcuchy''' – w teorii [[Częściowy porządek|częściowych porządków]] i w [[teoria mnogości|teorii mnogości]] podzbiory porządku, na których relacja porządkująca jest [[relacja spójna|spójna]].

== Definicja ==
Przy określonym częściowym porządku <math>(P, \sqsubseteq)</math> [[zbiór]] <math>A\subseteq P</math> nazywamy '''łańcuchem''' wtedy i tylko wtedy, gdy
: <math>\big(\forall x,y \in A\big)\big(x \sqsubseteq y \vee y \sqsubseteq x\big).</math>

Innymi słowy zbiór <math>A</math> jest łańcuchem wtedy i tylko wtedy, gdy relacja <math>\sqsubseteq</math> porządkuje go [[Porządek liniowy|liniowo]], czyli jest ona relacją [[Relacja spójna|spójną]] w <math>A.</math>

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ńcuch]]em).
* Rozważmy płaszczyznę <math>\mathbb{R}^2</math> z porządkiem częściowym zdefiniowanym przez
: <math>\langle x_1,y_1\rangle \leqslant_0\langle x_2,y_2\rangle</math> wtedy i tylko wtedy, gdy <math>x_1\leqslant x_2</math> i <math>y_1\leqslant y_2.</math>
: (Powyżej, <math>\leqslant</math> jest standardową nierównością na [[liczby rzeczywiste|prostej rzeczywistej]] <math>\mathbb{R}.</math>) Wówczas każda [[prosta]] pionowa i każda prosta o [[Znak liczby|nieujemnym]] współczynniku kierunkowym jest łańcuchem w <math>(\mathbb{R}^2,\leqslant_0).</math> Także wykres dowolnej [[Funkcja monotoniczna|funkcji rosnącej]] jest łańcuchem w tym porządku.
* Rozważmy zbiór <math>{}^{\omega>}2</math> wszystkich skończonych ciągów zero-jedynkowych uporządkowany (częściowo) przez relację <math>\trianglelefteq</math> wydłużania ciągów. Dla ciągu nieskończonego <math>\eta:\omega\longrightarrow 2</math> połóżmy <math>A_\eta=\{\eta\upharpoonright n:n\in\omega\}.</math> Wówczas <math>A_\eta</math> jest łańcuchem w <math>(^{\omega>}2,\trianglelefteq).</math> Ponadto każdy łańcuch w tym porządku częściowym jest zawarty w zbiorze <math>A_\eta</math> dla pewnego <math>\eta:\omega\longrightarrow 2.</math>
* [[Twierdzenie Dilwortha]] mówi, że częściowy porządek <math>(P, \sqsubseteq)</math> jest [[Suma zbiorów|sumą]] <math>n</math> łańcuchów <math>(n\in \mathbb{N})</math> wtedy i tylko wtedy, gdy <math>P</math> nie zawiera <math>n+1</math> 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 <math>(P, \sqsubseteq)</math> będzie zbiorem częściowo uporządkowanym.
* Powiemy, że <math>P</math> spełnia '''warunek rosnących łańcuchów''' lub ACC (od [[język angielski|ang.]] ''ascending chain condition''), jeśli każdy rosnący łańcuch <math>a_0\sqsubseteq a_1\sqsubseteq a_2\sqsubseteq\ldots</math> jest od pewnego miejsca stały.
* Podobnie mówimy, że <math>P</math> spełnia '''warunek malejących łańcuchów''' lub DCC (od [[język angielski|ang.]] ''descending chain condition''), jeśli każdy malejący łańcuch <math>a_0\sqsupseteq a_1\sqsupseteq a_2\sqsupseteq\ldots</math> jest od pewnego miejsca stały.

W teorii [[forsing]]u 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 [[Zbiór przeliczalny|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 <math>\mathbb{B}</math> jest zupełną [[algebra Boole’a|algebrą Boole’a]], to każdy antyłańcuch w <math>\mathbb{B}^+</math> jest przeliczalny wtedy i tylko wtedy, gdy w algebrze <math>\mathbb{B}</math> nie istnieje [[Zbiór nieprzeliczalny|nieprzeliczalny]] ściśle malejący ciąg <math>a_0>a_1>\ldots>a_\alpha>\ldots</math> <math>(\alpha<\omega_1).</math>

== 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 [[funkcja kardynalna|funkcje kardynalne]] na algebrach Boole’a, '''głębokość''' <math>\rm depth</math> i '''długość''' <math>\rm length</math> są bezpośrednio związane ze strukturą łańcuchów w rozważanej algebrze. Niech <math>\mathbb{B}</math> będzie algebrą Boole’a. Określamy
: <math>\mathrm{length}(\mathbb{B})=\sup\big\{|A|:A\subseteq \mathbb{B}</math> jest łańcuchem <math>\big\}</math>
: <math>\mathrm{depth}(\mathbb{B})=\sup\big\{ |A|:A\subseteq \mathbb{B}</math> jest [[Dobry porządek|dobrze uporządkowanym]] łańcuchem <math>\big\}.</math>

{{Teoria porządku}}

[[Kategoria:Porządki]]