\begin{frame}{Complement}
  \begin{alertblock}{}
    There exist recursively enumerable languages $L$, for which the complement
    $\overline{L}$ is \alert{not} recursively enumerable.
  \end{alertblock}
  \pause
  
  \begin{proof}{}
    Let $M_1, M_2, M_3, \ldots$ be a recursive enumeration of all TMs.
    \pause\medskip 
    
    Define the language $L$ by
    \begin{talign}
      L = \{\, a^i\mid a^i\in L(M_i),i\geq 1 \,\}
    \end{talign}
    \pause
    Then $L$ is recursively enumerable.
    \pause\smallskip
    
    If $\overline{L}$ was recursively enumerable\pause:
    \structure{$\overline{L} = L(M_k)$} for some $k\geq 1$.
    \pause\smallskip
    
    Then 
    \begin{talign}
      a^k \in \overline{L} \;\;\text{\structure{$\iff$}}\;\; a^k \in L(M_k) \mpause[1]{ \;\;\text{\alert{$\iff$}}\;\; a^k\in L }
    \end{talign}
    \pause\pause
    \alert{Contradiction}. Hence $\overline{L}$ is not recursively enumerable.
  \end{proof}
  \pause
  
  \begin{goal}{}
    $L_1 \setminus L_2$ is not always recursively enumerable since $\overline{L} = \Sigma^* \setminus L$.
  \end{goal}
\end{frame}