\documentclass[11pt]{article}

\usepackage{hw}

\begin{document}

\dotitle{3}{Thursday, September 28}

\begin{enumerate}

\item
\begin{enumerate}
\item
  Let $x\equiv y$ be an equivalence relation on a set $X$. For any
  element $x\in X$, let $[x]$ denote its equivalence class, defined by
\[
[x]
  = \{ a \in X \; | \; a \equiv x
  \}.
\]
Show that for any $a, b\in X$, one has $a \equiv b$ iff $[a] = [b]$.

\item
  Conclude from problems 2a and 2b on page 21 of van Dalen that the
  equivalence classes of propositional formulas are partially ordered.
\end{enumerate}

\item
\addstar Consider equivalence modulo 5 on the natural
numbers: $m \equiv n$ iff $m - n = 5z$ for some integer $z$.

\begin{itemize}

\item Define addition $\oplus$ on equivalence classes
  by:
\[
[m] \oplus [n] = [m+n].
\]
Show that this operation is well defined: if $m \equiv m'$ and $n
\equiv n'$ then $m + n \equiv m' + n'$.

\item
  Try to define exponentiation $\uparrow$ on equivalence classes by:
\[
[m] \uparrow [n] = [m^n].
\]
Show that exponentiation is {\em not} well-defined.
\end{itemize}


  
\item Use the semantic definitions to prove or find a counterexample
  to each of the following: 
\begin{enumerate} 
\item For every set of
  formulas $\Gamma$, every formula $\ph$, and every formula $\psi$, if
  $\Gamma \models \varphi \land \psi$, then $\Gamma \models \varphi$
  and $\Gamma \models \psi$.  
\item For every set of formulas
  $\Gamma$, every formula $\ph$, and every formula $\psi$, if $\Gamma
  \models \varphi \lor \psi$, then $\Gamma \models \varphi$ or $\Gamma
  \models \psi$.
\end{enumerate}
  
\item Do problem 1 on pages 27 of van Dalen.

\item 
\begin{enumerate}

%\item Do problems 5 and 6 on page 28. In other words, show that
%  ``nand'' and ``nor'' are the only two complete binary connectives.
  
\item Show that $\{ \limplies, \bot \}$ is a complete set of
  connectives.

\item Show that $\{ \limplies, \lor, \land \}$ is not a  complete set of connectives.
  
\item Conclude that $\{ \limplies, \lor, \land, \liff, \top \}$ is not
  a complete set of connectives.  (Hint: define the last
  two in terms of the others.)

%\item Show that $\{ \bot, \liff \}$ is not a complete set of
%  connectives. (Hint: show that any formula involving only these
%  connectives and the variables $p_0$ and $p_1$ is equivalent to one
%  of the following: $\bot$, $\top$, $p_0$, $p_1$, $\lnot p_0$, $\lnot
%  p_1$, $p_0 \liff p_1$, or $p_0 \oplus p_1$.)
%\item Conclude that $\{ \bot, \top, \lnot, \liff, \oplus \}$ is not
%  complete. (Hint: see the previous problem.)
\end{enumerate}

%\item How many ternary (3-ary) complete connectives are there?
  
%\item Do problem 10 on pages 28--29 of van Dalen.
  

\end{enumerate}


\end{document}