Transwersala

Ten artykuł od 2011-08 zawiera treści, przy których brakuje odnośników do źródeł.

Należy dodać przypisy do treści niemających odnośników do źródeł. Dodanie listy źródeł bibliograficznych jest problematyczne, ponieważ nie wiadomo, które treści one uźródławiają.
Sprawdź w źródłach: Google Books • Google Scholar • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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

${\displaystyle (\forall a\in A)(a\in f(a))}$ oraz ${\displaystyle (\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 ${\displaystyle {\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 ${\displaystyle {\mathcal {S}}}$ to taki ciąg różnowartościowy ${\displaystyle A=\langle a_{i}:i\in I\rangle }$ taki że ${\displaystyle a_{i}\in S_{i}}$ dla wszystkich ${\displaystyle i\in I}$.

Przykłady i własności

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

${\displaystyle \mathbb {S} ={\Big \{}\{a,f,g\},\{b,c,f,g,h\},\{c,f,g,h,i\},\{d,f,g\},\{e\}{\Big \}},}$

bowiem funkcja ${\displaystyle f\colon \{a,b,c,d,e\}\to \mathbb {S} }$ dana przez

${\displaystyle f(a)=\{a,f,g\},}$ ${\displaystyle f(b)=\{b,c,f,g,h\},}$ ${\displaystyle f(c)=\{c,f,g,h,i\},}$ ${\displaystyle f(d)=\{d,f,g\},}$ ${\displaystyle 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 ${\displaystyle S_{1}=S_{2}=\{1,2\},}$ ${\displaystyle S_{3}=S_{4}=\{2,3\}}$ oraz ${\displaystyle S_{5}=\{1,4,5,6\}.}$ Wówczas zbiór ${\displaystyle \{1,2,3,4\}}$ jest systemem różnych reprezentantów dla ciągu ${\displaystyle \langle S_{1},S_{2},S_{3},S_{5}\rangle .}$ Natomiast nie istnieje żadna transwersala dla ${\displaystyle \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 ${\displaystyle {\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 ${\displaystyle {\mathcal {S}}}$ ma transwersalę wtedy i tylko wtedy, gdy suma dowolnych ${\displaystyle m}$ zbiorów ${\displaystyle S_{k}}$ zawiera przynajmniej ${\displaystyle m}$ elementów ${\displaystyle (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.

Przypisy