Is it possible to skip the first line in a theorem environment?

Insert

\leavevmode

after the \begin{exercise}. That puts you into horizontal mode, which is where you want to be when you encounter the \begin{enumerate}.

See theorem or ntheorem package. Here is an example:

\documentclass{article}
\usepackage{theorem} % or ntheorem
\theoremstyle{break}
\newtheorem{exercise}{Exercise}
\begin{document}
\begin{exercise}
\begin{enumerate}
  \item foo
  \item bar
\end{enumerate}
\end{exercise}
\end{document}

It may be a little more complex to do that using amsthm. In amsthm we can define:

\usepackage{amsthm}
\newtheoremstyle{break}{3pt}{3pt}{\itshape}{}{\bfseries}{.}{\newline}{}
\theoremstyle{break}
\newtheorem{exercise}{Exercise}

It works fine without a enumerate environment at the beginning, but will fail for your code. This is a solution:

\begin{exercise}\mbox{}
\begin{enumerate}
  \item foo
  \item bar
\end{enumerate}
\end{exercise}

It seems no elegant solution. Therefore I prefer ntheorem to modify theorem styles.

I believe this is what you are looking for:

\begin{exercise} 
\begin{enumerate} 
\item[]
\item Show that $R$ is symmetric iff $R^{-1}\subseteq R$.
\item Show that $R$ is transitive iff $R\circ R\subseteq R$.
\end{enumerate}