Równoliczność zbiorów, parę prostych pytań.

[Jakub Gurak]

\(\displaystyle{ \left| \NN^{\NN} \right| \le \left| \left( 2^{ \NN}\right)^{\NN} \right|}\) Spotkałem takie naturalne szacowanie, ale nie odnotowane jako prawo. Czy zatem jest prawo, że dla dowolnych zbiorów \(\displaystyle{ A,B,C}\) jeśli \(\displaystyle{ \left| A\right| \le \left| B\right|,}\) to \(\displaystyle{ \left| A ^{C} \right| \le \left| B ^{C} \right|?}\)

Kolejne pytanie: Jak się dowodzi, że zbiory \(\displaystyle{ A \times B}\) i \(\displaystyle{ B \times A}\) są równoliczne? Czy wystarczy zdefiniować bijekcję \(\displaystyle{ f: A\times B\rightarrow B \times A}\) jako \(\displaystyle{ f\left( a,b\right)=\left( b,a\right)}\)?

A że zbiory \(\displaystyle{ \left( A \times B\right) \times C}\) i \(\displaystyle{ A \times \left( B \times C\right)}\) są równoliczne? Czy wystarczy zdefiniować bijekcję \(\displaystyle{ f: \left( A \times B\right) \times C \rightarrow A \times \left( B \times C\right)}\) jako \(\displaystyle{ f\left( \left( a,b\right),c \right)= \left( a, \left( b,c\right) \right)}\) ?

[Dasio11]

Trzy razy: tak.

[Jakub Gurak]

Zastanawia mnie teraz czy moc iloczynu kartezjańskiego skończenie wielu \(\displaystyle{ n}\) zbiorów( \(\displaystyle{ n \ge 3}\)) ,czyli iloczyn kartezjański dwóch zbiorów stosowany wielokrotnie (powiedzmy, że wykonujemy tą operację po kolei od lewej do prawej), ale moc takiego iloczynu kartezjańskiego zależy jedynie od mocy tych że zbiorów, a nie od kolejności w jakiej mnożymy kartezjańsko te zbiory? Ściślej rzecz biorąc:

Rozważmy zbiory \(\displaystyle{ X _{1},X _{2},X _{3},\ldots,X _{n} }\), czy dla dowolnej permutacji \(\displaystyle{ f:\left\{ 1,2,3,\ldots,n \right\} \rightarrow \left\{ 1,2,3\ldots,n \right\} }\) zbioru \(\displaystyle{ \left\{ 1,2,3,\ldots,n \right\} }\)(przestawienie kolejności tych indeksów \(\displaystyle{ 1,2,\ldots, n }\)) mamy:

\(\displaystyle{ \left( \left( X _{f _{1} } \times X _{f _{2} } \right) \times\ldots \times X _{f _{n} } \right)\sim \left( \left( X _{1} \times X _{2} \right) \times \ldots \times X _{n} \right)?}\)

Czy to wynika z powyższych praw równoliczości?

Ja tylko przekonałem się lekko dla czterech zbiorów wypisując ich (i to nawet nie wszystkie, ich jest za dużo, ale trochę mi to pomogło) możliwe ich iloczyny kartezjańskie. Tu już jest dużo możliwości. A co gdy zbiorów jest więcej- 5,6,..., 100

Oczywiście wiem, że wielu matematyków nie zadawałoby takich pytań

NIE POPIERAM TEGO:    

Nawet by te wszystkie możliwe iloczyny kartezjańskie oznaczali jednym symbolem (jakby mnożenie kartezjańskie było łączne, a nie jest), no może napisaliby dwa słowa "wyjaśnienia" typu: zbiory można utożsamić, jakoś do mnie to nie trafia. Także zdecydowanie nie popieram , ale zostawie ten temat na inną dłuższą dyskusję.

Ja wolę być ostrożny nawet mówiąc o równoliczości tych iloczynów kartezjańskich( dopóki tego nie udowodnię).

[Jan Kraszewski]

Oczywiście wiem, że wielu matematyków nie zadawałoby takich pytań

Bo raczej nie widzieliby potrzeby, gdyż to dość prosty fakt.

Zakładam, że akceptujesz fakt, iż dla zbiorów skończonych \(\displaystyle{ \left| X_1\times X_2\right|=|X_1|\cdot |X_2| }\) oraz że gdy przynajmniej jeden ze zbiorów \(\displaystyle{ X_1,X_2}\) jest nieskończony, to \(\displaystyle{ \left| X_1\times X_2\right|=\max\{|X_1|, |X_2|\} }\). W prosty sposób możesz indukcyjnie pokazać, że:

1. Jeśli wszystkie zbiory \(\displaystyle{ X _{1},X _{2} \ldots X _{n}}\) są skończone, to \(\displaystyle{ \left| \left( \left( X _{1} \times X _{2} \right) \times \ldots \times X _{n} \right)\right|= \prod_{i=1}^{n} | X _{i}|. }\)

