Łatwo zauważyć, że każdy porządek liniowy na zbiorze skończonym jest dobry (bo np. w każdym skończonym zbiorze częściowo uporządkowanym jest element minimalny). Porządków dobrych na zbiorze skończonym jest zatem tyle, ile jest na nim porządków liniowych, a te wszystkie są ze sobą izomorficzne i różnią się tylko kolejnością elementów. Zatem na zbiorze \(\displaystyle{ n}\)-elementowym jest \(\displaystyle{ n!}\) dobrych porządków.
To samo, ale w trzech linijkach...
JK
Ale jakże nieformalnie. I nie cieszy tak, jak porządny dowód
Ile jest bijekcji z \(\displaystyle{ \RR}\) do \(\displaystyle{ \RR}\)
Myślę, że potrafię uzasadnić, że jest ich co najmniej continuum.
PRÓBA DOWODU::
Dla dowolnej ustalonej liczby rzeczywistej \(\displaystyle{ x}\) różnej od zera, rozważmy funkcję \(\displaystyle{ f_x}\) z \(\displaystyle{ \RR}\) do \(\displaystyle{ \RR}\), która zerze przypisuje liczbę \(\displaystyle{ x}\), a liczbie \(\displaystyle{ x}\) przypisuje \(\displaystyle{ 0}\), a na pozostałych argumentach jest identycznością. Ponieważ identyczność na zbiorze jest zawsze bijekcją, więc również \(\displaystyle{ f_x}\) jest bijekcją. I tak dla dowolnego \(\displaystyle{ x \neq 0}\) rozważamy bijekcję \(\displaystyle{ f_x}\).
I jeśli \(\displaystyle{ x_1 \neq x _{2}}\), to \(\displaystyle{ f _{x_1}\left( 0\right) = x _{1} \neq x_2=f _{x_2}(0)}\), a więc \(\displaystyle{ f _{x_1} \neq f _{x_2}. }\) A zatem tych bijekcji jest co najmniej tyle ile elementów zbioru \(\displaystyle{ \RR \setminus \left\{ 0\right\},}\) czyli continuum.
Pytanie jest teraz takie, czy nie ma tych bijekcji, czy nie ma ich więcej niż continuum, gdyż wszystkich funkcji z \(\displaystyle{ \RR}\) do \(\displaystyle{ \RR}\) jest \(\displaystyle{ 2 ^{\left| \RR\right| } }\). Nie wiem jak się za to zadanie zabrać, metoda ze zliczania bijekcji na zbiorze liczb naturalnych może tu nie podziałać, gdyż zbiór liczb rzeczywistych jest nieprzeliczalny. Pomoże ktoś???
Ile jest bijekcji z \(\displaystyle{ \RR}\) do \(\displaystyle{ \RR}\)
\(\displaystyle{ 2^{\mathfrak{c}}}\)
Pomyśl o odwzorowaniach, które przeprowadzają \(\displaystyle{ 0}\) na \(\displaystyle{ 0}\), a każdą dodatnią liczbę rzeczywistą zamieniają miejscami z liczbą do niej przeciwną - albo nie zamieniają. Masz continuum wiele decyzji (dla każdej dodatniej liczby rzeczywistej), czy zamienić ją miejscami z liczbą do niej przeciwną, czy też zostawić je nieruszone. Każdy układ takich decyzji zadaje inną bijekcję \(\displaystyle{ \RR}\) w \(\displaystyle{ \RR}\).
Jak chcesz to formalizować, to jest to injekcja z \(\displaystyle{ \{0,1\}^{(0,+\infty)}}\) w zbiór bijekcji \(\displaystyle{ \RR}\) w \(\displaystyle{ \RR}\), co daje Ci pożądane oszacowanie od dołu.
Pomyśl o odwzorowaniach, które przeprowadzają \(\displaystyle{ 0}\) na \(\displaystyle{ 0}\), a każdą dodatnią liczbę rzeczywistą zamieniają miejscami z liczbą do niej przeciwną - albo nie zamieniają. Masz continuum wiele decyzji (dla każdej dodatniej liczby rzeczywistej), czy zamienić ją miejscami z liczbą do niej przeciwną, czy też zostawić je nieruszone. Każdy układ takich decyzji zadaje inną bijekcję \(\displaystyle{ \RR}\) w \(\displaystyle{ \RR}\).
Jak chcesz to formalizować, to jest to injekcja z \(\displaystyle{ \{0,1\}^{(0,+\infty)}}\) w zbiór bijekcji \(\displaystyle{ \RR}\) w \(\displaystyle{ \RR}\), co daje Ci pożądane oszacowanie od dołu.
JK
Nie wiem czy dobrze to rozumiem.
Rozumiem, że definiujemy funkcję \(\displaystyle{ \alpha :\left\{ 0,1\right\} ^{\RR _{+} } \rightarrow \mathbb{B}, }\) gdzie \(\displaystyle{ \mathbb {B} }\) jest naszą rodziną wszystkich bijekcji, tak, że jeśli \(\displaystyle{ f:\RR _{+} \rightarrow \left\{ 0,1\right\}}\), to \(\displaystyle{ \alpha \left( f\right) = f'}\), gdzie:
\(\displaystyle{ f':\RR \rightarrow \RR,}\)
jest tak określona, że:
\(\displaystyle{ f'(0)=0;}\)
I jeśli (dla \(\displaystyle{ x \in\RR_+}\)): \(\displaystyle{ f(x)=1}\), to \(\displaystyle{ f'(x)=- x}\) i \(\displaystyle{ f' (-x)=x}\) (w ten sposób funkcja \(\displaystyle{ f'}\) jest określona na \(\displaystyle{ 0}\), na argumentach dodatnich i na argumentach do nich przeciwnych, czyli na całym \(\displaystyle{ \RR}\));
a jeśli \(\displaystyle{ f(x)=0}\), to funkcja \(\displaystyle{ f'}\) ma punkty stałe, czyli: \(\displaystyle{ f'(x)=x}\), i \(\displaystyle{ f'(- x)=- x}\), oto chodzi
Rozumiem, że definiujemy funkcję \(\displaystyle{ \alpha :\left\{ 0,1\right\} ^{\RR _{+} } \rightarrow \mathbb{B}, }\) gdzie \(\displaystyle{ \mathbb {B} }\) jest naszą rodziną wszystkich bijekcji, tak, że jeśli \(\displaystyle{ f:\RR _{+} \rightarrow \left\{ 0,1\right\}}\), to \(\displaystyle{ \alpha \left( f\right) = f'}\), gdzie:
\(\displaystyle{ f':\RR \rightarrow \RR,}\)
jest tak określona, że:
\(\displaystyle{ f'(0)=0;}\)
I jeśli (dla \(\displaystyle{ x \in\RR_+}\)): \(\displaystyle{ f(x)=1}\), to \(\displaystyle{ f'(x)=- x}\) i \(\displaystyle{ f' (-x)=x}\) (w ten sposób funkcja \(\displaystyle{ f'}\) jest określona na \(\displaystyle{ 0}\), na argumentach dodatnich i na argumentach do nich przeciwnych, czyli na całym \(\displaystyle{ \RR}\));
a jeśli \(\displaystyle{ f(x)=0}\), to funkcja \(\displaystyle{ f'}\) ma punkty stałe, czyli: \(\displaystyle{ f'(x)=x}\), i \(\displaystyle{ f'(- x)=- x}\), oto chodzi
Przed chwilą udało się ukończyć dowód faktu, że na zbiorze przeliczalnym (równolicznym ze zbiorem liczb naturalnych) istnieje dokładnie continuum dobrych porządków. Jest to o tyle zaskakujące, że dobre porządki na zbiorze przeliczalnym mogą być bardzo długie( chyba mogą sięgać, o krok wcześniej, od najmniejszej liczby nieprzeliczalnej, o której nie wiemy, czy jest równa continuum, czy może jest mniejsza, zgodnie z wiedzą odnośnie hipotezy continuum). A jednak, z przyczyn formalnych, łatwo jest udowodnić, że dobrych porządków na zbiorze przeliczalnym jest co najwyżej continuum. Wykazałem też ostatnio, że dla funkcji między dwoma zbiorami, dla dwóch podzbiorów dziedziny tej funkcji, wtedy obraz różnicy symetrycznej tych dwóch podzbiorów jest nadzbiorem różnicy symetrycznej obrazów tych dwóch podzbiorów. Przedstawię teraz dowody tych ciekawych faktów.
Podajmy najpierw pewien Lemat.
Lemat 1. Niech \(\displaystyle{ X}\) będzie zbiorem; a \(\displaystyle{ Y_1, Y_2}\) niech będą zbiorami równolicznymi ze zbiorem \(\displaystyle{ X}\). Wykażemy, że tyle samo jest bijekcji z \(\displaystyle{ X}\) do \(\displaystyle{ X,}\) co bijekcji z \(\displaystyle{ Y_1}\) do \(\displaystyle{ Y_2.}\)
Tzn. niech:
\(\displaystyle{ \mathbb{B}_X=\left\{ f:X \rightarrow X\Bigl| \ f \hbox{ jest bijekcją }\right\} .}\)
I niech:
\(\displaystyle{ \mathbb{B} _{Y_{1}, Y_{2} }=\left\{ f:Y_1 \rightarrow Y_2\Bigl| \ f \hbox{ jest bijekcją } \right\}.}\)
I wykażemy, że:
\(\displaystyle{ \mathbb{B}_X\sim \mathbb{B} _{Y _{1}, Y _{2} }.}\)
DOWÓD LEMATU:
Jeśli \(\displaystyle{ g\in \mathbb{B}_X}\), wtedy \(\displaystyle{ g:X \rightarrow X,}\) i funkcja \(\displaystyle{ g}\) jest bijekcją. Ponieważ \(\displaystyle{ Y_1\sim X}\), więc istnieje miedzy nimi bijekcja, nazwijmy ją \(\displaystyle{ f_1}\). Podobnie, niech \(\displaystyle{ f_2:X \rightarrow Y_2}\) będzie bijekcją (uzyskaną na podstawie równoliczności zbioru \(\displaystyle{ X}\) i zbioru \(\displaystyle{ Y_2}\)). Definiujemy funkcję \(\displaystyle{ \alpha}\) w poniższy sposób:
\(\displaystyle{ \alpha \left( g\right) = g'=f_2\circ g \circ f_1}\).
Wtedy \(\displaystyle{ g': Y_1 \rightarrow Y_2,}\) i funkcja \(\displaystyle{ g'}\) jest bijekcją (jako złożenie bijekcji), a więc \(\displaystyle{ g'\in\mathbb{B} _{Y_1,Y_2}.}\)
I otrzymujemy, że funkcja:
\(\displaystyle{ \alpha :\mathbb{B}_X \rightarrow \mathbb{B} _{Y_1, Y_2}}\) jest dobrze określona.
Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest bijekcją.
Wykażemy, że \(\displaystyle{ \alpha}\) jest funkcją różnowartościową.
Jeśli \(\displaystyle{ \alpha \left( g_1\right)= \alpha \left( g_2\right)}\), to, z definicji tej funkcji \(\displaystyle{ \alpha,}\) oznacza, że:
\(\displaystyle{ f_2\circ g_1\circ f_1= f_2\circ g_2\circ f_1}\), ponieważ funkcje \(\displaystyle{ f_2, f_1}\) są bijekcjami, więc relacje odwrotne \(\displaystyle{ f_2 ^{-1}}\) i \(\displaystyle{ f_1 ^{-1}}\) są również bijekcjami. I wtedy:
czyli \(\displaystyle{ g_1=g_2}\), i funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.
Wykażemy teraz, że funkcja \(\displaystyle{ \alpha}\) jest funkcją 'na'.
Niech \(\displaystyle{ f\in \mathbb{B} _{Y_1,Y_2}.}\) Wtedy \(\displaystyle{ f:Y_1 \rightarrow Y_2}\) i funkcja \(\displaystyle{ f}\) jest bijekcją.
Zdefiniujmy:
\(\displaystyle{ g= f _{2} ^{-1}\circ f\circ f_{1} ^{-1}.}\)
Wtedy \(\displaystyle{ g:X \rightarrow X}\), i ponieważ również relacje odwrotne \(\displaystyle{ f_1 ^{-1}}\) i \(\displaystyle{ f_2 ^{-1}}\) są bijekcjami, to \(\displaystyle{ g}\) jest bijekcją (jako złożenie bijekcji). A zatem \(\displaystyle{ g\in \mathbb{B}_X}\). I wtedy:
czyli \(\displaystyle{ \alpha (g)= f}\), a więc funkcja \(\displaystyle{ f}\) jest wartością funkcji \(\displaystyle{ \alpha }\). Z dowolności wyboru tej funkcji otrzymujemy, że funkcja \(\displaystyle{ \alpha}\) jest funcją 'na'.
co kończy dowód tego lematu.\(\displaystyle{ \square}\)
Przejdźmy do naszego problemu:
Niech \(\displaystyle{ X}\) będzie zbiorem równolicznym z \(\displaystyle{ \NN}\). Rozważmy rodzinę dobrych porządków \(\displaystyle{ \mathbb{B}}\), daną jako:
\(\displaystyle{ \mathbb{B}= \left\{ \le \Bigl| \ \ \le \hbox{ jest dobrym porządkiem na } X\right\}.}\)
I pytamy o moc rodziny \(\displaystyle{ \mathbb{B}.}\)
Wykażemy, że jest to rodzina mocy continuum.
DOWÓD TEGO FAKTU:
Łatwo, z przyczyn formalnych, łatwo jest pokazać, że ta rodzina \(\displaystyle{ \mathbb{B} }\) ma moc co najwyżej continuum, gdyż:
jeśli \(\displaystyle{ \left( \le \right)\in \mathbb{B}}\), wtedy \(\displaystyle{ \le}\) jest dobrym porządkiem na \(\displaystyle{ X}\), a więc \(\displaystyle{ \le}\) jest relacją porządku na \(\displaystyle{ X}\), w szczególności jest relacją w zbiorze \(\displaystyle{ X}\), a więc
a więc \(\displaystyle{ \mathbb{B}\subset P(X \times X) \sim P(\NN)\sim \RR.}\)
a więc \(\displaystyle{ \left| \mathbb{B}\right| \le \left| \RR\right|.}\)
Aby pokazać nierówność mocy w drugą stronę, to niech:
\(\displaystyle{ \mathbb{A}= \left\{ f:\NN \rightarrow \NN\Bigl| \ f \hbox{ jest bijekcją }\right\} \sim \RR,}\)
(przypominam bijekcji na zbiorze liczb naturalnych jest continuum- to się uzasadnia, w taki ciekawy sposób, że dla dowolnego ciągu zerojedynkowego \(\displaystyle{ f}\) definiuje się bijekcję na \(\displaystyle{ \NN}\), w taki sposób, że jeśli \(\displaystyle{ f(n)=1}\), to liczby \(\displaystyle{ 2n}\) i \(\displaystyle{ 2n+1}\) zamieniamy miejscami, a jeśli \(\displaystyle{ f(n)= 0}\) to zostawiamy je w naturalnym porządku, i uzasadniamy, że jest to przekształcenie różnowartościowe; a z drugiej strony wszystkich funkcji z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\) jest continuum, a więc tych bijekcji jest continuum).
A zatem, na mocy Lematu 1, rodzina:
\(\displaystyle{ \mathbb{B} _{\NN, X}:= \left\{ f:\NN \rightarrow X\Bigl| \ f \hbox{ jest bijekcją}\right\},}\)
jest równoliczna z rodziną \(\displaystyle{ \mathbb{A}}\), a więc jest mocy continuum.
Definiujemy teraz funkcję:
\(\displaystyle{ \alpha :\mathbb{B} _{\NN, X} \rightarrow \mathbb{B}}\), w następujący sposób:
Jeśli \(\displaystyle{ f:\NN \rightarrow X}\) jest bijekcją, to definiujemy porządek \(\displaystyle{ \le}\) na \(\displaystyle{ X}\), jako:
\(\displaystyle{ f(0)< f(1)<f(2) < \ldots}\)
otrzymując liniowy porządek na \(\displaystyle{ X}\), i jest to porządek podobny do zwykłego porządku \(\displaystyle{ \le _{\NN}}\) na \(\displaystyle{ \NN}\).
Ponieważ \(\displaystyle{ \le _{\NN}}\) jest dobrym porządkiem, więc również porządek doń podobny \(\displaystyle{ \le}\) jest dobrym porządkiem na \(\displaystyle{ X}\), i \(\displaystyle{ \left( \le \right) \in \mathbb{B}}\), i w ten sposób otrzymujemy funkcję:
Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa:
DOWÓD TEGO FAKTU::
Weźmy dwie różne funkcje \(\displaystyle{ f_1, f_2 \in \mathbb{B} _{\NN,X}.}\) I pokażmy, że również przypisane odpowiednio im porządki \(\displaystyle{ \le _1}\) i \(\displaystyle{ \le _2}\) są różne.
Wtedy \(\displaystyle{ f_1,f_2:\NN \rightarrow X}\), a ponieważ \(\displaystyle{ f_1 \neq f_2}\), a a więc dla pewnego \(\displaystyle{ n\in\NN}\): \(\displaystyle{ f_1(n) \neq f_2(n).}\) Niech \(\displaystyle{ n\in \NN}\) będzie najmniejszą taką liczba naturalną gdzie funkcję \(\displaystyle{ f_1}\) i \(\displaystyle{ f_2}\) różnią się co do wartości.
Jeśli \(\displaystyle{ n=0}\), wtedy \(\displaystyle{ f _{1} (0) \neq f_2\left( 0\right)}\). Łatwo zauważyć, że wtedy element \(\displaystyle{ f_1\left( 0\right)}\) jest elementem najmniejszym \(\displaystyle{ X}\) względem \(\displaystyle{ \le _{1}}\), i podobnie element \(\displaystyle{ f_2 \left( 0\right) }\) jest elementem najmniejszym \(\displaystyle{ X}\) względem \(\displaystyle{ \le _2}\). Ponieważ porządki \(\displaystyle{ \le _1}\) i \(\displaystyle{ \le _2}\) mają różne elementy najmniejsze, a zatem są różne, czyli \(\displaystyle{ \left( \le _{1} \right) \neq \left( \le _{2} \right).}\)
A jeśli \(\displaystyle{ n>0}\), wtedy \(\displaystyle{ \left( n-1\right)\in\NN}\). Ponieważ \(\displaystyle{ n}\) jest najmniejszym numerem gdzie: \(\displaystyle{ f_1\left( n\right) \neq f_2(n)}\), a więc \(\displaystyle{ f_1\left( n-1\right) = f_2(n-1). }\)
Wtedy element \(\displaystyle{ f_1(n)}\) jest następnikiem elementu \(\displaystyle{ f_1(n-1)}\), i podobnie element \(\displaystyle{ f_2(n)}\) jest następnikiem elementu \(\displaystyle{ f_2\left(n-1 \right)}\). Przypuśćmy nie wprost, że \(\displaystyle{ \left( \le _{1}\right) =\left( \le _{2} \right)}\), oznaczmy ten porządek jako \(\displaystyle{ \le}\) . Oznaczmy \(\displaystyle{ f_1\left( n-1\right)= f_2\left( n-1\right) =: x _{n-1}}\), a zatem ponieważ mamy ten sam porządek i ten sam element \(\displaystyle{ x _{n-1} }\), więc również tylko jeden jego następnik, czyli:
i funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa. \(\displaystyle{ \square }\)
A zatem \(\displaystyle{ \left| \RR\right| =\left| \mathbb{B} _{\NN,X} \right|\le \left| \mathbb{B}\right| }\). A zatem, na mocy twierdzenia Cantora-Bernsteina:
czyli istnieje dokładnie continuum dobrych porządków na zbiorze przeliczalnym\(\displaystyle{ .\square}\)
Rozważmy jeszcze dwa zbiory \(\displaystyle{ X}\) i \(\displaystyle{ Y}\), i funkcję \(\displaystyle{ f:X \rightarrow Y}\), i rozważmy dwa podzbiory dziedziny funkcji \(\displaystyle{ A,B\subset X}\). Wykażemy, że obraz różnicy symetrycznej tych dwóch podzbiorów jest nadzbiorem różnicy symetrycznej obrazów tych dwóch zbiorów tzn.:
Jest to o tyle zaskakujące, że dobre porządki na zbiorze przeliczalnym mogą być bardzo długie( chyba mogą sięgać, o krok wcześniej, od najmniejszej liczby nieprzeliczalnej,
Nie ma czegoś takiego jak "o krok wcześniej od najmniejszej liczby nieprzeliczalnej" z tej prostej przyczyny, że \(\displaystyle{ \aleph_1}\) jest graniczną liczbą porządkową.
