\documentclass[12pt]{article}
\usepackage{graphics}\usepackage{amsmath}
\newcommand{\course}{Math 222A}
\newcommand{\quarter}{W03}
\newcommand{\handout}{B}
\newcommand{\hno}{B}
\usepackage{psfig}
\input{/h1/fa/baker/include/preamble}

\input{/h1/fa/baker/include/kcommands.tex}
\begin{document}


\chapter{Partially ordered sets}

\begin{figure}[p]
\renewcommand{\epsfile}{text/adir/all.eps}
\setlength{\unitlength}{.013889in}
\centerline{\input{text/adir/all.picture}}
\caption{Some examples}
\label{all.fig}
\end{figure}

\section{Definitions}

\noindent %(For examples see Figure \ref{all.fig}.)
%
A relation \(  \leq   \) on a set \( P \) is a
{\em partial order relation} if

\noindent \begin{tabular}{lll}
(a)&\( x  \leq   x \)&(reflexivity)\\
(b)&\( x  \leq   y \) and \( y  \leq   x \) imply \( x = y \)&(antisymmetry)\\
(c)&\( x  \leq   y \) and \( y  \leq   z \) imply \( x  \leq   z \)&(transitivity)\\
\end{tabular}

\noindent \( x  \geq   y \) means \( y  \leq   x \); \( x < y \)
means \( x  \leq   y \) and \( x \neq y \);  \( x > y \) means \( y <
x \).

\vspace{12pt}

\noindent \( \langle  P,  \leq    \rangle \) is a {\em partially ordered set} (or
{\em poset} or {\em partly ordered set} or {\em ordered set}) if \(  \leq   \)
is a partial order relation on \( P \).  (Generally we just say,
``the partially ordered set \( P \)''.)  In the following, \(P\) and
\(Q\) refer to partially ordered sets.

\vspace{12pt}

\noindent The relation \(  \leq   \) is a {\em total order relation} on \( P \) if also

\noindent (d)  for all \( x,y \), either \( x  \leq   y \) or \( y  \leq   x \).

\noindent In this case, \( \langle  P,  \leq    \rangle \) is a {\em chain} or
{\em totally ordered set} or {\em linearly ordered set}.  (In contrast,
if instead no two distinct elements are related, then \(P\) is an
{\em antichain}.)

\vspace{12pt}

\noindent In \( P \), \( a \) {\em covers} \( b \) if \( a > b \) and there is
no \( c \) with \( a > c > b \).

\vspace{12pt}

\noindent The {\em Hasse diagram} of a finite partially ordered set \( P \) is
a diagram indicating the elements of \( P \) by circles or dots,
connected by lines that indicate the coverings in \( P \).  (No
lines are drawn horizontal;  a non-horizontal line from \( b \)
up to \( a \) indicates that \( a \) covers \( b \).)

\vspace{12pt}

\noindent A map \(f:P\rightarrow Q\) is said to be {\em isotone} if \(f\) preserves
order:  \(x \leq  y \Rightarrow  f(x) \leq  f(y)\).  It is possible, however, for
an isotone map to take two unrelated elements to two related
elements, or even to the same element.

\noindent A map \(f:P\rightarrow Q\) is said to be an {\em isomorphism} if \(f\) is
one-to-one and onto and both \(f\) and its inverse are isotone.
In this case, \(P\) and \(Q\) are {\em isomorphic}.

\noindent {\em Note.}  The best way to show that two partially ordered sets \(P,Q\)
are isomorphic is to define maps \(f:P\rightarrow Q\) and \(g:Q\rightarrow P\), show
that \(f\) and \(g\) are isotone, and show that \(f\) and \(g\)
are inverse to each other, in the sense that \(g(f(p))=p\) and
\(f(g(q))=q\) for all \(p \in P, q \in Q\).  (It is {\em not} enough to
define \(f\) and show that \(f\) is isotone, one-to-one, and onto.)

\noindent For partially ordered sets \(P\), \(Q\), the
{\em direct product} partial order on the set \(P \times Q\) is the
coordinatewise ordering:  \(\langle p, q \rangle \leq  \langle p', q' \rangle\)
\(\Leftrightarrow \) \(p \leq  p'\) and \(q \leq  q'\).

\noindent The Hasse diagram of \(P \times Q\) can be drawn as a copy of
\(Q\) for each element of \(P\), with \(P\) used as a guide for
the placement of the copies and for the coverings between them.

\noindent A direct product \( P _ 1 \times \dots  \times P _ n\) or \(\prod
_ {i \in I} P _ i\) is defined similarly.

\vspace{12pt}

