\begin{frame}{Definability Results for Reachability/Unreachability} \begin{proposition} Let $\sbinpred{R}$ be a binary relation symbol. \begin{enumerate}\setlength{\itemsep}{0.6ex} \pause \item In predicate logic, \emph{reachability} by $\sbinpred{R}$-steps is: \pause \begin{itemize}\vspace*{0.4ex}\setlength{\itemsep}{0.4ex} \item \alert{not definable} by a sentence. \item \alert{not definable} by a set of sentences. \end{itemize} \vspace*{0.75ex} \pause \item In predicate logic, \emph{unreachability} by $\sbinpred{R}$-steps is: \pause \begin{itemize}\vspace*{0.4ex}\setlength{\itemsep}{0.4ex} \item \alert{not definable} by a single sentence. \item \emph{definable} by a set of sentences. \end{itemize} \end{enumerate} \end{proposition} \pause \begin{proof} Similar to definability and undefinability results (see earlier) for finiteness and infiniteness. \end{proof} \end{frame}