\documentstyle[12pt,twoside,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{3}{March 3, 1995}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Problem 1
\problem 
Let $n$ be a natural number greater than $2$. Define relation $R$ on 
$\integers$ by
\[a \, R \, b \; \iff \;  n \mbox{ divides } a-b. \]
 
\bparts

\ppart $R$ is an equivalence relation.
\begin{proof}
\begin{enumerate}
\item	{\bf reflexivity:} $a \, R \, a $ because $n$ divides $a-a=0$ 
	for any $a$ (since $0n=0$).
\item 	{\bf symmetry:}	If $a \, R \, b $, then $n \mid (a-b)$; that 
	is, $a-b = kn$ for some integer $k$. Therefore, $n \mid
	(b-a)$ since $b-a = -kn$. Therefore $b \, R \, a$.
\item	{\bf transitivity:} If $a \, R \, b $ and $b \, R \, c $,
	then, $a-b = k_1 n$ and $b-c = k_2 n$ for $k_1, k_2\in\integers$.
	 So $n \mid (a-c)$, since $a-c = (a-b)+(b-c) = (k_1+k_2)n$. 
	Therefore $a \, R \, c$.
\end{enumerate}
\end{proof}

\ppart There are total $n$ equivalence classes, namely
\[ 
\{ kn \mid k\in\integers\}, \quad \{ kn +1 \mid k\in\integers\}, \quad \cdots
\quad \{ kn + (n-1) \mid k\in\integers\}
\]
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Problem 2
\problem 

The following relation $\prec$ defines a partial order on 
$\{2,3,4, \cdots, 100 \}$:
\[
a \, \prec \, b \; \iff \; a \mbox{  divides  } b. 
\]
%\mbox{  iff }   where $a, b \in 

\bparts
\ppart 
The minimal elements are all the primes between $2$ and $100$.
The maximal elements are all the numbers between $51$ and $100$.
\ppart One longest chain is $\{ 2, \, 4, \, 8, \, 16, \, 32, \, 64 \}$
(there are others of length~6).
\ppart 
The partition 
\[
\{2,3 \} \, \{4,5,6\} \, \{ 7, \cdots, 12\} \, \{13, \cdots, 25 \}
\, \{26, \cdots, 50 \} \, \{51, \cdots, 100 \}
\] 
is an antichain cover of size 6.
Clearly we cannot have an antichain cover of size less than 6 since each
the elements of the chain $\{ 2, \, 4, \, 8, \, 16, \, 32, \, 64 \}$
must be put in a different antichain.
\eparts

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Problem 3
\problem \mbox{}\nopagebreak\newline\nopagebreak
\begin{defin}
A partial ordering $\preceq$ of a set $X$ is an {\em extension\/}
of a partial ordering $\leq$ if 
\[
x\leq y \implies x\preceq y
\]
for all $x,y\in X$, 
\end{defin}
In other words, thinking of the relations $\preceq$ and $\leq$ as
subsets of $X\times X$, we have $\leq \; \subseteq \; \preceq$.

\thm
Any partial ordering of a finite set 
can be extended to a total ordering of that set.
\ethm

\begin{proof}
By induction on the size of the set. 
In the base case, we have a set of size 1, which by itself is trivially 
a total order.

Now assume that any partial ordering on a finite
set of size $n$ can be extended to a total ordering on that set. 
Consider a partial ordering $\leq$ on set $X$ of size $n+1$. 
Let $m$ be a maximal element of the poset (one must exist; why?).  
Now $\leq$ induces a partial ordering of $X \setminus \{m\}$ in the 
obvious way.
By our inductive hypothesis, we can extend 
this partial ordering on $X\setminus\{m\}$
to a total ordering $\preceq$ on $X\setminus\{m\}$.
To obtain the desired total ordering of $X$, simply put $m$ at the
top of the chain given by $\preceq$ on $X\setminus\{m\}$
(that is, make $m$ greater than every other element of~$X$).

Clearly, this is a total ordering.
It is an extension of $\leq$ because the ordering for elements 
in $X\setminus \{m\}$ is preserved according to our inductive hypothesis, 
and since $m$ had no elements above it, orderings with respect to $m$ 
are also preserved.  Formally, if $x\leq m$ then $x\preceq m$ and 
if $x\leq y$, $y\neq m$ ($x\neq m$ because $m$ is maximal), 
then $x\preceq y$ because by the inductive hypothesis
$\preceq$ is an extension of the partial ordering on $X\setminus \{m\}$
induced by $\leq$.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Problem 4
\problem 

Let $\prec$ be a partial ordering. Define $R$ by 
$ b \, R \, a \;  \iff  \; a \prec b$.

$R$ is also a partial ordering.

\begin{proof}
\bparts
\ppart	{\bf reflexivity:}  $a \prec a$ since $\prec$  is reflexive, 
 so $a \, R \,a$.
\ppart	{\bf antisymmetry:} If $ a \, R \,b$  and $b \, R \, a$, then
	by definition of $R$, $b \prec a$ and $a \prec b$. Since $\prec$ is 
	antisymmetric, we have $b=a$ as desired.
\ppart {\bf transitivity:} If $ a \, R \,b$  and $b \, R \, c$, then
	by definition of $R$, $b \prec a$ and $c \prec b$. Since $\prec$ is
	transitive, we have $ c \prec a $, which implies $a \, R \,c$.
\eparts
\end{proof}

Notice that the partial order $R$ is simply the partial order $\prec$
``upside-down''.

\end{problems}

\end{document}

