Fie
\( D=A\times \{0,1\}=(A\times \{0\})\cup (A\times \{1\}) \). Atunci
\( card D=card A+card A=x+x \).
Notam cu
\( \mathcal{P}^*(A)=\mathcal{P}(A)\setminus \{\emptyset\} \) multimea partilor nevide ale multimii
\( A \). Pentru orice multime nevida
\( X \subseteq A \) notam cu
\( \mathcal{F}(X)=\{f:X \to X \times \{0,1\}:\ f\ \textrm{ este bijectiv\u a} \}. \)
Fie
\( \displaystyle \mathcal{F}=\bigcup_{X\in \mathcal{P}^*(A)}\mathcal{F}(X) \). Multimea
\( A \), fiind infinita, are proprietatea ca exista o submultime a sa numarabila; deci exista
\( h:\mathbb{N} \to A \) injectiva. Atunci multimea
\( E=h(\mathbb{N})\subseteq A \) este numarabila pentru ca
\( h:\mathbb{N} \to E \) este bijectiva si astfel
\( card E=\aleph_0 \). Mai departe avem ca
\( card (E\times \{0,1\})=card ((E\times \{0\})\cup(E \times\{1\}))=card (E\times \{0\}) +card (E \times \{1\})=\aleph_0+\aleph_0=\aleph_0=card E \). Prin urmare exista o functie
\( f:E \to E\times \{0,1\} \) bijectiva. Acest fapt arata ca multimea
\( \mathcal{F} \) este nevida
Sa consideram relatia binara
\( \mathcal{R}=\{(f,g) \in \mathcal F\times \mathcal F:\ g \textrm{ este o prelungire a lui } f\}. \)
(Functia
\( g:Z\to T \) este o prelungire a functiei
\( f:X \to Y \) daca
\( X \subseteq A \) si
\( g(\alpha)=f(\alpha)\ \forall \alpha \in X \))
Sa demonstram ca
\( (\mathcal F,\mathcal R) \) este o multime ordonata (adica
\( \mathcal R \) este o relatie de ordine).
i)
\( (f,f) \in \mathcal R \): Functia
\( f \) este o prelungire a sa pentru ca
\( Dom\ f\subseteq Dom\ f \) si
\( f(x)=f(x)\ \forall x \in Dom\ f \).
ii)
\( (f,g),\ (g,f) \in \mathcal R \Rightarrow f=g \): Avem ca
\( f:M\to N \) si
\( g: P\to Q \). Din faptul ca
\( (f,g),\ (g,f) \in \mathcal R \) rezulta ca
\( M\subseteq P \) si
\( P \subseteq M \), deci
\( M=P \) \c si
\( f(\alpha)=g(\alpha)\ \forall \alpha \in Dom\ f=M=P=Dom\ g \). Prin urmare
\( f=g \).
iii)
\( (f,g),\ (g,h) \in \mathcal R\Rightarrow (f,h) \in \mathcal R \): Avem ca
\( f:F_1 \to F_2,\ g:G_1 \to G_2,\ h:H_1\to H_2 \). Din ipoteza avem ca
\( F_1 \subseteq G_1 \subseteq H_1 \) si
\( h(\alpha)=g(\alpha),\ \forall \alpha \in G_1 \) si
\( g(\alpha)=f(\alpha),\ \forall \alpha \in F_1 \). Fie
\( \alpha \in F_1 \). Avem ca
\( \alpha \in F_1 \subseteq G_1 \). Deci
\( f(\alpha)=g(\alpha)=h(\alpha) \). Adica
\( h \) este o prelungire a lui
\( f \). Prin urmare
\( (f,h) \in \mathcal R \).
Din aceste trei afirmatii rezulta ca
\( \mathcal R \) este o relatie de ordine pe multimea
\( \mathcal F \), adica
\( (\mathcal F,\mathcal R) \) este o multime ordonata.
Fie
\( \mathcal L=(f_\alpha)_{\alpha \in J} \subset \mathcal F \) un lant (adica o multime total ordonata). Evident ca pentru orice
\( \alpha \in J \) functia
\( f_\alpha :X_\alpha \to X_\alpha \times \{0,1\} \) este o functie bijectiva. Mai mult, pentru orice
\( \alpha,\ \beta \in J \) avem ca bijectia
\( f_\alpha:X_\alpha \to X_\alpha \times \{0,1\} \) este o prelungire pentru bijectia
\( f_\beta:X_\beta\to X_\beta\times\{0,1\} \) sau bijectia
\( f_\beta:X_\beta\to X_\beta\times\{0,1\} \) este o prelungire pentru bijectia
\( f_\alpha:X_\alpha \to X_\alpha \times \{0,1\} \).
De aici rezulta ca daca
\( X_0=\displaystyle \bigcup_{\alpha \in J}X_\alpha \), atunci functia
\( f_0:X_0\to X_0\times \{0,1\} \) definita pentru orice
\( y \in X_0 \) prin
\( f_0(y)=f_\alpha(y) \), pentru orice
\( \alpha \in J \) cu proprietatea ca
\( y \in X_\alpha \), este o functie bijectiva.
Sa demonstram, mai intai ca
\( f_0 \) este bine definita. Daca
\( y \in X_\alpha \cap X_\beta \), atunci
\( y \in X_\alpha \subseteq X_\beta \) sau
\( y \in X_\beta \subseteq X_\alpha \). Deci
\( f_\alpha(y)=f_\beta(y) \). Astfel
\( f_0 \) este bine definita.
Fie
\( y,z \in X_0 \) cu
\( f_0(y)=f_0(z) \). Atunci
\( \exists \alpha,\beta \in J \) astfel incat
\( y \in X_\alpha,\ z \in X_\beta \). Cum una din bijectiile
\( f_\alpha:X_\alpha \to X_\alpha \times\{0,1\} \) si
\( f_\beta:X_\beta \to X_\beta\times \{0,1\} \) este o prelungire a celeilalte rezulta ca
\( y,z \in X_\alpha \) sau
\( y,z \in X_\beta \). Daca
\( y,z \in X_\alpha \), atunci
\( f_\alpha:X_\alpha \to X_\alpha \times \{0,1\} \) este bijectiva. Cum
\( f_0(y)=f_0(z) \) rezulta ca
\( f_\alpha(y)=f_\alpha(z) \) din care rezulta ca
\( y=z \). Analog pentru
\( y,z \in X_\beta \). Deci, din faptul ca
\( f_0(y)=f_0(z) \), unde
\( y,z \in X_0 \) a rezultat faptul ca
\( y=z \). Astfel functia
\( f_0 \) este injectiva.
Fie
\( (y,\varepsilon) \in X_0\times \{0,1\} \), unde
\( \varepsilon \in \{0,1\} \) \c si
\( y \in X_0 \). Din faptul ca
\( X_0=\displaystyle \bigcup_{\alpha \in J}X_\alpha \) rezulta ca
\( \exists \alpha \in J \) cu
\( y \in X_\alpha \). Cum
\( f_\alpha:X_\alpha \to X_\alpha \times \{0,1\} \) este bijectiva, rezulta ca exista
\( y_\alpha \in X_\alpha \) cu
\( f_\alpha(y_\alpha)=(y,\varepsilon) \). Dar
\( f_0(y_\alpha)=f_\alpha(y_\alpha)=(y,\varepsilon) \) unde
\( y_\alpha \in X_0 \). Am obtinut astfel ca
\( f_0 \) este surjectiva.
Prin urmare,
\( f_0 \) este bijectiva si
\( f_0 \) este o prelungire pentru orice
\( f_\alpha \in \mathcal L \). Deci
\( f_0 \in \mathcal F \) si
\( (f_\alpha,f_0) \in \mathcal R,\ \forall \alpha \in J \). Aceasta arata ca
\( f_0 \) este un majorant pentru
\( \mathcal L \). Cum
\( \mathcal L \) a fost ales arbitrar, am demonstrat astfel ca orice lant admite un majorant. Astfel
\( (\mathcal F,\mathcal R) \) este o multime inductiv ordonata.
Din lema lui
Zorn \( (\mathcal F,\mathcal R) \) are un element maximal
\( f^*:X^* \to X^*\times \{0,1\} \). Aceasta inseamna ca
\( X^* \) este o submultime nevida a lui
\( A \) si ca
\( f^*:X^* \to X^* \times \{0,1\} \) este o functie bijectiva care nu mai poate fi prelungita.
Sa aratam ca multimea
\( Y=A \setminus X^* \) este finita. Prin reducere la absurd presupunem ca
\( Y \) este infinita. Atunci exista o functie injectiva
\( v:\mathbb{N} \to Y \). Rezulta ca
\( H=v(\mathbb{N}) \) si
\( H \times \{0,1\} \) sunt numarabile. Astfel exista o functie bijectiva
\( g^*:H \to H \times \{0,1\} \). Fie
\( f^{**}:X^*\cup H \to (X^*\cup H)\times \{0,1\} \) definita pentru orice
\( y \in X^*\cup H \) prin
\( f^{**}(y)=\left\{\matrix{f^*(y),\ y \in X^* \cr g^*(y),\ y \in H}\right. \)
Atunci
\( f^{**}:X^*\cup H \to (X^*\cup H)\times \{0,1\} \) este o functie bijectiva care apartine lui
\( \mathcal F \) si care prelungeste pe
\( f*:X^* \to X^* \times \{0,1\} \). Aceasta contrazice maximalitatea lui
\( f^*:X^* \to X^*\times\{0,1\} \).
Prin urmare, multimea
\( Y=A\setminus X^{*} \) este multime finita si
\( X^*=A\setminus Y \) este o multime infinita. De aici deducem egalitatea
\( card A=card (X^*\cup Y)=card X^*=card (X^*\times \{0,1\})=card ((X\times \{0\})\cup (X\times \{1\}))=card (X^*\times\{0\})+card (X* \times \{1\})=card X^*+cardX^*=card A+card A \). Prin urmare
\( x+x=x \), unde
\( x=card A \).
Aceasta e solutia pentru prima parte...
Pentru a doua parte, rationamentul este analog, dar se complica un pic lucrurile la sfarsit...