Ha létezik f : A --> B injekció, és létezik g: B --> A injekció, akkor létezik h: A --> B bijekció?

Az állítás igaz. Bizonyítását lsd . az alábbi jegyzet 10. oldalán (5. tétel, ekvivalenciatétel):

[link]

Igen, ez az állítás igaz, de nem egészen triviális. Cantor-Schröder-Bernstein tétel a neve: [link] .

A bizonyítás nagy vonalakban: legyen f: A->B injekció és g:B->A injekció. Ha A_0 tetszőleges részhalmaza A-nak, akkor legyen B_0=f[A_0] (tehát minden olyan B-beli elem, ami előáll egy A_0-beli elem képeként az f függvénynél), B_1=B-B_0 (B-ben a maradék B-0-n kívül), A_1=g[B_1] (azon A-beli elemek, amik g-vel előállnak B_1 beli elem képeként) és A_2 = A-g[B_1] = A-g[B-f[A-0]] (az A-nak azon elemei, amik nem állnak elő B_1-beli elem képeként a g függvény által). Ha A_0=A_2 lenne, akkor lenne egy bijekciónk, hiszen akkor A_0 és B_0 között f adja meg a bijekciót, A_1 és B_1 között pedig a g, és ezek ekkor pont olyan halmazok lennének, hogy diszjunktak és uniójuk A, illetve B. Tehát legyen F: P(A)->P(A) (ahol P(A) az A hatványhalmaza, tehát összes részhalmazának a halmaza), F(X)=A-g[B-f[X]]. (Vagyis ez a függvény A minden részhalmazára megcsinálja azt amit az előbb csináltunk). Ekkor az előbbiek szerint olyan X részhalmaz kéne nekünk, amire F(X)=X.

Erre az F függvényre könnyen ellenőrizhető, hogy ha X részhalmaza Y-nak, akkor F(X) is részhalmaza F(Y)-nak (ha gondolod leírom, de amúgy nem nehéz látni miért).

Vegyük azt az X halmazt, amit úgy kapunk, hogy minden olyan Y részhalmazt összemetszünk, amire F(Y) részhalmaza Y-nak. (Ez nem üres metszet, mert A ilyen például). De ha F(Y) részhalmaza Y-nak, akkor mivel X minden ilyennek a metszete, akkor X részhalmaza Y-nak, és így az F tulajdonsága miatt F(X) részhalmaza F(Y)-nak, de F(Y) részhalmaza Y-nak, vagyis F(X) részhalmaza Y-nak. De ez minden olyan Y-ra igaz, amire F(Y) részhalmaza Y-nak, de így F(X) részhalmaza minden ilyennek, ezért részhalmaza a metszetüknek, ami X, vagyis F(X) részhalmaza X-nek. De így F(F(X)) részhalmaza F(X)-nek, de így F(X) egyike az Y-oknak, hiszen igaz rá az Y-okra jellemző tulajdonság. Így az Y-ok metszete részhalmaza F(X)-nek, de az Y-ok metszete X, vagyis X részhalmaza F(X)-nek, de az előbb azt is láttuk, hogy F(X) részhalmaza X-nek, és így F(X)=X, és ezért ez az X halmaz olyan amit kerestünk (ezt választhatjuk A_0-nak).