\section{Dilworth's Theorem}

\ssno {\bf Definition.}  The {\em width} of a partially ordered set \(P\) is
the cardinality of the largest antichain.  (For example, a chain
has width 1.)

\vspace{12pt}

\noindent {\em Observation.}  If \(P\) is the union of \(n\) chains, then \(P\)
has width at most \(n\).

\vspace{12pt}

\ssno {\bf Theorem} (R.\ P.\ Dilworth)  Let \(P\) be a finite partially ordered
set of width \(n\).  Then \(P\) {\em is} a union of \(n\) chains.

\noindent This is a kind of minimax theorem, in that it shows that the maximum
size of an antichain in \(P\) is the minimum number of chains whose union
is \(P\).  There are a number of combinatorial consequences.  Here is one:

  Let \(\rho\) be a binary relation between finite sets
\(A\) and \(B\), i.e., \(\rho \subseteq A \times B\).  A {\em matching}
of \(A\) into \(B\) is a one-to-one function \(f:A\rightarrow B\) such that
for all \(a \in A\), \(a \rho f(a)\).

\vspace{12pt}

\ssno {\bf Corollary} (P.\ Hall's matching theorem)  Given \(\rho\), a necessary
and sufficient condition for the existence of a matching of \(A\) into
\(B\) is that for each \(k=1,2,\dots \),

\noindent (*) any \(k\) elements of \(A\) are related to at least \(k\) elements
of \(B\), in the sense that each of these elements of \(B\) is
related to at least one of the \(k\) elements of \(A\).

\noindent (In the proof, the disjoint union of \(A\) and \(B\) is made into
a partially ordered set by declaring \(a < b\) when \(a \rho b\).)

\vspace{12pt}

\ssno {\bf Definition}
Let \( A _ 1,\dots, A _ n \) be subsets of a finite set.
A {\em system of distinct representatives} (SDR) for the \( A _ i \)
is a set of distinct elements \( a _ 1,\dots, a _ n \) with \( a _ i
\in A _ i \).

\noindent An obvious necessary condition for the existence of an SDR is
(*)  For each \( k  \leq   n \), the union of any \( k \) of the \(
A _ i \) has at least \( k \) elements.

\vspace{12pt}

\ssno {\bf Corollary}\label{SDR.cor} (P.\ Hall's theorem on
distinct representatives) The condition (*) is a necessary
and sufficient condition for the existence of an SDR.

\vspace{12pt}

\noindent Recall that subsets \(A _ 1,\dots, A _ n\) of a set
\(S\) form a {\em partition} of \(S\) if the \(A _ i\) are pairwise
disjoint and have union \(S\).  The \(A _ i\) are called the
{\em blocks} of the partition.

\noindent We say that a partition is an {\em equipartition} if all its blocks
have the same cardinality.

\vspace{12pt}

\ssno {\bf Corollary}\label{SCR.cor} (Equipartition theorem) Two
equipartions of a finite set \(S\), each with the same number of
blocks, have a system of common representatives (SCR)---in other
words, one set of elements that constitutes a system of distinct
representatives for both of the two equipartitions.

\vspace{12pt}

\section{Problems} (not to hand in except as assigned)

\prob (a) Draw a copy of \(\xbm 2 ^ 4\).   (Think of it either as
\(\xbm 2 ^ 2 \times \xbm 2 ^ 2\) or as \(\xbm 2 \times \xbm 2 ^ 3\).)

\noindent (b) Draw  \(\xrm{Subgp} (\xbm Z _ 5 \times \xbm Z _ 5)\), where \(\xbm Z _ 5\)
denotes the integers modulo 5.

\vspace{12pt}

\prob  \label{union} Represent the partially ordered set of
Figure \ref{dilw.fig} as a union of chains, using as few as
possible:

\begin{figure}[htbp]
\renewcommand{\epsfile}{text/adir/dilw.eps}
\setlength{\unitlength}{.013889in}
\centerline{\includegraphics{\epsfile}}
\caption{For Problem 2.}
\label{dilw.fig}
\end{figure}

\vspace{12pt}

\prob Give an example of a map between partially ordered sets that
is isotone, one-to-one, and onto, but not an isomorphism.

\vspace{12pt}

\prob  A {\em quasi-order} on a set \(Q\) is a relation \( \leq  \)
that is reflexive and transitive but not necessarily antisymmetric.
Show that if \(Q\) is a quasi-ordered set, then the relation
\(a \sim b \Leftrightarrow  a\leq  b\) and \(b \leq  a\) defines an equivalence relation
for which the set \(Q/\sim\) becomes a partially ordered set in a
natural way.
% add something about the symmetric-transitive closure of a digraph?

\vspace{12pt}

\prob  Show that every partially ordered set can be
represented by sets.  In other words, show that for each
partially ordered set \(P\) there is a set \(S\) such that \(P\)
can be embedded in \(\xrm {Pow}(S)\).  (Suggestion: Take \(S=P\).
For partially ordered sets \(P\) and \(Q\), a map \(f:P\rightarrow Q\) is
an {\em embedding} if \(f\) is one-to-one and \(p \leq  p' \Leftrightarrow  f(p) \leq 
f(p')\).  In other words, \(f\) is an isomorphism of \(P\) with
a subset of \(Q\).)

\vspace{12pt}

\prob  Show that \(\xrm {Div}(n)\) is isomorphic to a direct
product of chains.

\noindent (For partially ordered sets \(P\) and \(Q\), the direct product
\(P \times Q\) consists of pairs as usual and is partially ordered
coordinatewise.  Thus \(\langle p,q \rangle \leq  \langle
p', q' \rangle \) \( \Leftrightarrow  \) \(p \leq  p' \) and \( q \leq  q'\).)

\vspace{12pt}

\prob  Let \(P\) be a partially ordered set in which every
chain is finite and every antichain is finite.  Show that \(P\)
must be finite.

\vspace{12pt}

\prob Suppose that \(H\) is a subgroup of a finite group
\(G\).  Show that there is a set of \( [G:H] \) elements of \(G\)
that are simultaneously left coset representatives and right
coset representatives for \(H\).

\vspace{12pt}

\prob Show that every countable chain can be embedded in the chain
\(\xbm Q\) of rationals.

\noindent (An embedding of a partially ordered set \(P\)
into a partially ordered set \(Q\) is an isomorphism of \(P\) with
a subset of \(Q\).  In general this is not the same thing as a
one-to-one isotone map of \(P\) into \(Q\), but when \(P\) is a chain
it {\em is} the same thing.)

\vspace{12pt}

\prob A chain is said to be {\em dense} (or {\em dense-in-itself})
if no element covers another, and {\em endless} if it has no top
element and no bottom element.  Show that every two dense,
endless, countably infinite chains are isomorphic.  (Thus all are
isomorphic to the chain \(\xbm Q\) of rationals.)

\vspace{12pt}

\prob  For partially ordered sets \(P,Q\), the ``cardinal power''
\(P ^ Q\) is the set of all isotone functions from \(Q\) into \(P\),
partially ordered pointwise.  In other words, for \(f,g\) isotone,
\(f \leq  g\) means that  \(f(q)\leq g(q)\) for all \(q \in Q\).

\noindent (a)  Draw a diagram of \(\xbm 3 ^ {\xbm 3}\) (a chain to a chain power).

\noindent (b) For \( P ^ Q \) as an ``operation'' on partially ordered
sets, state analogues of these rules of algebra for positive real
numbers.  For each analogue state whether it is true, up to
isomorphism.  (You need not give proofs.)

\noindent (i)  \( (ab) ^  c = a ^ c b ^ c \),

\noindent (ii) \( a ^ {b + c} = a ^ b a ^ c \),

\noindent (iii) \( (a ^ b) ^ c = a ^ {bc} \).

	(The analogue of multiplication will be the direct
product; the analogue of addition of two partially ordered sets
will be to put them side by side, i.e., to form their disjoint union
with no order relations between the two pieces.)

\vspace{12pt}

\prob  Sketch (a) \({\xbm 2} ^ {\xbm 4}\) and (b) \({\xbm 3} ^ {\xbm 4}\) (chains
to chain powers)

\vspace{12pt}

\prob  (This problem concerns chains to chain powers.)

\noindent (a)  Describe \({\xbm 2} ^ {\xbm n}\) more simply, up to isomorphism.

\noindent Use the rules for powers of partially ordered sets
(from a previous problem) to derive the strange result that \( {\xbm 3} ^ {\xbm 4}
\cong  {\xbm 5} ^ {\xbm 2}\). 

\vspace{12pt}

\prob  Let \( {\bf \omega} = \curly {0,1,2,\dots } \), as a chain.  Prove:
For each \( n \), every antichain in \( {\bf \omega} ^ n \) is finite.
(Here \(n\) is not a chain, so \( {\bf \omega} ^ n \) means \({\bf \omega}
\times \dots  \times {\bf \omega}\).)

\vspace{12pt}

\prob  A {\em bipartite graph} is a partially ordered set of
the kind used in Hall's matching theorem, where all elements are
maximal or minimal but not both.  Can you find a bipartite graph
with five minimal elements such that for each \(k\) any \(k\)
minimal elements are together related to at least \(k\) maximal
elements, {\em except} for \(k=3\)?

\vspace{12pt}

\prob Prove P.~Hall's theorem on distinct representatives (Corollary
\ref{SDR.cor}).

\noindent (Suggestion: Use the matching theorem.  But what should be on
the upper level and what on the lower?)

\vspace{12pt}

\prob Prove the theorem on a system of common representatives
for two equipartitions (Corollary \ref{SCR.cor}).

\noindent (Suggestion: Use the matching theorem.)

\vspace{12pt}

\prob  Let \( \xbm Q \) be the set of rational numbers.

\noindent (a)  Show that \( \xbm R \) can be embedded in \( \xrm{Pow} (\xbm Q) \).

\noindent (b)  Show that \( \xbm Q \) has an uncountable family of
subsets whose pairwise intersections are finite.

\vspace{12pt}

\prob If \(W\) is a well ordered set, a {\em limit element} in
\(W\) is an element that does not cover any other element
and is not the least element of \(W\).  Let \(\Lambda(W)\) denote
the set of limit elements of \(W\).  Let \(\Lambda ^ 2 (W) =
\Lambda(\Lambda(W))\), etc.  Construct explicitly a well ordered subset
\(W\) of the reals such that \(\Lambda ^ 3 (W)\) is nonempty.

\end{document}
