Transwersala

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Transwersalazbiór powstały z wybrania po jednym elemencie ze zbiorów danej rodziny (wymaga się zwykle, aby wybrane elementy były parami różne, wtedy moc transwersali jest równa mocy rodziny).

W użyciu są różne definicje tego terminu. Najczęściej jest on używany w matematyce dyskretnej w znaczeniach podanych poniżej, ale występuje też poza tą dziedziną matematyki w nieco odmiennych, choć pokrewnych znaczeniach.

Definicja[edytuj]

Niech będzie rodziną zbiorów. Transwersala rodziny zbiorów to taki zbiór że można wybrać bijekcję ze zbioru A na rodzinę , która każdemu elementowi zbioru A przyporządkowuje pewien zbiór, do którego element ten należy. Tak więc A jest transwersalą rodziny jeśli istnieje funkcja taka, że

oraz .

Pojęcie transwersali wprowadza się również dla indeksowanych rodzin zbiorów pozwalając na ich powtórzenia w indeksowaniu. Niech będzie ciągiem (niekoniecznie różnych) zbiorów. Transwersala (system różnych reprezentantów) dla ciągu to taki ciąg różnowartościowy taki że dla wszystkich [1].

Przykłady i własności[edytuj]

  • Zbiór jest transwersalą dla rodziny
,

bowiem funkcja dana przez

, , , ,

jest bijekcją świadczącą o tym fakcie.

  • Transwersale dla rodzin zbiorów parami rozłącznych są także nazywane selektorami z tych rodzin. Dla każdej skończonej rodziny parami rozłącznych zbiorów niepustych można wybrać selektor (transwersalę). Przy założeniu AC, każda rodzina parami rozłącznych zbiorów niepustych ma transwersale.
  • Rozważmy zbiory , oraz . Wówczas zbiór jest systemem różnych reprezentantów dla ciągu . Natomiast nie istnieje żadna transwersala dla .
  • Nawet rodziny zbiorów bez powtórzeń mogą nie mieć transwersali. Charakteryzacja skończonych rodzin (indeksowanych) dopuszczających transwersale jest dana przez twierdzenie o kojarzeniu małżeństw:
Twierdzenie Halla
Niech będzie skończonym ciągiem (niekoniecznie różnych) niepustych zbiorów skończonych. Wówczas ma transwersalę wtedy i tylko wtedy, gdy suma dowolnych zbiorów zawiera przynajmniej elementów ().

Inne znaczenia terminu[edytuj]

  • W geometrii, transwersala (prosta transwersalna) dla danej rodziny prostych to prosta przecinająca wszystkie proste z tej rodziny.
  • Transwersala kwadratu łacińskiego rzędu n to wybór n pozycji w tym kwadracie w taki sposób, że w każdym wierszu i każdej kolumnie wybrano jedną pozycję oraz że każdy symbol pojawia się w jakiejś pozycji.
  • W geometrii różniczkowej i topologii różniczkowej rozważa się przekroje transwersalne.

Przypisy

  1. Wilson, Robin J.: Wprowadzenie do teorii grafów. Państwowe Wydawnictwo Naukowe, Warszawa 1985. Strony 157-160. ISBN 83-01-05247-3