2. Jeśli jeden ze zbiorów \(\displaystyle{ X _{1},X _{2} \ldots X _{n}}\) jest nieskończony, to \(\displaystyle{ \left| \left( \left( X _{1} \times X _{2} \right) \times \ldots \times X _{n} \right)\right|=\max\{| X _{1}|,|X _{2}| \ldots |X _{n}|\}. }\)

skąd od razu masz swoją tezę.

Inna sprawa, że bijekcja pomiędzy \(\displaystyle{ \left( \left( X _{1} \times X _{2} \right) \times \ldots \times X _{n} \right)}\) a \(\displaystyle{ \left( \left( X _{f _{1} } \times X _{f _{2} } \right) \times\ldots \times X _{f _{n} } \right)}\) jest dość oczywista. Jeżeli \(\displaystyle{ n}\)-kę uporządkowaną definiujemy jako \(\displaystyle{ \left( x_1,x_2,...,x_n\right):= \left( \left( x _{1}, x _{2} \right), \ldots ,x _{n} \right),}\) to bijekcję \(\displaystyle{ \phi:\left( \left( X _{1} \times X _{2} \right) \times \ldots \times X _{n} \right)\to \left( \left( X _{f _{1} } \times X _{f _{2} } \right) \times\ldots \times X _{f _{n} } \right)}\) definiujesz wzorem \(\displaystyle{ \phi(x_1,x_2,...,x_n)=(x_{f_1},x_{f_2},...,x_{f_n}).}\)

Ja wolę być ostrożny nawet mówiąc o równoliczości tych iloczynów kartezjańskich( dopóki tego nie udowodnię).

Nikt Ci tego nie wyrzuca. Ale tracisz w ten sposób mnóstwo czasu i energii.

JK

[Jakub Gurak]

\(\displaystyle{ }\)Jeżeli \(\displaystyle{ n}\)-kę uporządkowaną definiujemy jako \(\displaystyle{ \left( x_1,x_2,...,x_n\right):= \left( \left( x _{1}, x _{2} \right), \ldots ,x _{n} \right),}\) to bijekcję \(\displaystyle{ \phi:\left( \left( X _{1} \times X _{2} \right) \times \ldots \times X _{n} \right)\to \left( \left( X _{f _{1} } \times X _{f _{2} } \right) \times\ldots \times X _{f _{n} } \right)}\) definiujesz wzorem \(\displaystyle{ \phi(x_1,x_2,...,x_n)=(x_{f_1},x_{f_2},...,x_{f_n}).}\)

Może domyślam się co to może oznaczać, ale nie wiem co oznacza \(\displaystyle{ x _{m} }\) (dla \(\displaystyle{ m \in \left\{ 1,2,\ldots,n \right\} .}\)). Dokładniej nie wiedziałem, choć w tym momencie mi coś zaświtało, zdziwienie moje wywołał zapis:

\(\displaystyle{ x _{f _{1} }, x _{f _{2} } ,\ldots }\)

Czy chodzi o to, że np. gdy n=3, a \(\displaystyle{ f=\left( 3,1,2\right)}\), to \(\displaystyle{ \alpha: \left( X _{1} \times X _{2} \right) \times X _{3}\rightarrow \left( X _{3} \times X_{1} \right) \times X _{2} }\) jest dana jako:

\(\displaystyle{ \alpha \left( x _{1},x _{2},x _{3} \right) =\left( x _{3},x _{1},x _{2} \right). }\)

Co już jest w miarę jasne- funkcja \(\displaystyle{ \alpha}\) dostaje trzy argumenty kolejno ze zbiorów \(\displaystyle{ X _{1},X _{2},X _{3} }\) (formalnie jeden argument będący trójką argumentów ), i przypisuje im trójkę złożoną kolejno z trzeciej współrzędnej, pierwszej współrzędnej, drugiej współrzędnej trojki, która była na wejściu .

I Pana zapis rozumiem, że to jest uogólnienie tego przypadku, tak W podobny sposób, tak

[Jan Kraszewski]

Może domyślam się co to może oznaczać, ale nie wiem co oznacza \(\displaystyle{ x _{m} }\) (dla \(\displaystyle{ m \in \left\{ 1,2,\ldots,n \right\} .}\)). Dokładniej nie wiedziałem, choć w tym momencie mi coś zaświtało, zdziwienie moje wywołał zapis:

\(\displaystyle{ x _{f _{1} }, x _{f _{2} } ,\ldots }\)

Użyłem w zasadzie Twoich oznaczeń...

I Pana zapis rozumiem, że to jest uogólnienie tego przypadku, tak

Tak.

JK

[Jakub Gurak]

zdziwienie moje wywołał zapis:

\(\displaystyle{ x _{f _{1} }, x _{f _{2} } ,\ldots }\)

Użyłem w zasadzie Twoich oznaczeń ...

Nie bardzo- ja wprowadziłem tylko notacje dla zbiorów \(\displaystyle{ X _{1},X _{2},\ldots,X _{n} }\) ( tu iksy są z dużych liter), i dla permutacji f, a iksy z małych liter nie wprowadzałem. Dodam jeszcze, że teraz gdy już to zrozumiałem, to gdy Pan użył tych wlasnych oznaczeń argumentów, to (gdy już to rozumiem), to Pan operował na nich w przepisie funkcji(w sumie normalna rzecz) na tych własnych oznaczeniach tych zmiennych.

Z drugiej strony nie jest to przytyk, gdyż musiał Pan jakoś oznaczyć elementy tych że zbiorów (chyba nie byłoby znaczenia jakby oznaczenia zmiennych byłyby zupełnie inne, tylko po co cudować ), ale ja notacji na oznaczenia elementów tych zbiorów nie wprowadziłem, gdyż nie zaszła taka potrzeba, stąd było moje zdziwienie co oznaczały te iksy z małych liter z podwójnymi indeksami.

Ale dziękuję, już chyba rozumiem, nigdy na takie zapisy, pomysły bym nie wpadł.

[Jan Kraszewski]

No cóż, dość naturalne jest, gdy przyjmę, że \(\displaystyle{ x_i\in X_i}\). A wtedy oczywiście \(\displaystyle{ x_{f_i}\in X_{f_i}}\) - tak zapisywałeś spermutowane indeksy (\(\displaystyle{ f_i=f(i)}\)). I w tym sensie jest to konsekwencja Twojego zapisu - ja tu nic nie wprowadzałem.

JK

[Jakub Gurak]

jest prawo, że dla dowolnych zbiorów \(\displaystyle{ A,B,C}\) jeśli \(\displaystyle{ \left| A\right| \le \left| B\right|,}\) to \(\displaystyle{ \left| A ^{C} \right| \le \left| B ^{C} \right|?}\)

Udowodniłem zatem przed chwilą, że jeśli \(\displaystyle{ X}\) jest zbiorem równolicznym ze zbiorem \(\displaystyle{ \NN}\), a \(\displaystyle{ Y}\) dowolnym zbiorem co najmniej dwuelementowym i o mocy co najwyżej continuum, to zbiór funkcji \(\displaystyle{ Y^X}\) jest mocy continuum. Udowodnię to zaraz.


Nim to zrobię, przypomnę taki (trochę grubszy ) fakt z teorii mocy, że zbiór \(\displaystyle{ \RR ^{\NN}}\) , czyli zbiór wszystkich ciągów liczb rzeczywistych, jest mocy continuum- udowodniono to chyba w Guzickim ""Wstępie do matematyki".

Przejdźmy do dowodu naszego faktu:

Ponieważ zbiór \(\displaystyle{ Y}\) jest co najmniej dwuelementowy, to \(\displaystyle{ \left| Y\right| \ge \left\{ 0,1\right\} }\)- (ławo jest wskazać funkcję różnowartościową ze zbioru \(\displaystyle{ \left\{ 0,1\right\}}\) w zbiór \(\displaystyle{ Y}\) ) . I wtedy, na mocy zacytowanego prawa:

\(\displaystyle{ \left| Y^X\right| \ge \left| \left\{ 0,1\right\} ^{X} \right| \stackrel{X\sim \NN}{=} \left| 2 ^{\NN} \right|= \left| \RR\right| .}\)

Z drugiej strony, ponieważ zbiór \(\displaystyle{ Y}\) ma moc co najwyżej continuum, to:

\(\displaystyle{ \left| Y^X\right| \le \left| \RR^X\right| \stackrel {X\sim \NN}{=} \left| \RR ^{\NN}\right| =\left| \RR\right| .}\)

Na mocy twierdzenia Cantora-Bernsteina: zbiór \(\displaystyle{ Y^X}\) jest mocy continuum\(\displaystyle{ .\square}\)

[Jan Kraszewski]

Nim to zrobię, przypomnę taki (trochę grubszy ) fakt z teorii mocy, że zbiór \(\displaystyle{ \RR ^{\NN}}\) , czyli zbiór wszystkich ciągów liczb rzeczywistych, jest mocy continuum- udowodniono to chyba w Guzickim ""Wstępie do matematyki".

Ten fakt był dobrze znany sporo przed narodzinami dr. Guzickiego... A fakt nie jest grubszy, tylko dość podstawowy, bo skoro \(\displaystyle{ \RR\sim 2^\NN,}\) to \(\displaystyle{ \RR^\NN\sim\left( 2^\NN\right)^\NN\sim 2^{\NN\times\NN}\sim 2^\NN\sim \RR. }\)

JK