Teoria mocy zbiorów

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
a4karo
Użytkownik
Użytkownik
Posty: 20202
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 23 razy
Pomógł: 3429 razy

Re: Teoria mocy zbiorów

Post autor: a4karo » 5 maja 2022, o 20:18

Jan Kraszewski pisze:
5 maja 2022, o 18:06
Uch...

Ł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 :twisted:

Jakub Gurak
Użytkownik
Użytkownik
Posty: 996
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 33 razy
Pomógł: 62 razy

Re: Teoria mocy zbiorów

Post autor: Jakub Gurak » 6 maja 2022, o 01:04

Mam teraz pytanie, może ktoś pomoże:

Ile jest bijekcji z \(\displaystyle{ \RR}\) do \(\displaystyle{ \RR}\) :?:

Myślę, że potrafię uzasadnić, że jest ich co najmniej continuum.
PRÓBA DOWODU::    
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ś???

Jan Kraszewski
Administrator
Administrator
Posty: 30368
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4861 razy

Re: Teoria mocy zbiorów

Post autor: Jan Kraszewski » 6 maja 2022, o 01:38

Jakub Gurak pisze:
6 maja 2022, o 01:04
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.

JK

a4karo
Użytkownik
Użytkownik
Posty: 20202
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 23 razy
Pomógł: 3429 razy

Re: Teoria mocy zbiorów

Post autor: a4karo » 6 maja 2022, o 06:55

Da się to nawet prostym wzorkiem napisać: dla dowolnego `A\subset [0,\infty)`, funkcja `f(x)=(2\chi_A(|x|)-1)x` jest bijekcją.

Dodano po 2 minutach 54 sekundach:
PS wiem, że Janusz Tracz napisze, że to nie funkcja lecz ewaluacja i będzie miał rację :)

Jan Kraszewski
Administrator
Administrator
Posty: 30368
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4861 razy

Re: Teoria mocy zbiorów

Post autor: Jan Kraszewski » 6 maja 2022, o 10:58

To nie funkcja, tylko wzór funkcji (ale to nie rozwiązanie, tylko wskazówka, więc jest OK) :) .

JK

Jakub Gurak
Użytkownik
Użytkownik
Posty: 996
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 33 razy
Pomógł: 62 razy

Re: Teoria mocy zbiorów

Post autor: Jakub Gurak » 6 maja 2022, o 23:42

Jan Kraszewski pisze:
6 maja 2022, o 01:38
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 :?:

Jan Kraszewski
Administrator
Administrator
Posty: 30368
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4861 razy

Re: Teoria mocy zbiorów

Post autor: Jan Kraszewski » 6 maja 2022, o 23:47

Jakub Gurak pisze:
6 maja 2022, o 23:42
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 :?:
Tak, o to chodzi.

JK

Jakub Gurak
Użytkownik
Użytkownik
Posty: 996
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 33 razy
Pomógł: 62 razy

Re: Teoria mocy zbiorów

Post autor: Jakub Gurak » 9 maja 2022, o 20:38

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:

\(\displaystyle{ f_2 ^{-1} \circ\left( f_2\circ g_1\circ f_1\right) \circ f_1 ^{-1} = f_2 ^{-1} \circ \left( f_2\circ g_2\circ f_1\right) \circ f_1 ^{-1} }\), czyli (z łączności złożenia funkcji) otrzymujemy:

\(\displaystyle{ \left( f_2 ^{-1}\circ f_2 \right) \circ g_1\circ \left( f_1\circ f_1 ^{-1} \right) = \left( f_2 ^{-1}\circ f_2 \right) \circ g_2\circ \left( f_1\circ f_1 ^{-1} \right)}\), i ponieważ funkcje \(\displaystyle{ f_2}\) i \(\displaystyle{ f_1}\) są bijekcjami, a więc:

\(\displaystyle{ I_X\circ g_1\circ I_X= g_1= I_X\circ g_2\circ I_X= g_2}\),

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:

\(\displaystyle{ \alpha \left( g\right) = g'=f_2\circ g\circ f_1=f_2\circ \left( f_2 ^{-1}\circ f\circ f_1 ^{-1} \right) \circ f_1= \left( f_2\circ f_2 ^{-1} \right)\circ f\circ \left( f_1 ^{-1}\circ f_1 \right)=f,}\)

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'.

A zatem:

\(\displaystyle{ \mathbb{B}_X\sim \mathbb{B} _{Y_1,Y_2}}\),

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

\(\displaystyle{ \left( \le \right) \subset X \times X\stackrel{X\sim \NN} {\sim} \NN \times \NN\sim \NN}\),

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ę:

\(\displaystyle{ \alpha :f\in \mathbb{B} _{\NN,X} \rightarrow \left( \le \right) \in \mathbb{B}.}\)

Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa:
DOWÓD TEGO FAKTU::    
A zatem \(\displaystyle{ \left| \RR\right| =\left| \mathbb{B} _{\NN,X} \right|\le \left| \mathbb{B}\right| }\). A zatem, na mocy twierdzenia Cantora-Bernsteina:

\(\displaystyle{ \left| \mathbb{B}\right| =\left| \RR\right|}\),

czyli istnieje dokładnie continuum dobrych porządków na zbiorze przeliczalnym\(\displaystyle{ .\square}\) :D 8-)


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.:

\(\displaystyle{ \stackrel{ \rightarrow }{f} \left( A\oplus B\right)\supset \stackrel { \rightarrow } {f} \left( A\right) \oplus \stackrel { \rightarrow }{f}(B).}\)

DOWÓD TEGO FAKTU:

Mamy:

\(\displaystyle{ \stackrel{ \rightarrow }{f}\left( A\oplus B\right) =\stackrel{ \rightarrow }{f}\left( \left( A \setminus B\right) \cup \left( B\setminus A \right) \right) =\underbrace{ \stackrel{ \rightarrow }{f} \left( A \setminus B\right) }_{\supset \stackrel { \rightarrow } {f} \left( A\right) \setminus \stackrel { \rightarrow } {f} \left( B\right) } \cup \underbrace{ \stackrel{ \rightarrow }{f} \left( B \setminus A\right) }_{\supset \stackrel { \rightarrow } {f} \left( B\right) \setminus \stackrel { \rightarrow } {f} \left( A\right) } \supset \left( \stackrel { \rightarrow } {f} \left( A\right) \setminus \stackrel { \rightarrow } {f} \left( B\right) \right) \cup \left( \stackrel { \rightarrow } {f} \left( B\right) \setminus \stackrel { \rightarrow } {f} \left( A\right)\right) =\stackrel { \rightarrow } {f} \left( A\right) \oplus \stackrel { \rightarrow }{f}(B).\square }\) :D

Jan Kraszewski
Administrator
Administrator
Posty: 30368
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4861 razy

Re: Teoria mocy zbiorów

Post autor: Jan Kraszewski » 9 maja 2022, o 21:19

Jakub Gurak pisze:
9 maja 2022, o 20:38
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ą.

JK

ODPOWIEDZ