Transwersala

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 $\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\colon A\to \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$.

Przykłady i własności

• 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\colon \{a,b,c,d,e\}\to \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},\dots ,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

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