CMSC 250 Fall 2001 Homework 13 solutions

1. There are 40 elements in $A$, and 11 equivalence classes for $R$. Thus, by the generalized pigeonhole principle, since $\lceil\frac{40}{11}\rceil = 4$, any function $f:A\rightarrow\{A_{k}\}$ must map at least four elements to one of the $A_{k}$'s.

2. 1. R $= \{(a,b), (c,a), (d,f), (e,g)\}$.

   2. The reflexive closure of R: $\{(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(g,g)\}\cup R.$

   3. The symmetric closure of R: $\{(b,a), (a,c), (f,d), (g,e)\}\cup R$.

   4. The transitive closure of R: $\{(c,b) \}\cup R$.

3. 1. 0	1	0	0	0	0	0
      0	0	0	0	0	0	0
      1	0	0	0	0	0	0
      0	0	0	0	0	1	0
      0	0	0	0	0	0	0
      0	0	0	0	0	0	0
      0	0	0	0	1	0	0

   2. 1	1	0	0	0	0	0
      0	1	0	0	0	0	0
      1	0	1	0	0	0	0
      0	0	0	1	0	1	0
      0	0	0	0	1	0	0
      0	0	0	0	0	1	0
      0	0	0	0	1	0	1

   3. 0	1	1	0	0	0	0
      1	0	0	0	0	0	0
      1	0	0	0	0	0	0
      0	0	0	0	0	1	0
      0	0	0	0	0	0	1
      0	0	0	1	0	0	0
      0	0	0	0	1	0	0

   4. 0	1	0	0	0	0	0
      0	0	0	0	0	0	0
      1	1	0	0	0	0	0
      0	0	0	0	0	1	0
      0	0	0	0	0	0	0
      0	0	0	0	0	0	0
      0	0	0	0	1	0	0

4. 

5. The original relation $R$ is:

   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

   The reflexive closure of $R$ is:

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

   The symmetric closure of $R$ is:

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

   To answer the following problems, assume that the matrix represents a binary relation on the set $A=\{1,2,3,4,5,6\}$, since it's some arbitrary set with 6 elements.

   1. Is $A$ asymmetric? No, $(1,1)\in R$.

   2. Is $A$ antisymmetric? No, $(3,2)$ and $(2,3)\in R$.

   3. Is $A$ reflexive? No, $(2,2)\notin R$.

   4. Is $A$ irreflexive? No, $(1,1)\in R$.

6. 1. 1	0	1
      0	1	0
      1	1	1

   2. This matrix cannot exist because asymmetric means that $a\not{R}a$ for all $a\in A$, and irreflexive means the same thing.

   3. 0	1	0
      1	0	0
      0	0	0

7. R $= \{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9),\\ (1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(2,4),\\ (2,6),(2,8),(3,6),(3,9),(4,8)\}$
   

   R is antisymmetric because given distinct elements $a$ and $b$ in $A$, it is not possible for $a\vert b$ and $b\vert a$ simultaneously. Because if it were true, then $ak=b$ and $bl=a$ for some $k,l\in{\bf {Z}}^{+}$ with $k,l$ both not equal to 1. Hence, $akl = (ak)l = bl = a$, which means that $kl=1$, and $k$ and $l$ are positive integers not equal to 1. This is a contradiction, so there must not be elements $a$, $b$ in $A$ such that $a\neq b$ and $aRb$ and $bRa$.

8. $R$ is not a partial ordering because it is not antisymmetric. It is possible for a set $A$ to have two subsets of the same size that are not the same subset. For example, two subsets with one element each are related to each other, but they are not the same subset.

9. Let A $= \{a,b\}$ and B$= \{b,c\}$ now since $A\not\subseteq B$ and $B\not\subseteq A$.

10. C $= \{ \emptyset, \{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\}\}$

About this document ...

This document was generated using the LaTeX2HTML translator Version 99.1 release (March 30, 1999)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -show_section_numbers -split 0 -no_navigation -no_footnode h13ans.tex

The translation was initiated by Deep Saraf on 2001-12-05