Łańcuch (teoria mnogości): Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
Zmiana kategorii stuba na {{Matematyka stub}} na podstawie kategorii |
gruntowne przeredagowanie i rozbudowa - może starczy na razie? (-stub) |
||
Linia 1:
W teorii [[Częściowy porządek|częściowych porządków]] i w [[teoria mnogości|teorii mnogości]], '''łańcuchy''' to podzbiory porządku na których relacja porządkująca jest totalna.
Przy określonym [[Częściowy porządek|porządku]] <math>(A, \sqsubseteq)</math> zbiór <math>B \subseteq A</math> nazywamy '''łańcuchem''' wtedy i tylko wtedy, gdy <math>\forall x,y \in B\ (x \sqsubseteq y \vee y \sqsubseteq x)</math>.▼
==Definicja==
Innymi słowy zbiór ''B'' 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 ''B''.▼
▲Przy określonym
<center>
<math>\big(\forall x,y \in A\big)\big(x \sqsubseteq y \vee y \sqsubseteq x\big)</math>.
</center>
▲Innymi słowy zbiór
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|antyłańcuchem]]).
*Rozważmy płaszczyznę <math>{\mathbb R}^2</math> z porządkiem częściowym zdefiniowanym przez
<center>
<math>\langle x_1,y_1\rangle \leq_0\langle x_2,y_2\rangle</math> wtedy i tylko wtedy gdy <math>x_1\leq x_2</math> i <math>y_1\leq y_2</math>.
</center>
:(Powyżej, <math>\leq </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,\leq_0)</math>. Także wykres dowolnej [[funkcja rosnąca|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==
'''Zobacz też:'''▼
*W teorii porządków częściowych rozważa się czasami dwie własności porządków bezpośrednio związane z łancuchami.
: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 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 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ą łancuchów w rozważanej algebrze. Niech <math>{\mathbb B}</math> będzie algebrą Boole'a. Określamy
:<math>{\rm length}({\mathbb B})=\sup\big\{|A|:A\subseteq {\mathbb B}</math> jest łańcuchem <math>\big\}</math>
:<math>{\rm depth}({\mathbb B})=\sup\big\{ |A|:A\subseteq {\mathbb B}</math> jest [[Dobry porządek|dobrze uporządkowanym]] łańcuchem <math>\big\}</math>.
* [[Przegląd zagadnień z zakresu matematyki]],
* [[częściowy porządek]],
* [[antyłańcuch]].▼
▲* [[antyłańcuch]]
[[Kategoria:Teoria mnogości]]
| |||