Relacja równoważności

[Augustyn Kaczmarek]

Dana jest następująca relacja równoważności \(\displaystyle{ r \subseteq P(\mathbb{N}) ^{2}}\):
\(\displaystyle{ P \ r \ Q}\) wtedy i tylko wtedy, gdy \(\displaystyle{ P = Q = \emptyset}\) lub
\(\displaystyle{ P, Q \neq \emptyset}\) i \(\displaystyle{ \min\ P = \min\ Q}\).

Jakiej mocy jest zbiór ilorazowy \(\displaystyle{ P(\mathbb{N})/_r}\)? Jakie są moce poszczególnych klas abstrakcji?

[Jan Kraszewski]

Jedną klasę abstrakcji powinieneś bez problemu zidentyfikować (co daje częściową odpowiedź na jedno z pytań...).

Żeby odpowiedzieć na te pytania trzeba zrozumieć, jak wyglądają klasy abstrakcji tej relacji. Jak nie masz innego pomysłu, to weź jakiś prosty zbiór i postaraj się wyznaczyć jego klasę abstrakcji - już sama taka próba pozwala sporo zobaczyć.

JK

[Augustyn Kaczmarek]

Mam taką odpowiedź na pierwsze pytanie. Czy jest poprawne?
Zbiór ilorazowy \(\displaystyle{ P(\mathbb{N})/_r}\) jest zbiorem wszystkich klas równoważności modulo \(\displaystyle{ r}\). Każda klasa zawiera podzbiory \(\displaystyle{ \mathbb{N}}\), które mają identyczne elementy minimalne. Klas równoważności jest tyle, ile jest możliwych elementów minimalnych (czyli liczb naturalnych). Zatem moc \(\displaystyle{ P(\mathbb{N})/_r}\) wynosi \(\displaystyle{ \aleph_{0}}\). Dla pewności trzeba jeszcze bijekcja pokazująca, że \(\displaystyle{ P(\mathbb{N})/_r}\) jest policzalna:
Definiujemy klasy równoważności jako \(\displaystyle{ [n]:= \{S \in P(\mathbb{N}) : \mathrm{min}(S) = n \}}\). I jest też klasa \(\displaystyle{ [\emptyset] = \{ \emptyset \}}\). Teraz \(\displaystyle{ P(\mathbb{N})/_r = \{[n]:n \in \mathbb{N} \} \cup \{ [\emptyset] \} = \{ [\emptyset],[0 ],[1],[2],... \}.}\) Definiujemy bijekcję \(\displaystyle{ f:P(\mathbb{N})/_r \longrightarrow \mathbb{N}}\) następująco: \(\displaystyle{ f([\emptyset])=0}\) i \(\displaystyle{ f([n])=n+1}\). Możemy zauważyć, że jest injektywna i surjektywna.

Dodano po 43 minutach 12 sekundach:
Mam coś takiego dla drugiego pytania:
Klasa zawierająca pusty zbiór jest singletonem i większość (jeśli nie wszystkie) innych klas równoważności będzie równoliczna z \(\displaystyle{ P(\mathbb{N})}\), ponieważ są to zbióry potęgowe zbiorów równolicznych z \(\displaystyle{ \mathbb{N}}\).
Scharakteryzujmy klasę równoważności \(\displaystyle{ [n]}\) w taki sposób, żeby ich moc była jasna: \(\displaystyle{ [0]= \{S \in P(\mathbb{N}):0 \in S \}}\) i \(\displaystyle{ [n]= \{ S \in P(\mathbb{N} \backslash \{ 0,1,...,n-1 \}):n \in S \}}\), zatem każdy \(\displaystyle{ [n]}\) jest równoliczny z \(\displaystyle{ P(\mathbb{N})}\), ponieważ on jest zbiorem potęgowym przeliczalnie nieskończonego zbioru, czyli \(\displaystyle{ \mathbb{N}}\) z obciętym początkowym (skończonym) segmentem.

Czy moje odpowiedzi są poprawne? Gdy tak, to czy są dobrze udowondione (być może coś należy dodać?)?

[Jan Kraszewski]

