Kantor-Bernsteins sats

Cantor-Bernstein-satsen (i den engelska litteraturen Cantor-Bernstein-Schroeder-satsen ), säger att om det finns injektiva mappningar och mellan mängderna och , så finns det en en-till-en-mappning . Med andra ord, att uppsättningarnas kardinaliteter och sammanfaller: $f:A\till B$ $g:B\to A$ $A$ $B$ $h:A\to B$ $A$ $B$

|A|=|B|.

Med andra ord, satsen säger följande:

Det följer av och att var är kardinalnummer . ${\mathfrak {a}}\leqslant {\mathfrak {b}}$ ${\mathfrak {b}}\leqslant {\mathfrak {a}}$ ${\mathfrak {a}}={\mathfrak {b}},$ ${\mathfrak {a)],{\mathfrak {b))$

Historik

Teoremet är uppkallat efter Georg Cantor , Felix Bernstein och Ernst Schröder .

Det ursprungliga beviset använde valets axiom , men detta axiom är inte nödvändigt för att bevisa detta teorem.

Ernst Schröder var den första som formulerade satsen, men publicerade ett felaktigt bevis. Denna sats formulerades självständigt av Cantor. Kantors elev Felix Bernstein publicerade en avhandling innehållande ett helt korrekt bevis.

Bevis

Låta

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

och

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

på

n\geqslant 0

och

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

Sedan för alla vi lägger $x\i A$

h(x)=\left\{{\begin{matrix}f(x)&\,\,{\mbox{if }}x\in C\\g^{-1}(x)& {\mbox{if }}x\inte \i C\end{matrix}}\right.

Om den inte ligger i , måste den vara i (bilden av uppsättningen under åtgärden av mappningen ). Och så finns det , och kartläggningen. $x$ $C$ $x$ $g(B)$ $B$ $g$ $g^{-1}(x)$ $h$

Det återstår att verifiera att det är en bijektion. $h:A\to B$

Låt oss kontrollera att h är en operation.

Det måste vi bevisa $\forall y\in B\exists x\in A:h(x)=y$
$\forall y\in B$

$\mathrm {I} \ \ \$ Om , då . Sedan $y\in f(C)$ $\exists x\in Cf(x)=y$ $h(x)=f(x)=y$

$\mathrm {II} \;y\notin f(C)$
Låt . Låt oss anta . Då , för , betyder , eftersom är en injektion, vilket motsäger antagandet. Så . Sedan $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 \} }\Höger pil$ $g$ $y=f(c)\in f(C)$
$x\notin C$ $h(x)=g^{-1}(x)=g^{-1}(g(y))=y$

Låt oss kontrollera att h är en injektion.

Det måste vi bevisa $h(x_{1})=h(x_{2})\Högerpil x_{1}=x_{2}$

$\mathrm {I} \;x_{1},x_{2}\in C$
$f(x_{1})=f(x_{2})\Högerpil x_{1}=x_{2}$ ( - injektion) $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}\in 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}))\in C$ . Så det här fallet är omöjligt.

Notera

Mappningsdefinitionen ovan är icke-konstruktiv , det vill säga det finns ingen algoritm för att i ett ändligt antal steg bestämma om något element i mängden ligger i mängden eller inte. Även om det finns en sådan algoritm för vissa speciella fall. $h$ $x$ $A$ $C$

Se även

Litteratur

N.K. Vereshchagin, A. Shen. Föreläsningar om matematisk logik och teori om algoritmer. Del 1. Början av mängdlära.

Ershov Yu. L., Palyutin E. A. Matematisk logik: Lärobok. - 3:a, stereotyp. ed. - St Petersburg: "Lan", 2004. - 336 s.