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: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$.

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:\{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

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