\documentclass[twoside,a4paper,12pt,draft]{article}
\usepackage{amssymb,amsmath,amsthm}
\title{Model-theory homework}
\date{2001, fall}
\author{Math 736---David Pierce}
\pagestyle{myheadings}
 \markboth{Model-theory homework}{Math 736, fall 2001}
\theoremstyle{definition}
\newtheorem{problem}{Problem}


\newcommand{\Z}{\mathbf Z}          % the integers
\newcommand{\Q}{\mathbf Q}          % the rationals
%\newcommand{\A}{\mathbf A}          % affine space
\newcommand{\R}{\mathbf R}          % the reals
\newcommand{\N}{\mathbf{N}}         % the naturals
\newcommand{\C}{\mathbf{C}}         % the complex numbers
\newcommand{\F}{\mathbf{F}}         % (finite) field

\newcommand{\id}{\mathrm{id}}       % identity-function

\newcommand{\unit}[1]{{#1}^{\times}} % group of units of a ring

\newcommand{\stroke}{\mathrel{|}}   % stroke for semi-group example

\newcommand{\str}[1]{\mathcal{#1}}  % structure with universe #1

%I don't like the standard loose inequalities
\renewcommand{\leq}{\leqslant}
\renewcommand{\nleq}{\nleqslant}
\renewcommand{\geq}{\geqslant}

%I don't much like the standard here either:
\renewcommand{\setminus}{-}

%I don't want epsilon to look like `is an element of'
\renewcommand{\epsilon}{\varepsilon}

\newcommand{\To}{\longrightarrow}

\newcommand{\mapset}[2]{#2^{#1}}

\newcommand{\Mod}{\mathfrak{Mod}}
\DeclareMathOperator{\Th}{Th}
\newcommand{\pow}{\mathcal{P}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\arity}[1]{\textrm{arity}(#1)}
\newcommand{\proj}{\pi}
\newcommand{\inv}{^{-1}}
\newcommand{\Fm}[1]{\textrm{Fm}^{#1}}
\newcommand{\Fmo}[1]{\textrm{Fm}^{#1}_0}
\newcommand{\2}{\mathbf{F}_2}

\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\elsub}{\preccurlyeq}
\newcommand{\Ba}{\mathcal{M}^\mathrm{a}}  % a Boolean algebra
\newcommand{\Br}{\mathcal{M}^\mathrm{r}}  % a Boolean ring

\DeclareMathOperator{\diag}{diag}   % Robinson diagram of a structure

\DeclareMathOperator{\sgn}{sgn}     % signum of a permutation

\newcommand{\included}{\subseteq}   % the name suggests the meaning here
\newcommand{\lang}{\mathcal L}      % a language
\newcommand{\SL}{\mathrm{PL}}       % Propositional (was sentential) logic
\newcommand{\pairing}[1]{\langle#1\rangle} % pairing

\newtheorem*{theorem}{Theorem}
\newtheorem*{lemma}{Lemma}
\newtheorem*{corollary}{Corollary}

\theoremstyle{remark}
\newtheorem*{remark}{Remark}
\newtheorem*{example}{Example}
\newtheorem*{examples}{Examples}

%  For distinguishing claims made and proved within proofs
%\newtheoremstyle{subclaim}{0pt}{0pt}{\itshape}{}{\bfseries}{}{0em}{}
%\theoremstyle{subclaim}
%\newtheorem*{claim}{}

\newcommand{\tuple}{\mathbf}
\newcommand{\reduct}{\overline}

%  Should the word `modulo' be italicized?
\newcommand{\modulo}{\emph{modulo}\ }

%  To distinguish terms being defined
\newcommand{\defn}[1]{{\bf#1}}

\begin{document}
%\maketitle
\thispagestyle{empty}

\noindent\emph{Some homework for Math 736, Model-Theory, given \today.}

Let $\lang$ be a signature, and let $\str M$ be a structure in
$\Mod(\lang)$.

\begin{problem}
We didn't actually \emph{define} terms of $\lang$; we simply asserted
that terms $t$ exist whose interpretations $t^{\str M}$ have certain
properties.  Prove this assertion.
\end{problem}

\begin{problem}
Prove the lemma that, if $t$ is an $n$-ary term of $\lang$, and $u_0$,
\dots, $u_{n-1}$ are $m$-ary terms of $\lang$, then there is an $m$-ary
term of $\lang$ whose interpretation in ${\str M}$ is the map
\begin{equation*}
\tuple a\mapsto t^{\str M}(u_0^{\str M}(\tuple a),\dots,u_{n-1}^{\str
M}(\tuple a)):M^m\to M.
\end{equation*}
\end{problem}

\begin{problem}
Suppose that a structure in the signature $\{\land,\lor,\lnot,0,1\}$ can
be expanded to a signature containing $+$ in such a way that
  the identities
  $x\lor y  ={x+y}+(x\land y)$ and
  $\lnot x  =x+1$
are satisfied; suppose further that this expansion, reduced to the
signature $\{+,\land,0,1\}$, is a Boolean ring.  Then the original
structure is, by definition, a Boolean algebra.
\begin{enumerate}
  \item
  Prove that the Boolean algebras are precisely those structures\\
  $(B, \land, \lor, \lnot, 0, 1)$ whose reducts $(B,\land,1)$ and $(B,\lor,0)$ are
  monoids, and that
  satisfy the equations $\lnot\lnot x =x$, and $\lnot(x\land y) =\lnot x\land\lnot
  y$, and also
\begin{align*}
  x\land y&=y\land x, & x\lor y&=y\lor x, \\
  x\land(y\lor z)&=(x\land y)\lor(x\land z),
         & x\lor(y\land z)&=(x\lor y)\land(x\lor z),\\
  x\land \lnot x&=0 & x\lor\lnot x&=1\\
  x\land 0 &=0 & x\lor 1&=1.
\end{align*}
  \item
  Find a structure $(C,+,\land,\curlyvee,\lnot,0,1)$ that satisfies
  \begin{equation*}
  x+y =(x\land\lnot y)\curlyvee(y\land\lnot x),
  \end{equation*}
  and whose reduct $(C,+,\land,0,1)$ is a Boolean ring, but whose reduct
  $(C,\land,\curlyvee,\lnot,0,1)$ is \emph{not} a Boolean algebra.
\end{enumerate}
\end{problem}
\begin{problem}
Prove that the map $x\mapsto[x]$ from a Boolean algebra to the power-set
of its Stone-space is an embedding of Boolean algebras.
\end{problem}
\end{document}