Zbiory nieprzeliczalne
: 5 paź 2019, o 02:56
Chciałbym zebrać tu parę ogólnych własności zbiorów nieprzeliczalnych. Po pierwsze, zbiór równoliczny ze zbiorem nieprzeliczalnym jest nieprzeliczalny. Nadzbiór zbioru nieprzeliczalnego jest nieprzeliczalny( gdyż podzbiór zbioru co najwyżej przeliczalnego jest co najwyżej przeliczalny). Jeszcze jeden fakt: zbiór większej lub równej mocy niż zbiór nieprzeliczalny jest nieprzeliczalny. Dowód jest odrobinę trudniejszy niż poprzednie fakty:
Dowód:
Niech \(\displaystyle{ X}\) będzie zbiorem nieprzeliczalnym. A \(\displaystyle{ Y}\) zbiorem takim, że \(\displaystyle{ \left| X\right| \le \left| Y\right|.}\) Pokażemy, że zbiór \(\displaystyle{ Y}\) jest nieprzeliczalny. Przypuśćmy, że tak nie jest. Wtedy \(\displaystyle{ Y}\) jest co najwyżej przeliczalny. Z nierówności mocy mamy funkcję różnowartościową \(\displaystyle{ f:X \rightarrow Y.}\) Funkcja \(\displaystyle{ f}\) jest różnowartościowa i 'na' zbiór wartości \(\displaystyle{ f_P}\), zatem jest bijekcją między \(\displaystyle{ X}\) a \(\displaystyle{ f_P}\), i te zbiory są równoliczne. Ponieważ \(\displaystyle{ f_P \subset Y}\), który to zbiór \(\displaystyle{ Y}\) jest co najwyżej przeliczalny, więc również \(\displaystyle{ f_P}\) jest co najwyżej przeliczalny, i \(\displaystyle{ X}\) jest co najwyżej przeliczalny. Otrzymujemy więc sprzeczność, która kończy dowód.\(\displaystyle{ \square}\)
Kolejne dwa fakty mówią, że zbiory nieprzeliczalne są odporne na dodawanie zbiorów co najwyżej przeliczalnych, i odporne na ujmowanie zbiorów co najwyżej przeliczalnych. Po takich operacjach(dodaniu zbioru do sumy lub odjęciu zbioru jako różnicy) moc zbioru pozostaje taka jaka była. Tzn.
1.Jeśli \(\displaystyle{ A}\) jest dowolnym zbiorem nieprzeliczalnym, a \(\displaystyle{ B}\) dowolnym zbiorem co najwyżej przeliczalnym, to \(\displaystyle{ A \setminus B\sim A.}\)
oraz
2. Jeśli \(\displaystyle{ A}\) jest dowolnym zbiorem nieprzeliczalnym, a \(\displaystyle{ B}\) dowolnym zbiorem co najwyżej przeliczalnym, to \(\displaystyle{ A \cup B\sim A.}\)
Dowód 1. tu
Dowód 2. Załóżmy najpierw, że zbiory \(\displaystyle{ A,B}\) są rozłączne. Zbiór \(\displaystyle{ A}\) jest nieprzeliczalny, a więc nieskończony. Możemy zatem odnaleźć w nim nieskończony zbiór przeliczalny \(\displaystyle{ C\subset A}\). Ponieważ \(\displaystyle{ B}\) jest co najwyżej przeliczalny, więc \(\displaystyle{ C \cup B}\) jest przeliczalny. Również \(\displaystyle{ C}\) jest przeliczalny, zatem istnieje bijekcja \(\displaystyle{ f:C \cup B \rightarrow C}\). Ustalmy ją. Niech \(\displaystyle{ g}\) będzie funkcją identyczności na \(\displaystyle{ A\setminus C}\), która jest bijekcją. Zatem \(\displaystyle{ h=f \cup g }\) jako suma bijekcji na rozłącznych dziedzinach (\(\displaystyle{ C \cup B}\) i \(\displaystyle{ A \setminus C}\)) i mających rozłączne zbiory wartości jest bijekcją z \(\displaystyle{ \left( C \cup B\right) \cup \left( A\setminus C\right)=A \cup B }\), w \(\displaystyle{ C \cup \left( A\setminus C\right)=A }\), a więc \(\displaystyle{ A \cup B\sim A.}\)
Jeśli zbiory \(\displaystyle{ A,B}\) nie są rozłączne, to jednak zbiory \(\displaystyle{ A}\) i \(\displaystyle{ B \setminus A}\) są rozłączne , i \(\displaystyle{ B \setminus A}\) jako podzbiór zbioru co najwyżej przeliczalnego \(\displaystyle{ B}\) jest co najwyżej przeliczalny, możemy zatem zastosować udowodnioną część do zbiorów rozłącznych dostając, że \(\displaystyle{ A \cup \left( B \setminus A\right) \sim A }\), czyli \(\displaystyle{ A \cup B\sim A.\square }\)
Można też trochę podobnie uzasadnić, że jeśli \(\displaystyle{ X}\) jest zbiorem nieskończonym, a \(\displaystyle{ a}\) ustalonym elementem, to \(\displaystyle{ X \cup \left\{ a\right\}\sim X.}\) Znowu trzeba w \(\displaystyle{ X}\) odnaleźć nieskończony zbiór przeliczalny \(\displaystyle{ Y\subset X}\), a następnie bijekcję \(\displaystyle{ f:\NN \rightarrow Y}\), i rozważyć funkcję \(\displaystyle{ g:X \cup \left\{ a\right\} \rightarrow X,}\) która elementowi \(\displaystyle{ a}\) przypisuje element \(\displaystyle{ f(0)}\),\(\displaystyle{ f(0)}\) przesuwa na \(\displaystyle{ f(1)}\), \(\displaystyle{ f(1)}\) na \(\displaystyle{ f(2)}\), itd., a na elementach \(\displaystyle{ X \setminus Y}\) jest identycznością, taka funkcja jest bijekcją, a więc \(\displaystyle{ X \cup \left\{ a\right\}\sim X.}\)
Natomiast już fakt, że jeśli \(\displaystyle{ X}\) jest zbiorem nieskończonym, \(\displaystyle{ a\in X}\), to \(\displaystyle{ X \setminus \left\{ a\right\}}\) jest równoliczny z \(\displaystyle{ X}\), czyli wyrzucając jeden element ze zbioru nieskończonego otrzymamy zbiór tej samej mocy, dowód tego jest natychmiastowym wnioskiem z poprzedniego.
Jeśli bowiem \(\displaystyle{ X}\) jest nieskończony, to \(\displaystyle{ X \setminus \left\{ a\right\} }\) jest nieskończony( bo gdy dodamy do zbioru skończonego jeden element to otrzymamy nadal zbiór skończony),więc \(\displaystyle{ X \setminus \left\{ a\right\} }\) jest nieskończony, więc stosując poprzedni fakt otrzymujemy, że \(\displaystyle{ X=X \setminus \left\{ a\right\} \cup \left\{ a\right\}\sim X \setminus \left\{ a\right\}.}\)
Dowód:
Niech \(\displaystyle{ X}\) będzie zbiorem nieprzeliczalnym. A \(\displaystyle{ Y}\) zbiorem takim, że \(\displaystyle{ \left| X\right| \le \left| Y\right|.}\) Pokażemy, że zbiór \(\displaystyle{ Y}\) jest nieprzeliczalny. Przypuśćmy, że tak nie jest. Wtedy \(\displaystyle{ Y}\) jest co najwyżej przeliczalny. Z nierówności mocy mamy funkcję różnowartościową \(\displaystyle{ f:X \rightarrow Y.}\) Funkcja \(\displaystyle{ f}\) jest różnowartościowa i 'na' zbiór wartości \(\displaystyle{ f_P}\), zatem jest bijekcją między \(\displaystyle{ X}\) a \(\displaystyle{ f_P}\), i te zbiory są równoliczne. Ponieważ \(\displaystyle{ f_P \subset Y}\), który to zbiór \(\displaystyle{ Y}\) jest co najwyżej przeliczalny, więc również \(\displaystyle{ f_P}\) jest co najwyżej przeliczalny, i \(\displaystyle{ X}\) jest co najwyżej przeliczalny. Otrzymujemy więc sprzeczność, która kończy dowód.\(\displaystyle{ \square}\)
Kolejne dwa fakty mówią, że zbiory nieprzeliczalne są odporne na dodawanie zbiorów co najwyżej przeliczalnych, i odporne na ujmowanie zbiorów co najwyżej przeliczalnych. Po takich operacjach(dodaniu zbioru do sumy lub odjęciu zbioru jako różnicy) moc zbioru pozostaje taka jaka była. Tzn.
1.Jeśli \(\displaystyle{ A}\) jest dowolnym zbiorem nieprzeliczalnym, a \(\displaystyle{ B}\) dowolnym zbiorem co najwyżej przeliczalnym, to \(\displaystyle{ A \setminus B\sim A.}\)
oraz
2. Jeśli \(\displaystyle{ A}\) jest dowolnym zbiorem nieprzeliczalnym, a \(\displaystyle{ B}\) dowolnym zbiorem co najwyżej przeliczalnym, to \(\displaystyle{ A \cup B\sim A.}\)
Dowód 1. tu
Dowód 2. Załóżmy najpierw, że zbiory \(\displaystyle{ A,B}\) są rozłączne. Zbiór \(\displaystyle{ A}\) jest nieprzeliczalny, a więc nieskończony. Możemy zatem odnaleźć w nim nieskończony zbiór przeliczalny \(\displaystyle{ C\subset A}\). Ponieważ \(\displaystyle{ B}\) jest co najwyżej przeliczalny, więc \(\displaystyle{ C \cup B}\) jest przeliczalny. Również \(\displaystyle{ C}\) jest przeliczalny, zatem istnieje bijekcja \(\displaystyle{ f:C \cup B \rightarrow C}\). Ustalmy ją. Niech \(\displaystyle{ g}\) będzie funkcją identyczności na \(\displaystyle{ A\setminus C}\), która jest bijekcją. Zatem \(\displaystyle{ h=f \cup g }\) jako suma bijekcji na rozłącznych dziedzinach (\(\displaystyle{ C \cup B}\) i \(\displaystyle{ A \setminus C}\)) i mających rozłączne zbiory wartości jest bijekcją z \(\displaystyle{ \left( C \cup B\right) \cup \left( A\setminus C\right)=A \cup B }\), w \(\displaystyle{ C \cup \left( A\setminus C\right)=A }\), a więc \(\displaystyle{ A \cup B\sim A.}\)
Jeśli zbiory \(\displaystyle{ A,B}\) nie są rozłączne, to jednak zbiory \(\displaystyle{ A}\) i \(\displaystyle{ B \setminus A}\) są rozłączne , i \(\displaystyle{ B \setminus A}\) jako podzbiór zbioru co najwyżej przeliczalnego \(\displaystyle{ B}\) jest co najwyżej przeliczalny, możemy zatem zastosować udowodnioną część do zbiorów rozłącznych dostając, że \(\displaystyle{ A \cup \left( B \setminus A\right) \sim A }\), czyli \(\displaystyle{ A \cup B\sim A.\square }\)
Można też trochę podobnie uzasadnić, że jeśli \(\displaystyle{ X}\) jest zbiorem nieskończonym, a \(\displaystyle{ a}\) ustalonym elementem, to \(\displaystyle{ X \cup \left\{ a\right\}\sim X.}\) Znowu trzeba w \(\displaystyle{ X}\) odnaleźć nieskończony zbiór przeliczalny \(\displaystyle{ Y\subset X}\), a następnie bijekcję \(\displaystyle{ f:\NN \rightarrow Y}\), i rozważyć funkcję \(\displaystyle{ g:X \cup \left\{ a\right\} \rightarrow X,}\) która elementowi \(\displaystyle{ a}\) przypisuje element \(\displaystyle{ f(0)}\),\(\displaystyle{ f(0)}\) przesuwa na \(\displaystyle{ f(1)}\), \(\displaystyle{ f(1)}\) na \(\displaystyle{ f(2)}\), itd., a na elementach \(\displaystyle{ X \setminus Y}\) jest identycznością, taka funkcja jest bijekcją, a więc \(\displaystyle{ X \cup \left\{ a\right\}\sim X.}\)
Natomiast już fakt, że jeśli \(\displaystyle{ X}\) jest zbiorem nieskończonym, \(\displaystyle{ a\in X}\), to \(\displaystyle{ X \setminus \left\{ a\right\}}\) jest równoliczny z \(\displaystyle{ X}\), czyli wyrzucając jeden element ze zbioru nieskończonego otrzymamy zbiór tej samej mocy, dowód tego jest natychmiastowym wnioskiem z poprzedniego.
Jeśli bowiem \(\displaystyle{ X}\) jest nieskończony, to \(\displaystyle{ X \setminus \left\{ a\right\} }\) jest nieskończony( bo gdy dodamy do zbioru skończonego jeden element to otrzymamy nadal zbiór skończony),więc \(\displaystyle{ X \setminus \left\{ a\right\} }\) jest nieskończony, więc stosując poprzedni fakt otrzymujemy, że \(\displaystyle{ X=X \setminus \left\{ a\right\} \cup \left\{ a\right\}\sim X \setminus \left\{ a\right\}.}\)