\documentclass{amsart}

\usepackage{amssymb} 

\title{21-300 F15 HW 2}

\begin{document}

\maketitle


   Since it's harder to word-process proofs, you may submit hand-written solutions 
   to this homework subject to the following conditions: your homework is written
   in black ink on alternating lines, and is submitted as a legible 600dpi scan in
   PDF form. 

   Note: When I say ``prove'' in this homework I mean produce a formal proof using
   the nine proof rules from class. Unless I specify hypotheses, your proof should 
   have no hypotheses. Letters from the Greek alphabet ($\alpha$, $\beta$, $\gamma$, $\delta$)
   stand for arbitrary formulae.

   IMPORTANT: PLEASE EMAIL COMPLETED HOMEWORKS TO:
\begin{verbatim}
   lserafin.algebra@gmail.com
\end{verbatim}

\begin{enumerate}

\item  Prove the formulae:

\begin{enumerate}

\item  $(\alpha \rightarrow \beta) \rightarrow ( (\neg \alpha) \vee \beta)$.

\item  $( (\neg \alpha) \vee \beta) \rightarrow (\alpha \rightarrow \beta)$. 

\item  $(\alpha \rightarrow \beta) \rightarrow ( (\neg \beta) \rightarrow (\neg\alpha))$. 

\item  $((\neg \beta) \rightarrow (\neg\alpha)) \rightarrow  (\alpha \rightarrow \beta)$ 

\end{enumerate} 

\item  Prove the following formulae without using the Contradiction rule (that is the last rule from class, that lets
    you take a proof with conclusion $\neg \neg \beta$ and make a proof with the same hypotheses and conclusion $\beta$).

\begin{enumerate}

\item $\neg \beta \rightarrow \neg \neg \neg \beta$.

\item $\neg \neg \neg \beta \rightarrow \neg \beta$. 

\end{enumerate} 


\item  Prove the formula $\beta \vee \gamma$ from the hypotheses $\alpha \vee \beta$, $\neg \alpha \vee \gamma$.
 
\item  A consistent theory $\Gamma$ is said to be {\em maximally consistent} if there no consistent
   $\Delta$ with $\Gamma \subsetneq \Delta$. Prove that a maximally consistent theory is deductively closed.   
   Hint: Suppose it isn't, what would be a natural thing to try adding? 

\end{enumerate}

\end{document} 



