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
![:)](./images/smilies/icon_smile.gif)
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\}.}\)