\documentclass{amsart}

\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[slovene]{babel}
\usepackage{times}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage[hidelinks]{hyperref}

\newcommand{\NN}{\mathbb{N}}

\newtheorem*{izrek}{Izrek}

\newenvironment{dokaz}{\textit{Dokaz.}}{\medskip}

\begin{document}

\title{Cantor-Schröder-Bernsteinov izrek}

\maketitle

\begin{izrek}
  Če obstajata injektivni preslikavi $f : A \to B$ in $g : B \to A$, potem
  obstaja bijektivna preslikava $h : A \to B$.
\end{izrek}

\begin{proof}
  Definirajmo družino $C : \NN \to \mathsf{Set}$ takole:\footnote{Za lažje
    razumevanje dokaza si oglejte \url{https://vimeo.com/117221911}.}
  %
  \begin{align*}
    C_0 &= A \setminus g_{*}(B), \\
    C_{n+1} &= g_{*}(f_{*}(C_n).
  \end{align*}
  %
  Naj bo $D = \bigcup_{n \in \NN} C_n$. Očitno je $C_n \subseteq A$ za vse
  $n \in \NN$, zato velja tudi $D \subseteq A$.

  Ker je $g$ injektivna, je bijekcija kot preslikava $g : B \to g_{*}(B)$, zato
  obstaja inverz $g^{-1} : g_{*}(B) \to B$. Trdimo, da velja
  $A \setminus D \subseteq g_{*}(B)$. Res, če velja $x \in A \setminus D$, tedaj
  $x \not\in D$ in zato $x \not\in C_0 = A \setminus g_{*}(B)$, od koder sledi
  $x \in g_{*}(B)$. Od tod sledi, da lahko $g^{-1}$ uporabimo na
  $x \in A \setminus D$.

  Definirajmo $h : A \to B$ s predpisom
  % 
  \begin{equation*}
    h(x) =
    \begin{cases}
      f(x), & \text{če $x \in D$,} \\
      g^{-1}(x) &\text{če $x \in A \setminus D$.}
    \end{cases}
  \end{equation*}
  %
  Dokažimo, da je $h$ injektivna preslikava.
  Denimo, da za $x, y \in A$ velja $h(x) = h(y)$. Obravnavamo štiri primere:
  %
  \begin{enumerate}
  \item Če je $x \in D$ in $y \in D$, potem je $f(x) = h(x) = h(y) = f(y)$ in
    zato $x = y$, saj je~$f$ injektivna.
  \item Če je $x \in A \setminus D$ in $y \in A \setminus D$, potem je
    $g^{-1}(x) = h(x) = h(y) = g^{-1}(y)$ in zato $x = y$, saj je $g^{-1}$
    injektivna.
  \item Če je $x \in D$ in $y \in A \setminus D$, potem je
    $f(x) = h(x) = h(y) = g^{-1}(y)$, zato je $y = g(g^{-1}(y)) = g(f(x))$.
    Obstaja $n \in \NN$, da je $x \in C_n$, od tod pa sledi
    $y = g(f(x)) \in C_{n+1} \subseteq D$, kar je v protislovju z
    $y \in A \setminus D$. Torej se ta primer sploh ne more zgoditi.
  \item Če je $x \in A \setminus D$ in $y \in D$, je razmislek kot v prejšnjem
    primru, le da zamenjamo vlogi~$x$ in~$y$.
  \end{enumerate}

  Preveriti moramo še, da je $h$ surjektivna preslikava. Naj bo $z \in B$.
  Poiskati moramo tak $x \in A$, da velja $h(x) = z$. Obravnavamo dva primera:
  %
  \begin{enumerate}
  \item Če $z \in f_{*}(D)$, potem obstaja $x \in D$, da je $f(x) = y$, s tem pa
    velja tudi $h(x) = f(x) = z$.
  \item Če velja $z \not\in f_{*}(D)$, potem vzamemo $x = g(z)$. Preverimo, da
    velja $h(x) = z$.

    Najprej dokažimo $x \not\in D$. Če bi namreč veljalo $x \in D$, potem bi
    obstajal $n \in \NN$, da je $x \in C_n$. Poleg tega
    $x = g(z) \not\in A \setminus g_{*}(B) = C_0$, zato velja $n > 0$. Se pravi,
    da obstaja $y \in C_{n-1}$, da je $g(z) = x = g(f(y))$. Ker je $g$
    injektivna, sledi $z = f(y)$, kar je v nasprotju z predpostavko
    $z \not\in f_{*}(D)$. Torej res velja $x \not\in D$.

    Ker $x \not\in D$, velja $h(x) = g^{-1}(x) = g^{-1}(g(z)) = z$, kar smo
    želeli dokazati. \qedhere
  \end{enumerate}
\end{proof}

\end{document}
