\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

\newcommand{\baexp}{\text{BAexp}}

\newcommand{\ms}[1]{\mathop{\text{#1}}}

\providecommand{\ide}{\ms{id}}
\providecommand{\EF}{\ms{F18}}
\providecommand{\T}{\ms{ST}}

\newcommand{\deriv}{\frac{d}{dx}}
\renewcommand{\paren}[1]{\left(#1\right)}


\begin{document} 
\paper{qu4}{}{Quiz, Week~4}

\begin{problem}
\bparts

\problempart What are the maxim\emph{al} and minim\emph{al} elements, if
any, of the set, $\naturals$, of all nonnegative integers under
divisibility?  Is there a minim\emph{um} or maxim\emph{um} element?

\solution[\vspace{1in}]{The minimum (and therefore unique
minimal) element is 1 since 1 divides all natural numbers. The maximum
(and therefore unique maximal) element is 0 since all numbers divide 0.}

\problempart What are the minimal and maximal elements, if any, of the set
of integers $\ge 2$ under divisibility?

\solution[\vspace{1in}]{All prime numbers are minimal elements, since no
numbers divide them.

There is no maximal element, because for any $n\ge 2$, there is  a
``larger'' number under the divisibility partial order, namely,
$mn$, for any $m > 1$.}


\iffalse
\ppart
What is the size of the longest chain that is guaranteed to exist in any
partially ordered set of $n$ elements?  What about the largest antichain?

\solution{
Chain size is 1 in the ``discrete'' partial order in which every two
distinct elements are incomparable.  Antichain size is 1 if the partial
order is total.
}
\fi

\ppart Describe an infinite chain and an infinite antichain in the
divisibility partial order on the nonnegative integers.

\solution[\vspace{1in}]{ $1, 2, 2^2, 2^3,\dots$ is an infinite chain; the
primes are an infinite antichain.}

\ppart Describe a partially ordered set (i.e., describe a set and then 
a partial order on this set) that has no minimal or maximal elements.

\solution[\vspace{1in}]{$\integers$, $\reals$, etc.}

\iffalse

\ppart Describe a partially ordered set that has a \emph{unique}
minim\emph{al} element, but no minim\emph{um} element. \hint It will have
to be infinite.

\solution{
$\integers \union{i}$ where $i$ is a root of $-1$, under the usual order
$\integers$.  So $i$ is incomparable to everything but itself, and is
therefore minimal.
}
\fi

\eparts
\end{problem}

\iffalse
\begin{problem}
Notes 2 contains a proof by induction that:
%
\[
1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}.
\]
Give a proof of this theorem using the well-ordering principle. 
\end{problem}
\fi

\instatements{\newpage}

\begin{problem}
Consider two integers, $a$ and $b$.  We define the set, $L$, recursively,
as follows: 
\begin{itemize}
\item 
\textbf{Base case:} $0\in L$.
\item 
\textbf{Constructor cases:} if $x\in L$, then
\begin{itemize}
\item[$\bullet$] $x+a\in L$,
\item[$\bullet$] $x-a\in L$,
\item[$\bullet$] $x+b\in L$,
\item[$\bullet$] $x-b\in L$.
\end{itemize}
\end{itemize}
Use structural induction to prove that all members of $L$ are integer
linear combinations of $a$ and $b$.  In other words, prove that
\[
\text{for every $x\in L$: }\quad 
x = sa + tb
\;\text{ for some integer coefficients $s$ and $t$.}
\]
\end{problem}

\instatements{\newpage}
\section*{Appendix}

\subsection*{Arithmetic}

If $m$ and $n$ are nonnegative integers, we say  
$m$ divides $n$ if $km=n$
for some nonnegative integer $k$.

\subsection*{Relational Properties}
A binary relation, $R$, on a set, $A$, is
\begin{itemize}

\item \emph{transitive} if for every $a,b,c\in A$, $aR b$ and
    $bR c$ implies $aR c$.

\item \emph{asymmetric} if for every $a,b\in A$, $aR b$ implies 
    $\neg(bR a)$,

\item \emph{reflexive} if $a R a$ for every $a \in A$,

\item \emph{antisymmetric} if for every $a \neq b\in A$, $aR b$ implies 
    $\neg(bR a)$,

\item \emph{irreflexive} if $a R a$ holds for no $a \in A$.

\end{itemize}


\subsection*{Partial Orders}

A binary relation is a \emph{strict partial order} iff it is transitive
and asymmetric.  It is a \emph{weak partial order} iff it is transitive,
reflexive, and antisymmetric.

Let $\preceq$ be a weak (reflexive) partial order on a set, $A$.
\begin{itemize}

\item An element $a \in A$ is \emph{minimal} iff there is no element in
$A$ that is $\preceq a$ except possibly $a$ itself.  Similarly, an element
$a \in A$ is \emph{maximal} iff there is no element in $A$ that is
$\succeq a$ except possibly $a$ itself.

\item An element $a \in A$ is a \emph{lower bound} for a subset, $S
\subseteq A$ iff $a \preceq s$ for every $s \in S$.  Similarly, an element
$a \in A$ is an \emph{upper bound} for a subset, $S \subseteq A$ iff $s
\preceq a$ for every $s \in S$.

\item An element $a \in A$ is the \emph{minimum} element iff $a$ is a
lower bound on $A$.  Similarly, an element $a \in A$ is the \emph{maximum}
element iff $a$ is an upper bound on $A$.

\item Elements $a,b \in A$ are \emph{comparable} iff either $a \preceq b$
or $b \preceq a$.  Two elements are \emph{incomparable} iff they are not
comparable.

\item A subset, $S \subseteq A$ is \emph{totally ordered} iff every
two distinct elements in $S$ are comparable.

\item A \emph{chain} is a totally ordered subset of $A$.  

\item An \emph{antichain} is a subset of $A$, such that no two elements in
it are comparable.

\iffalse
\item An element $a \in A$ is the \emph{greatest lower bound (glb)} of a
subset, $S \subseteq A$ iff $a$ is a lower bound for $S$, and if $b \in A$
is also a lower bound for $S$, then $b \preceq a$.  Similarly for
\emph{least upper bound (lub)}.
\fi

\end{itemize}



\end{document} 
