\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}