Łańcuch (teoria mnogości)

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

Łańcuchy to 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 zbiór nazywamy łańcuchem wtedy i tylko wtedy, gdy

.

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

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ę z porządkiem częściowym zdefiniowanym przez
wtedy i tylko wtedy, gdy i .
(Powyżej, jest standardową nierównością na prostej rzeczywistej .) Wówczas każda prosta pionowa i każda prosta o nieujemnym współczynniku kierunkowym jest łańcuchem w . Także wykres dowolnej funkcji rosnącej jest łańcuchem w tym porządku.
  • Rozważmy zbiór wszystkich skończonych ciągów zero-jedynkowych uporządkowany (częściowo) przez relację wydłużania ciągów. Dla ciągu nieskończonego połóżmy . Wówczas jest łańcuchem w . Ponadto każdy łańcuch w tym porządku częściowym jest zawarty w zbiorze dla pewnego .
  • Twierdzenie Dilwortha mówi że częściowy porządek jest sumą łańcuchów () wtedy i tylko wtedy, gdy nie zawiera 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 będzie zbiorem częściowo uporządkowanym.

  • Powiemy że spełnia warunek rosnących łańcuchów lub ACC (od ang. ascending chain condition) jeśli każdy rosnący łańcuch jest od pewnego miejsca stały.
  • Podobnie mówimy że spełnia warunek malejących łańcuchów lub DCC (od ang. descending chain condition) jeśli każdy malejący łańcuch 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 jest zupełną algebrą Boole’a, to każdy antyłańcuch w jest przeliczalny wtedy i tylko wtedy, gdy w algebrze nie istnieje nieprzeliczalny ściśle malejący ciąg ().

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

jest łańcuchem
jest dobrze uporządkowanym łańcuchem .

Zobacz też[edytuj | edytuj kod]