CRN 12107: HW 7

Problem 31. On the set of natural numbers $\mathbb{N}$ consider the partial order \[n\ |\ m \Leftrightarrow\ n\mbox{ is a divisor of }m.\]

1. Draw a Hasse diagram for the set $A=\{1,2,3,4,5,\ldots, 12,13,14,15\}$ endowed with this partial order.
2. Find the largest element (maximum) of $A$, or show that it does not exist.
3. Find the maximal elements of $A$, or show that none exist.
4. Find three upper bounds for $A$ in $\mathbb{N}$.

Problem 32. Consider $\mathbb{R}^2$ with the lexicographical order $\leq_\ell$: \[(a,b)\leq_\ell (c,d)\quad\Leftrightarrow\quad (a<c) \vee ((a=c) \wedge (b\leq d)).\]

1. Show that $\leq_\ell$ is a linear order on $\mathbb{R}^2$.
2. Find a subset of $(\mathbb{R}^2,\leq_\ell)$ that is bounded from above, but fails to have a least upper bound.

Problem 33. The relation "$\preceq$" on a Boolean Algebra ${\cal B}$ defined by $A\preceq B \Leftrightarrow A\sqcup B=B$ for $A,B\in{\cal B}$ is a partial order (cp. Problem 30). Let ${\cal B}$ be a Boolean Algebra with null-element $N$, partially ordered by $\preceq$. We say that $A\in{\cal B}$ is an atom of ${\cal B}$ if $N$ is the immediate predecessor of $A$.

1. Find all atoms of ${\cal P}(\{1,2,3,4\})$.
2. Find all atoms of ${\cal D}_{42}$, defined in Problem 20.
3. Suppose the Boolean Algebra ${\cal B}$ has finitely many elements. Show that for every $B\in{\cal B}$ with $B\neq N$ there is an atom $A$ such that $A\preceq B$.

Problem 34.

1. Find a function whose domain is the set of real numbers $\mathbb{R}$ and whose range is the set of rational numbers $\mathbb{Q}$.
2. Find a function whose domain is the set of natural numbers $\mathbb{N}$ and whose range is the set of integers $\mathbb{Z}$.

Problem 35.

1. Find functions $f:B\to C$, $g:A\to B$ and $h:A\to B$ such that $f\circ g=f\circ h$, yet $g\ne h$.
2. Suppose $f:A\to B$ is a surjective function. Prove or disprove: If $g:B\to C$ and $h:B\to C$ satisfy $g\circ f=h\circ f$, then $g=h$.