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). Wow would you be able to determine if A and B have the same cardinality?

   2. Give the information necessary to show that $Z^{\geq 0 }$ has the same cardinality as $Z^+$.

   3. Give the information necessary to show that $Z$ has the same cardinality as $Z^+$.

   4. Give the information necessary to show that $Z^even$ has the same cardinality as $Z^+$.

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}$.

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$

   2. The reflexive closure of $R$.

   3. The symmetric closure of $R$.

   4. The transitive closure of $R$.

4. Redo number 2 representing each relation as a matrix.

5. Redo number 2 representing each relation as a directed graph.

6. Let $R$ be a relation defined by

   	1 0 0 0 1 0
   	0 0 1 0 0 1
   	1 1 0 0 0 1
   	1 0 1 0 1 0
   	0 0 0 0 0 1
   	0 1 1 1 0 0

   Write the matrices representing the reflexive and symmetric closures of $R$. Is $R$ asymmetric? Is $R$ antisymmetric? Give reasons for your answers.

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.

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.

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$.

Web Accessibility