
\documentclass{amsart}

\usepackage{amssymb} 

\title{21-300 F15 HW 3}

\begin{document}

\maketitle



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

\begin{enumerate}

\item  Recall that the {\em deductive closure} of a set $\Gamma$ of propositional formulae
     is $\{ \delta: \Gamma \vdash \delta \}$. A set is {\em deductively closed} if and only
     if it is equal to its own deductive closure.  Use the Soundness and Completeness
     theorems to give a short proof that for any $\Gamma$ the deductive closure 
     of $\Gamma$ is deductively closed (if your proof uses induction or is more than ten
     lines long then it is probably too long)

\item Prove that no finite consistent set of propositional formulae is complete.

\item Let $\Gamma$ be a set of propositional formulae. Prove that if every finite
    subset of $\Gamma$ is consistent, then $\Gamma$ is consistent.

\item Two formulae of propositional logic are {\em equivalent} if they are satisfied by exactly the
   same truth assignments. 

\begin{enumerate}
\item  Prove that every propositional formula is equivalent to one which only uses $\neg$ and $\wedge$.
\item  Prove that not every propositional formula is equivalent to one which only uses $\rightarrow$.
\end{enumerate}

\item  Consider a signature for a first order language which has only three symbols, a binary function
    symbol $\circ$, a constant symbol $e$, and a binary relation symbol $\equiv$ (whose intended 
   interpretation is the equlaity relation).  Write down sentences which express:
\begin{enumerate}
\item  $\circ$ is commutative. 
\item  $\circ$ is associative.
\item  $e$ is a two-sided identity element for $\circ$.
\end{enumerate}




\end{enumerate}

\end{document} 



