Łańcuch (teoria mnogości).html

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 totalna.

Spis treści

1 Definicja
2 Przykłady i własności
3 Warunki łańcucha
4 Funkcje kardynalne
5 Zobacz też

edytuj 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.

edytuj 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 $ω > 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 η$ jest łańcuchem w $({}^{\omega>}2,\trianglelefteq)$ . Ponadto każdy łańcuch w tym porządku częściowym jest zawarty w zbiorze $A η$ 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).

edytuj 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$ (

α < ω 1

edytuj 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ść $depth$ i długość $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\}$ .