Przejdź do zawartości

Transwersala

Z Wikipedii, wolnej encyklopedii

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 | edytuj kod]

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 | edytuj kod]
  • 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 | edytuj kod]
  • 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

[edytuj | edytuj kod]
  1. Robin J. Wilson: Wprowadzenie do teorii grafów, Państwowe Wydawnictwo Naukowe, Warszawa 1985, s. 157–160. ISBN 83-01-05247-3.