CMSC 250 Homework 14 Spring 2006

This Homework is never actually due.

It is up to you when and if you do it.

You must write the solutions to the problems single-sided on your own lined paper, with all sheets stapled together, and with all answers written in sequential order or you will lose points.

1. Answer the following questions about cardinality:
   1. Assume you have two infinite sets (A and B). How would you be able to determine if A and B have the same cardinality? Find a bijection (or one-to-one correspondence) between the two sets.
   2. Give the information necessary to show that $Z^{\geq 0 }$ has the same cardinality as $Z^+$. Define $f: Z^{\geq 0 } \rightarrow Z^+$ as $f(i) = i+1$.
   3. Give the information necessary to show that $Z$ has the same cardinality as $Z^+$. Define $f: Z \rightarrow Z^+$ so that positive numbers map to the evens ($f(i)=2i$ for $i>0$) and nonpositive numbers map to the odds ($f(i) =-2i+1$ for $i\le0$).
   4. Give the information necessary to show that $Z^{even}$ has the same cardinality as $Z^+$. Define $f: Z^{even} \rightarrow Z^+$ so that positive evens map to themselves ($f(i)=i$ for $i>0$) and nonpositive numbers map to the positive odds ($f(i) =-i+1$ for $i\le0$).
2. Let $A=\{x\in{\bf {Z}}\vert 1\leq x\leq 40\}$. Let $R$ be the relation of congruence mod 11. Let $\{A_{k}\}$ be the set of equivalence classes for $R$. Prove that any function from $A$ to $B=\{A_{k}\}$ must map 4 elements to at least one $A_{j}$. $N(A) = 40$ and $N(B) = 11$.
   $N(A) > 3 \cdot N(B)$, since $40 > 3 \cdot 11$.
   By the generalized pigeon hole principle, some element of $B$ must be the image of $3+1 = 4$ elements of $A$.
3. Let $A=\{a,b,c,d,e,f,g\}$. Let $R$ be a binary relation on $A$ with the following pairs related: $aRb$, $cRa$, $dRf$, $gRe$. Write the following sets using ordered pair notation.
   1. $R$
      $\{ (a,b), (c,a), (d,f), (g,e) \}$
   2. The reflexive closure of $R$.
      $\{ (a,a), (b,b), (c,c), (d,d), (e,e), (f,f), (g,g), (a,b), (c,a), (d,f), (g,e) \}$
   3. The symmetric closure of $R$.
      $\{ (a,b), (b,a), (c,a), (a,c), (d,f), (f,d), (g,e), (e,g) \}$
   4. The transitive closure of $R$.
      $\{ (a,b), (c,a), (c,b), (d,f), (g,e) \}$
4. Redo number 3 representing each relation as a matrix.
   1. $R$
      
      
      $$\begin{array}{ c } a \\ b \\ c \\ d \\ e \\ f \\ g \\ \e... ... & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \end{array} \right]$$
      
      

   2. The reflexive closure of $R$.
      
      
      $$\begin{array}{ c } a \\ b \\ c \\ d \\ e \\ f \\ g \\ \e... ... & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ \end{array} \right]$$
      
      

   3. The symmetric closure of $R$.
      
      
      $$\begin{array}{ c } a \\ b \\ c \\ d \\ e \\ f \\ g \\ \e... ... & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \end{array} \right]$$
      
      

   4. The transitive closure of $R$.
      
      
      $$\begin{array}{ c } a \\ b \\ c \\ d \\ e \\ f \\ g \\ \e... ... & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \end{array} \right]$$
      
      

5. Redo number 3 representing each relation as a directed graph.
   
   =4.5in
6. Let $R$ be a relation defined by
   
   $$\left[ \begin{array}{ c c c c c c } 1 & 0 & 0 & 0 & 1 & 0... ... & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ \end{array} \right]$$
   
   
   Reflexive closure or $R$:
   
   $$\left[ \begin{array}{ c c c c c c } 1 & 0 & 0 & 0 & 1 & 0... ... & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 \\ \end{array} \right]$$
   
   
   Symmetric closure or $R$:
   
   $$\left[ \begin{array}{ c c c c c c } 1 & 0 & 1 & 1 & 1 & 0... ... & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 \\ \end{array} \right]$$
   
   
   Is $R$ asymmetric?
   NO: $(1,1)$ is in the relation. Is $R$ antisymmetric?
   NO: $(2,3)$ and $(3,2)$ are both in the relation.
7. Let $A=\{1,2,3,4,5,6,7,8,9\}$. Let $R$ be a binary relation defined on $A$ defined by $a_{1}Ra_{2}$ if $a_{1}\vert a_{2}$. Write the the relation using ordered pair notation, and show that the relation is antisymmetric. $\{$ $(1,2)$, $(1,3)$, $(1,4)$, $(1,5)$, $(1,6)$, $(1,7)$, $(1,8)$, $(1,9)$, $(2,2)$, $(2,4)$, $(2,6)$, $(2,8)$, $(3,3)$, $(3,6)$, $(3,9)$, $(4,4)$, $(4,8)$, $(5,5)$, $(6,6)$, $(7,7)$, $(8,8)$, $(9,9)$ $\}$ Antisymmetic: There are no two pairs $(i,j)$ and $(j,i)$ for $i \ne j$.
8. Let $A$ be a finite nonempty set and let $R$ be a relation on $P(A)$ (the power set of $A$ defined by $\forall S_{1}, S_{2}\in P(A),$ $S_{1}RS_{2}$ if $n(S_{1})\leq n(S_{2})$. Show that $R$ is a partial ordering.
9. Using the subset partial order relation, give an example of two elements that are not comparable. $\{a\}$ and $\{b\}$ Neither is a subset of the other.
10. Let $A=\{1,2,3,4,5,6,7,8\}$. Let $R$ be the partial order relation defined by inclusion of subsets of $A$. Write a chain $C$ of maximal length contained in $R$. $\{$ $\{\}$, $\{1\}$, $\{1,2\}$, $\{1,2,3\}$, $\{1,2,3,4\}$, $\{1,2,3,4,5\}$, $\{1,2,3,4,5,6\}$, $\{1,2,3,4,5,6,7\}$, $\{1,2,3,4,5,6,7,8\}$ $\}$

Web Accessibility