Cantor-Bernsteinin lause

Cantor-Bernstein-lause (englanninkielisessä kirjallisuudessa Cantor-Bernstein-Schroeder-lause ) sanoo, että jos on injektiokuvauksia ja joukkojen ja välillä , niin on olemassa yksi-yhteen-kuvaus . Toisin sanoen, että sarjojen ja sarjojen kardinaalit osuvat yhteen: $f:A\ to B$ $g:B\to A$ $A$ $B$ ${\näyttötyyli h:A\to B}$ $A$ $B$

|A|=|B|.

Toisin sanoen lause sanoo seuraavaa:

Siitä seuraa ja että missä ovat kardinaaliluvut . ${\mathfrak {a}}\leqslant {\mathfrak {b}}$ ${\mathfrak {b}}\leqslant {\mathfrak {a}}$ ${\mathfrak {a}}={\mathfrak {b}},$ ${\mathfrak {a)],{\mathfrak {b))$

Historia

Lause on nimetty Georg Cantorin , Felix Bernsteinin ja Ernst Schröderin mukaan .

Alkuperäisessä todistuksessa käytettiin valinnan aksioomaa , mutta tämä aksiooma ei ole välttämätön tämän lauseen todistukselle.

Ernst Schröder muotoili ensimmäisenä lauseen, mutta julkaisi väärän todisteen. Cantor muotoili tämän lauseen itsenäisesti. Kantorin oppilas Felix Bernstein julkaisi väitöskirjan, joka sisälsi täysin oikean todisteen.

Todiste

Päästää

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

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

klo

n\geqslant 0

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

Sitten mitä tahansa laitamme $x\in A$

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

Jos se ei sijaitse , sen on oltava sisällä (kuva joukosta kartoituksen toiminnon alla ). Ja sitten on olemassa , ja kartoitus. $x$ $C$ $x$ $g(B)$ $B$ $g$ $g^{-1}(x)$ $h$

On vielä tarkistettava, että se on arvaus. ${\näyttötyyli h:A\to B}$

Tarkistetaan, että h on surjektio.

Meidän on todistettava se $\forall y\in B\exists x\in A:h(x)=y$
$\forall y\in B$

$\mathrm {I} \ \ \$ Jos , niin . Sitten $y\in f(C)$ $\exists x\in Cf(x)=y$ $h(x)=f(x)=y$

$\mathrm {II} \;y\notin f(C)$
Anna . Oletetaan . Sitten , for , tarkoittaa , koska on injektio, joka on ristiriidassa oletuksen kanssa. Joten . Sitten ${\näyttötyyli 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 \} }\Rightarrow$ $g$ $y=f(c)\in f(C)$
$x\notin C$ $h(x)=g^{-1}(x)=g^{-1}(g(y))=y$

Tarkastetaan, että h on injektio.

Meidän on todistettava se $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}$ ( -injektio) $f$

$\mathrm {II} \;x_{1},x_{2}\notin C$
$g^{-1}(x_{1})=g^{-1}(x_{2})\Oikea nuoli 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$ . Tämä tapaus on siis mahdoton.

Huomautus

Yllä oleva kartoitusmäärittely on ei-konstruktiivinen , eli ei ole algoritmia sen määrittämiseksi äärellisessä määrässä vaiheita, onko jokin joukon elementti joukossa vai ei. Vaikka joissain erikoistapauksissa tällainen algoritmi on olemassa. $h$ $x$ $A$ $C$

Katso myös

Kirjallisuus

N. K. Vereshchagin, A. Shen. Luentoja matemaattisesta logiikasta ja algoritmien teoriasta. Osa 1. Joukkoteorian alkua.

Ershov Yu. L., Palyutin E. A. Matemaattinen logiikka: Oppikirja. - Kolmas, stereotypia. toim. - Pietari: "Lan", 2004. - 336 s.