MAT511 homework,         due Oct 29, 2003

1. Define the relation $\unlhd$ on ${\mathbb{R}}\times {\mathbb{R}}$ by $(a,b) \unlhd (c,d)$ if and only if $a\le c$ and $b \le d$. Prove that this relation is a partial ordering on ${\mathbb{R}}\times {\mathbb{R}}$.

2. Let $A$ be a partially ordered set, which we call the ``alphabet''. A ``string'' (or a ``word'') is a finite sequence of elements of $A$ (written strung all together). Let ${\mathcal W}_A$ be the set of all strings made from elements of $A$. For example, if $A = \left\{{a,b,c}\right\}$, then $a$, $abba$, $baccababa$, and $\emptyset$ are all elements of ${\mathcal W}_A$, where $\emptyset$ denotes the empty string which is of length zero.

   If $\sigma$ and $\tau$ are two strings in ${\mathcal W}_A$, then let $\sigma\smile\tau$ be the concatenation of $\sigma$ and $\tau$. For example, if $\sigma$ is the string $floo$ and $\tau$ is $baru$, then $\sigma\smile\tau$ is $floobaru$. Note that for any string $\sigma$, $\sigma\smile\emptyset = \sigma$.

   Define the relation $\ll$ on ${\mathcal W}_A$ by $\sigma \ll \tau$ if and only if there is a string $\nu \in {\mathcal W}_A$ so that $\tau = \sigma\smile\nu$.

   Prove that $\ll$ is a partial order on ${\mathcal W}_A$.

3. Let $R$ be the rectangle in the cartesian plane given by
   $$R = \left\{{ (x,y) \vrule{} 0 \le x \le 3, 0\le y \le 1}\right\}$$
   Let ${\mathcal H}$ be the set of all rectangles whose sides have positive length, are parallel to the sides of $R$, and are contained in $R$. ${\mathcal H}$ is partially ordered by set inclusion.
   1. Does every subset of ${\mathcal H}$ have an upper bound? A least upper bound? (justify your answers).
   2. Does every subset of ${\mathcal H}$ have a largest element?
   3. Does every subset of ${\mathcal H}$ have a lower bound? A greatest lower bound?
   4. Does every subset of ${\mathcal H}$ have an smallest element?