Zbiór ilorazowy \(\displaystyle{ P(\mathbb{N})/_r}\) jest zbiorem wszystkich klas równoważności modulo \(\displaystyle{ r}\). Każda klasa zawiera podzbiory \(\displaystyle{ \mathbb{N}}\), które mają identyczne elementy minimalne. Klas równoważności jest tyle, ile jest możliwych elementów minimalnych (czyli liczb naturalnych). Zatem moc \(\displaystyle{ P(\mathbb{N})/_r}\) wynosi \(\displaystyle{ \aleph_{0}}\). Dla pewności trzeba jeszcze bijekcja pokazująca, że \(\displaystyle{ P(\mathbb{N})/_r}\) jest policzalna:
Definiujemy klasy równoważności jako \(\displaystyle{ [n]:= \{S \in P(\mathbb{N}) : \mathrm{min}(S) = n \}}\). I jest też klasa \(\displaystyle{ [\emptyset] = \{ \emptyset \}}\). Teraz \(\displaystyle{ P(\mathbb{N})/_r = \{[n]:n \in \mathbb{N} \} \cup \{ [\emptyset] \} = \{ [\emptyset],[0 ],[1],[2],... \}.}\) Definiujemy bijekcję \(\displaystyle{ f:P(\mathbb{N})/_r \longrightarrow \mathbb{N}}\) następująco: \(\displaystyle{ f([\emptyset])=0}\) i \(\displaystyle{ f([n])=n+1}\). Możemy zauważyć, że jest injektywna i surjektywna.

Jak dla mnie OK (bo bardzo dokładnie opisałeś sytuację), ale mogę sobie wyobrazić, że ktoś domaga się dowodu bijektywności tej funkcji...

Klasa zawierająca pusty zbiór jest singletonem i większość (jeśli nie wszystkie) innych klas równoważności będzie równoliczna z \(\displaystyle{ P(\mathbb{N})}\),

No wszystkie - przecież one identycznie powstają.

ponieważ są to zbióry potęgowe zbiorów równolicznych z \(\displaystyle{ \mathbb{N}}\).

To nieprawda jest.

Scharakteryzujmy klasę równoważności \(\displaystyle{ [n]}\) w taki sposób, żeby ich moc była jasna: \(\displaystyle{ [0]= \{S \in P(\mathbb{N}):0 \in S \}}\) i \(\displaystyle{ [n]= \{ S \in P(\mathbb{N} \backslash \{ 0,1,...,n-1 \}):n \in S \}}\), zatem każdy \(\displaystyle{ [n]}\) jest równoliczny z \(\displaystyle{ P(\mathbb{N})}\), ponieważ on jest zbiorem potęgowym przeliczalnie nieskończonego zbioru, czyli \(\displaystyle{ \mathbb{N}}\) z obciętym początkowym (skończonym) segmentem.

Charakteryzacja klas abstrakcji jest poprawna, ale to nie są zbiory potęgowe, więc argument jest niepoprawny. Może lepiej wziąć taką charakteryzację: \(\displaystyle{ [n]=\{\{n\}\cup D: D\in P(\mathbb{N} \setminus \{ 0,1,...,n\})\},}\) wtedy nietrudno uzasadnić, że jest to zbiór równoliczny z \(\displaystyle{ P(\mathbb{N} \setminus \{ 0,1,...,n\}).}\)

JK

[Augustyn Kaczmarek]

Bardzo dziękuję Panu za odpowiedzi.

Charakteryzacja klas abstrakcji jest poprawna, ale to nie są zbiory potęgowe, więc argument jest niepoprawny. Może lepiej wziąć taką charakteryzację: \(\displaystyle{ [n]=\{\{n\}\cup D: D\in P(\mathbb{N} \setminus \{ 0,1,...,n\})\},}\) wtedy nietrudno uzasadnić, że jest to zbiór równoliczny z \(\displaystyle{ P(\mathbb{N} \setminus \{ 0,1,...,n\}).}\)

Dla mnie ta równoliczność jest chyba oczywista i nie wiem tak naprawde, jak to uzasadnić i zapisać

[Jan Kraszewski]

Dla mnie ta równoliczność jest chyba oczywista i nie wiem tak naprawde, jak to uzasadnić i zapisać

Funkcja \(\displaystyle{ F:P(\mathbb{N} \setminus \{ 0,1,...,n\})\to[n], F(D)=\{n\}\cup D}\) jest bijekcją, co przy tym opisie klasy abstrakcji \(\displaystyle{ [n]}\) jest (w razie potrzeby) proste do wykazania.

JK