Liczba funkcji oraz relacji.

[Emiel Regis]

Prosze o sprawdzenie poprawnosci moich wyników. Ewentualnie korektę wraz z komentarzem.
Co prawda zbiory X lub Y niekoniecznie są dyskretne jednak zamieściłem to w tym dziale gdyż liczyłem to w sposób kombinatoryczny.

1. Moc zbioru wszystkich funkcji z X do Y
\(\displaystyle{ |\{f| \ f: X \to Y\}| = |Y|^{|X|}}\)

2. Moc zbioru wszystkich relacji
\(\displaystyle{ |\{R: R X Y\}|=2^{|Y|} |X|}\)

\(\displaystyle{ |\{R: R X ... \X =X^n\}|=(2^{|X|})^n |X|}\)

[andkom]

1. O.K.
2. Powinno raczej być
\(\displaystyle{ |\{R: R X Y\}|=2^{|Y|\cdot |X|}}\)
oraz
\(\displaystyle{ |\{R: R X ... \X =X^n\}|=2^{|X|^n}}\)

[Emiel Regis]

Tak czułem że coś źle robię bo znalazłem wynik w wikipedii i mi się nie zgodził... (choć zawsze jest nadzieja że u nich błąd: p )

Natomiast nie sam wynik a rozumowanie jest dla mnie ważniejsze, napisze jak sam to liczyłem na przykladzie X i Y dyskretnych. Mamy tak:
\(\displaystyle{ X=\{1, 2, ..., m\} \\ Y = \{1, 2, ..., n\}}\)

No to zajmijmy się liczbą relacji z X do Y.
\(\displaystyle{ |\{R: R X Y\}|=2^{|Y|} |X|}\)
Pierwszemu punktowi z X mogę przyporządkować wszystkie możliwe podzbiory ze zbioru Y, a tych jest mianowicie \(\displaystyle{ 2^n}\), z kolei wiedząc że w X punktów mam m to rozumuję że różnych relacji moge otrzymać \(\displaystyle{ m 2^n}\).

Kolejne:
\(\displaystyle{ |\{R: R X ... \X =X^n\}|=(2^{|X|})^n |X|}\)
Biorę sobie pierwszy punkt z X, mogę mu przyporządkować \(\displaystyle{ 2^m}\) punktów z kolejnego zbioru a także z każdego nastepnego czyli mam już możliwosci \(\displaystyle{ (2^m)^n}\), no i teraz podobnie, punktów w X mam m czyli wszystkich relacji mi wychodzi \(\displaystyle{ (2^m)^n m}\)

No i pytania:
1. Gdzie tu jest błąd?
2. Nawet gdyby powyższe rozumowanie było dobre to czy w ogóle mogę je przenieść na przypadek ciagły poprzez zastąpienie m i n mocami zbiorów X i Y...

(w pierwszym pytaniu z pierwszego postu liczyłem dokładnie na tej samej zasadzie wiec teraz nie wiem czy to przypadek że się zgodziło... Punktów w X jest m, każdemu mogę przypisać n punktów z Y, więc liczba funkcji to jest \(\displaystyle{ n^m}\))

[andkom]

No to zajmijmy się liczbą relacji z X do Y.
\(\displaystyle{ |\{R: R X Y\}|=2^{|Y|} |X|}\)
Pierwszemu punktowi z \(\displaystyle{ X}\) mogę przyporządkować wszystkie możliwe podzbiory ze zbioru \(\displaystyle{ Y}\), a tych jest mianowicie \(\displaystyle{ 2^n}\), z kolei wiedząc że w \(\displaystyle{ X}\) punktów mam \(\displaystyle{ m}\) to rozumuję że różnych relacji moge otrzymać \(\displaystyle{ m 2^n}\).

Relacja, to podzbiór produktu \(\displaystyle{ X\times Y}\). Produkt ten ma \(\displaystyle{ m\cdot n}\) elementów, a więc \(\displaystyle{ 2^{m\cdot n}}\) podzbiorów. I już. O żadnym przyporządkowywaniu punktom \(\displaystyle{ X}\) podzbiorów \(\displaystyle{ Y}\) nie trzeba mówić. Jeśli jednak koniecznie chcemy tak robić, to dostaniemy nie \(\displaystyle{ m\cdot2^n}\), lecz \(\displaystyle{ 2^n\cdot2^n\cdot\cdots\text{($m$ razy)}\cdots\cdot2^n\cdot2^n=(2^n)^m=2^{m\cdot n}}\)

[Emiel Regis]

No faktycznie! Od razu idzie. Dziekuje za pomoc.