Transwersala

Szablon:Dopracować Transwersala – zbió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

Niech $𝕊$ będzie rodziną zbiorów. Transwersala rodziny zbiorów $𝕊$ to taki zbiór $A,$ ż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 $f:A\to 𝕊$ taka, że

$(\mathrm{\forall }a\in A)(a\in f(a))$ oraz $(\mathrm{\forall }S\in 𝕊)(\mathrm{\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 $𝒮=⟨S_i:i\in I⟩$ 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 $A=⟨a_i:i\in I⟩$ taki że $a_i\in S_i$ dla wszystkich $i\in I$.

Przykłady i własności

• Zbiór $\{a,b,c,d,e\}$ jest transwersalą dla rodziny

$𝕊=\{\{a,f,g\},\{b,c,f,g,h\},\{c,f,g,h,i\},\{d,f,g\},\{e\}\},$

bowiem funkcja $f:\{a,b,c,d,e\}\to 𝕊$ 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 $⟨S_1,S_2,S_3,S_5⟩.$ Natomiast nie istnieje żadna transwersala dla $⟨S_1,S_2,S_3,S_4,S_5⟩.$
• 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 $𝒮=⟨S_1,\dots ,S_n⟩$ 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 $m$ zbiorów $S_k$ zawiera przynajmniej $m$ elementów $(1⩽k⩽m).$

Inne znaczenia terminu

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