2. Problems (not to hand in except as assigned)

Problem B-1. (a) Draw a copy of 2$^ 4$. (Think of it either as 2$^ 2 \times$   2$^ 2$ or as 2$\times$   2$^ 3$.)

(b) Draw Subgp$($Z$_ 5 \times$   Z$_ 5)$, where Z$_ 5$ denotes the integers modulo 5.

Problem B-2. Represent the partially ordered set of Figure as a union of chains, using as few as possible:

Figure: For Problem 2.

text/adir/dilw.eps

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

Problem B-4. A 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.

Problem B-5. 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 Pow$(S)$. (Suggestion: Take $S=P$. For partially ordered sets $P$ and $Q$, a map $f:P\rightarrow Q$ is an 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$.)

Problem B-6. Show that Div$(n)$ is isomorphic to a direct product of chains.

(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'$.)

Problem B-7. Let $P$ be a partially ordered set in which every chain is finite and every antichain is finite. Show that $P$ must be finite.

Problem B-8. 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$.

Problem B-9. Show that every countable chain can be embedded in the chain Q of rationals.

(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 is the same thing.)

Problem B-10. A chain is said to be dense (or dense-in-itself) if no element covers another, and 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 Q of rationals.)

Problem B-11. 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$.

(a) Draw a diagram of 3$^ {\mbox{\bf 3}}$ (a chain to a chain power).

(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.)

(i) $(ab) ^ c = a ^ c b ^ c$,

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

(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.)

Problem B-12. Sketch (a) ${\mbox{\bf 2}} ^ {\mbox{\bf 4}}$ and (b) ${\mbox{\bf 3}} ^ {\mbox{\bf 4}}$ (chains to chain powers)

Problem B-13. (This problem concerns chains to chain powers.)

(a) Describe ${\mbox{\bf 2}} ^ {\mbox{\bf n}}$ more simply, up to isomorphism.

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

Problem B-14. Let ${\bf\omega} = \{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}$.)

Problem B-15. A 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, except for $k=3$?

Problem B-16. Prove P. Hall's theorem on distinct representatives (Corollary ).

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

Problem B-17. Prove the theorem on a system of common representatives for two equipartitions (Corollary ).

(Suggestion: Use the matching theorem.)

Problem B-18. Let    Q$$ be the set of rational numbers.

(a) Show that    R$$ can be embedded in    Pow$($Q$)$.

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

Problem B-19. If $W$ is a well ordered set, a 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.