CMSC 250 Homework 13 Fall 2001
Due Wed Dec 5 at the beginning of your discussion section.

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. 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 at least 4 elements of $A$ to one of the $A_{k}'s$.

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

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

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

  5. 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? Is $R$ reflexive? Is $R$ irreflexive? Give reasons for your answers.

  6. Give examples of relations with the following properties using matrix notation, or state why such a matrix cannot be created. Your matrices must be at least 3x3.

    1. The relation is reflexive but not symmetric, asymmetric, antisymmetric, or irreflexive.

    2. The relation is asymmetric and antisymmetric, but not reflexive or irreflexive.

    3. The relation is symmetric but not reflexive, asymmetric, or antisymmetric.

  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, or explain why it isn't a partial ordering.

  9. Using the subset inclusion 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$.

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 h13.tex

The translation was initiated by Deep Saraf on 2001-11-29

Deep Saraf
2001-11-29