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

Niech \mathbb{S} będzie rodziną zbiorów. Transwersala rodziny zbiorów \mathbb{S} to taki zbiór A że można wybrać bijekcję ze zbioru A na rodzinę \mathbb{S}, 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 \mathbb{S} jeśli istnieje funkcja f:A\longrightarrow \mathbb{S} taka, że

(\forall a\in A)(a\in f(a)) oraz (\forall S\in \mathbb{S})(\exists ! a\in A)(f(a)=S).

Pojęcie transwersali wprowadza się również dla indeksowanych rodzin zbiorów pozwalając na ich powtórzenia w indeksowaniu. Niech \mathcal{S}=\langle S_i:i\in I\rangle będzie ciągiem (niekoniecznie różnych) zbiorów. Transwersala (system różnych reprezentantów) dla ciągu \mathcal{S} to taki ciąg różnowartościowy A=\langle a_i:i\in I\rangle taki że a_i\in S_i dla wszystkich i\in I[1].

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

  • Zbiór \{a,b,c,d,e\} jest transwersalą dla rodziny
\mathbb{S}=\Big\{\{a,f,g\},\{b,c,f,g,h\},\{c,f,g,h,i\},\{d,f,g\},\{e\}\Big\},

bowiem funkcja f:\{a,b,c,d,e\}\longrightarrow \mathbb{S} dana przez

f(a)=\{a,f,g\}, f(b)=\{b,c,f,g,h\}, f(c)=\{c,f,g,h,i\}, f(d)=\{d,f,g\},  f(e)=\{e\}

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 S_1=S_2=\{1,2\}, S_3=S_4=\{2,3\} oraz S_5=\{1,4,5,6\}. Wówczas zbiór \{1,2,3,4\} jest systemem różnych reprezentantów dla ciągu \langle S_1, S_2,S_3,S_5 \rangle. Natomiast nie istnieje żadna transwersala dla \langle S_1,S_2,S_3,S_4,S_5 \rangle.
  • 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 \mathcal{S}=\langle S_1,\ldots,S_n\rangle będzie skończonym ciągiem (niekoniecznie różnych) niepustych zbiorów skończonych. Wówczas \mathcal{S} ma transwersalę wtedy i tylko wtedy, gdy suma dowolnych m zbiorów S_k zawiera przynajmniej m elementów (1\leqslant k\leqslant m).

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

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