Teorema Cantor-Bernstein

Teorema Cantor-Bernstein (în literatura engleză, teorema Cantor-Bernstein-Schroeder ), afirmă că dacă există mapări injective și între mulțimi și , atunci există o mapare unu-la-unu . Cu alte cuvinte, că cardinalitățile seturilor și coincid: $f:A\la B$ $g:B\la A$ $A$ $B$ $h:A\la B$ $A$ $B$

|A|=|B|.

Cu alte cuvinte, teorema spune următoarele:

Rezultă din și că unde sunt numerele cardinale . ${\mathfrak {a}}\leqslant {\mathfrak {b}}$ ${\mathfrak {b}}\leqslant {\mathfrak {a}}$ ${\mathfrak {a}}={\mathfrak {b}},$ ${\mathfrak {a)], {\mathfrak {b)}$

Istorie

Teorema poartă numele lui Georg Cantor , Felix Bernstein și Ernst Schröder .

Dovada originală a folosit axioma alegerii , totuși această axiomă nu este necesară pentru demonstrarea acestei teoreme.

Ernst Schröder a fost primul care a formulat teorema, dar a publicat o demonstrație incorectă. Această teoremă a fost formulată independent de Cantor. Studentul lui Cantor, Felix Bernstein, a publicat o disertație care conține o dovadă complet corectă.

Dovada

Lăsa

C_{0}=A\setminus g(B),

și

C_{n+1}=g(f(C_{n}))\quad

n\geqslant 0

și

C=\bigcup _{n=0}^{\infty }C_{n}.

Apoi pentru orice punem $x\în A$

h(x)=\left\{{\begin{matrix}f(x)&\,\,{\mbox{if }}x\in C\\g^{-1}(x)& {\mbox{dacă }}x\nu \în C\end{matrice}}\right.

Dacă nu se află în , atunci trebuie să fie în (imaginea setului sub acțiunea mapării ). Și apoi există și maparea. $X$ $C$ $X$ $g(B)$ $B$ $g$ $g^{-1}(x)$ $h$

Rămâne de verificat că este o bijecție. $h:A\la B$

Să verificăm că h este o surjecție.

Trebuie să dovedim asta $\forall y\in B\există x\in A:h(x)=y$
$\forall y\in B$

$\mathrm {I} \ \ \$ Dacă , atunci . Apoi $y\in f(C)$ $\există x\in Cf(x)=y$ $h(x)=f(x)=y$

$\mathrm {II} \;y\notin f(C)$
Lasă . Să presupunem . Atunci , pentru , înseamnă , deoarece este o injecție, ceea ce contrazice presupunerea. Deci . Apoi $x=g(y)$ $x\in C$ $x\in C_{n}$ $n>0$ $x\in g(f(C_{n-1}))$
$\Rightarrow \exists c\in C_{n-1}{\begin{matrix}x=g(f(c))\\x=g(y)\end{matrix}}{\Bigg \} }\Sageata dreapta$ $g$ $y=f(c)\in f(C)$
$x\notin C$ $h(x)=g^{-1}(x)=g^{-1}(g(y))=y$

Să verificăm dacă h este o injecție.

Trebuie să dovedim asta $h(x_{1})=h(x_{2})\Rightarrow x_{1}=x_{2}$

$\mathrm {I} \;x_{1},x_{2}\in C$
$f(x_{1})=f(x_{2})\Rightarrow x_{1}=x_{2}$ ( - injectare) $f$

$\mathrm {II} \;x_{1},x_{2}\notin C$
$g^{-1}(x_{1})=g^{-1}(x_{2})\Rightarrow x_{1}=g(g^{-1}(x_{1})) =g(g^{-1}(x_{2}))=x_{2}$

$\mathrm {III} \;x_{1}\în C,x_{2}\notin C$
$h(x_{1})=f(x_{1}),h(x_{2})=g^{-1}(x_{2})$
$h(x_{1})=h(x_{2})$
$x_{2}=g(h(x_{2}))=g(h(x_{1}))=g(f(x_{1}))\în C$ . Deci acest caz este imposibil.

Notă

Definiția de mapare de mai sus este neconstructivă , adică nu există un algoritm pentru a determina într-un număr finit de pași dacă un element al mulțimii se află sau nu în mulțime . Deși pentru unele cazuri speciale există un astfel de algoritm. $h$ $X$ $A$ $C$

Vezi și

Literatură

N. K. Vereshchagin, A. Shen. Prelegeri despre logica matematica si teoria algoritmilor. Partea 1. Începuturile teoriei mulțimilor.

Ershov Yu. L., Paliutin E. A. Logica matematică: manual. - al treilea, stereotip. ed. - Sankt Petersburg: „Lan”, 2004. - 336 p.