\documentstyle[12pt,twoside,amssymb]{article}
\input{macros-course}

\let\comp\circ
\let\union\cup
\let\intersect\cap
\newcommand{\Cal}[1]{{\cal #1}}

\begin{document}

%\problem

Let $A$ be a set.
\bparts

\ppart
Desrcibe the smallest equivalence relation on $A$.

\noindent
Note: if $R$ and $Q$ are binary relations on $A$, $R$ is {\em smaller}
than $Q$ iff $R\subseteq Q$.

\ppart
Let $R$ and $S$ be partial orders on $A$, and $S\comp R$ the
composition of $R$ with $S$ (as defined in the book). Is $S\comp R$ a
partial order on $A$?

\ppart
Let $R$ be a partial order on $A$. Describe the relation $R\comp R$.

\ppart
Let $E$ and $F$ be two equivalence relations on $A$ such that for
every $a\in A$ either $aEb$ implies $aFb$ or $aFb$ implies $aEb$. Show
that $E\union F$ is an equivalence relation on $A$.

\ppart
Assume the set $A$ has $n$ elements, and let $R$ be any relation on
$A$. Prove that the relation
\[
\underbrace{R\comp R\cdots\comp R}_{n-1}
\]
is always transitive.

\ppart
Prove that for any relations $R$, $S$, and $T$ on $A$
\[
(S\union T)\comp R = (S\comp R)\union(T\comp R).
\]

\ppart
Let $R$ be a relation on $\Cal{P}(A)\times\Cal{P}(A)$ defined by
\[
(s_1,s_2)\ R\ (t_1,t_2)\text{ iff }s_1\oplus s_2\subseteq t_1\oplus t_2{.}
\]
Is $R$ a partial order?

\noindent
Note: $\Cal{P}(A)$ denotes the power set of $A$, and $s\oplus t$
denotes the set of all elements in either $s$ or $t$ but not in both.

\ppart
Let $A$ be a set and let $R$, $S$ and $T$ be binary relations on $A$.

\begin{tabular}{l||c|c|c|c|c|c|}
$R$, $S$ and $T$ are... & $R\union S$ & $R\intersect S$ & $R-S$ & $R\comp S$ & $R\oplus S$\\
\hline\hline
reflexive & & & & &\\
\hline
symetric & & & & &\\
\hline
transitive & & & & &\\
\hline
equivalence & & & & &\\
\hline
partial order & & & & &\\
\hline
strict partial order & & & & &\\
\hline
total order & & & & &\\
\end{tabular}

\eparts

\end{document}
