Ilość relacji na zbiorze.

[aussie]

Witam, mam problem z poniższym zadaniem:
Niech dany będzie n-elementowy zbiór X, ile można w tym zbiorze zdefiniować relacji symetrycznych?
Odpowiedź to \(\displaystyle{ 2 ^{n+\frac{n(n-1)}{2}}}\), tylko nie mogę dojść dlaczego. Czy mógłby ktoś mi wyjaśnić skąd taka zależność, chociażby na przykładzie \(\displaystyle{ \{1,2\}}\), bo według tego wzoru wychodzi, że dla dwuelementowego zbioru mamy \(\displaystyle{ 8}\) relacji symetrycznych, i wydaje mi się, że to trochę za dużo.

[Lorek]

Dla zbioru dwuelementowego \(\displaystyle{ X=\{1,2\}}\) masz
\(\displaystyle{ \emptyset,\ \{(1,1)\},\ \{(2,2)\},\ \{(1,2),(2,1)\},\ \{(1,1),(1,2),(2,1)\},\ \{(2,2),(1,2),(2,1)\},\ \{(1,1),(2,2)\},\ X^2}\)
a co do wyniku to spróbuj dojść do tego ile może być relacji na zbiorze \(\displaystyle{ n+1}\) - elementowym jeśli na \(\displaystyle{ n}\) - elementowym jest ich \(\displaystyle{ a_n}\).

[lukasz.przontka]

Podpowiem Ci jak to wygląda dla zbioru dwuargumentowego. Naszą relację będziemy oznaczali \(\displaystyle{ \star}\)
Z definicji relacji symetrycznej mamy:
\(\displaystyle{ x \star y \Rightarrow y \star x}\)

Stwórzmy sobie wykres relacji \(\displaystyle{ \star}\).\(\displaystyle{ \bullet}\) będziemy oznaczać, że element z wiersza jest w relacji z elementem z kolumny. Dla przykładu:

\(\displaystyle{ \begin{tabular}{c|c|c}
\star & 0 & 1 \\ \hline
0 & & \bullet \\ \hline
1 & & \\
\end{tabular}}\) - ta relacja nie jest symetryczna

Oznacza, że \(\displaystyle{ 0 \star 1}\)

Jak symetryczność relacji wpływa na jej wykres? Jest on symetryczny względem przekątnej, np.:

\(\displaystyle{ \begin{tabular}{c|c|c}
\star & 0 & 1 \\ \hline
0 & & \bullet \\ \hline
1 & \bullet & \\
\end{tabular}}\) - ta relacja jest symetryczna. Dokładniej jest to \(\displaystyle{ \{(1,2), (2,1)\}}\)

Zatem żeby tworzyć relacje symetryczne musimy jedynie wstawiać kropki w górny trójkąt macierzy wraz z przekątną (dolna część uzupełni się "sama"). Dodatkowo kropki możemy wstawiać niezależnie. Zatem liczba relacji symetrycznych wynosi \(\displaystyle{ 2^k}\), gdzie \(\displaystyle{ k}\) to liczba pól w które możemy wstawiać kropki.
W naszym przypadku \(\displaystyle{ k}\) wynosi 3.

Resztę możesz już policzyć sama.

[aussie]

Właśnie chyba jeszcze nie do końca potrafię sobie tego wyobrazić. A patrząc na te wypisane podzbiory to mamy takie relacje: \(\displaystyle{ \left\{(1,2),(2,1) \right\},\left\{ (1,1),(1,2),(2,1)\right\},\left\{ (2,2),(1,2),(2,1)\right\},\left\{ (1,1),(1,2),(2,1),(2,2)\right\}}\) i nie mogę znaleźć tych pozostałych 4 relacji. I dlaczego ten wzór przyjmuje potęgę 2, te 2 kropki zaznaczone są chyba traktowane jako 1 relacja?

[lukasz.przontka]

Pozostały Ci jeszcze relacje:
\(\displaystyle{ \emptyset}\)
\(\displaystyle{ \{(1,1)\}}\)
\(\displaystyle{ \{(2,2)\}}\)
\(\displaystyle{ \{(1,1), (2,2)\}}\)

Zauważ, że w dane pole możemy wstawić kropkę, lub jej nie wstawić. Zatem mamy 2 możliwości na "zapełnienie" pola. Pól które możemy "zapełnić" jest \(\displaystyle{ k}\) (musisz policzyć dokładnie ile ich jest). Zatem wszystkich możliwości mamy \(\displaystyle{ \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{k} = 2^k}\)

[aussie]

Okej, już wszystko jasne, dziękuje serdecznie za pomoc .

[darlove]

Wystarczy zauwazyc, ze kazdy zbior n-elementowy mozna wzajemnie jednoznacznie przeksztalcic na zbior pierwszych n liczb naturalnych (nie chodzi o liczby pierwsze), a kazda relacja na takim wyjsciowym zbiorze jest pewna relacja na zbiorze tych pierwszych liczb. Co wiecej, relacja symetryczna na zbiorze wyjsciowym pozostaje symetryczna na zbiorze liczb, w ktory odwzorowujemy. Wystarczy zatem policzyc, ile jest relacji symetrycznych na zbiorze n-elementowym zawartym w \(\displaystyle{ \mathbb{N}}\), np. w \(\displaystyle{ \{1,2,3,\ldots,n\}}\). Kazda relacja to po prostu podzbior iloczynu kartezjanskiego danego zbioru, czyli u nas zbioru \(\displaystyle{ A=\{1,2,3,\ldots,n\}}\). Wyobraz sobie kwadrat o boku na osi \(\displaystyle{ x}\) i drugim na \(\displaystyle{ y}\). Pierwszy bok sklada sie z punktow \(\displaystyle{ 1,2,3,\ldots,n}\); drugi - to samo. Co to znaczy, ze relacja jest symetryczna? To znaczy, ze wraz z punktem \(\displaystyle{ (a, b)}\) nalezy tam punkt \(\displaystyle{ (b, a)}\). Wystarczy zatem policzyc, ile mozna utworzyc podzbiorow w tym zbiorze: \(\displaystyle{ B=\{(a, b): b\leq a\wedge a,b\in A\}}\). Poniewaz licznosc zbioru \(\displaystyle{ B}\) wynosi \(\displaystyle{ \frac{n^2-n}{2}+n}\), wiec w zbiorze \(\displaystyle{ A}\) jest \(\displaystyle{ 2^{ {{n+1} \choose 2} }}\) elementow, a zatem tyle wlasnie relacji symetrycznych.