Łańcuch (teoria mnogości)


Łańcuch (teoria mnogości) w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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

Spis treści

Definicja | edytuj kod

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

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

Innymi słowy zbiór A {\displaystyle A} jest łańcuchem wtedy i tylko wtedy, gdy relacja {\displaystyle \sqsubseteq } porządkuje go liniowo, czyli jest ona relacją spójną w A . {\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 kod

  • Zauważmy, że każdy zbiór jednoelementowy jest łańcuchem (i jednocześnie jest też antyłańcuchem).
  • Rozważmy płaszczyznę R 2 {\displaystyle \mathbb {R} ^{2}} z porządkiem częściowym zdefiniowanym przez
x 1 , y 1 0 x 2 , y 2 {\displaystyle \langle x_{1},y_{1}\rangle \leqslant _{0}\langle x_{2},y_{2}\rangle } wtedy i tylko wtedy, gdy x 1 x 2 {\displaystyle x_{1}\leqslant x_{2}} i y 1 y 2 . {\displaystyle y_{1}\leqslant y_{2}.} (Powyżej, {\displaystyle \leqslant } jest standardową nierównością na prostej rzeczywistej R . {\displaystyle \mathbb {R} .} ) Wówczas każda prosta pionowa i każda prosta o nieujemnym współczynniku kierunkowym jest łańcuchem w ( R 2 , 0 ) . {\displaystyle (\mathbb {R} ^{2},\leqslant _{0}).} Także wykres dowolnej funkcji rosnącej jest łańcuchem w tym porządku.
  • Rozważmy zbiór ω > 2 {\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 η : ω 2 {\displaystyle \eta :\omega \longrightarrow 2} połóżmy A η = { η n : n ω } . {\displaystyle A_{\eta }=\{\eta \upharpoonright n:n\in \omega \}.} Wówczas A η {\displaystyle A_{\eta }} jest łańcuchem w ( ω > 2 , ) . {\displaystyle (^{\omega >}2,\trianglelefteq ).} Ponadto każdy łańcuch w tym porządku częściowym jest zawarty w zbiorze A η {\displaystyle A_{\eta }} dla pewnego η : ω 2. {\displaystyle \eta :\omega \longrightarrow 2.}
  • Twierdzenie Dilwortha mówi, że częściowy porządek ( P , ) {\displaystyle (P,\sqsubseteq )} jest sumą n {\displaystyle n} łańcuchów ( n N ) {\displaystyle (n\in \mathbb {N} )} wtedy i tylko wtedy, gdy P {\displaystyle P} nie zawiera n + 1 {\displaystyle n+1} elementowych antyłańcuchów (w sensie teorii posetów).

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

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

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

l e n g t h ( B ) = sup { | A | : A B {\displaystyle \mathrm {length} (\mathbb {B} )=\sup {\big \{}|A|:A\subseteq \mathbb {B} } jest łańcuchem } {\displaystyle {\big \}}} d e p t h ( B ) = sup { | A | : A B {\displaystyle \mathrm {depth} (\mathbb {B} )=\sup {\big \{}|A|:A\subseteq \mathbb {B} } jest dobrze uporządkowanym łańcuchem } . {\displaystyle {\big \}}.}

Zobacz też | edytuj kod

Na podstawie artykułu: "Łańcuch (teoria mnogości)" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy