CMSC 250 Homework 12 Fall 2001
Due Wed Nov 28 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 = \{0,1,2,3,\}$ and $B=\{1,2,4\}$. The element $a\in A$ is related to the element $b\in B$ by relation $R$ if either $2^{a}=b$, or if $a$ is an integral power of $2$.

    1. Write down $a$ $R$ $b$ or $a$ $\not R$ $b$ for each pair of elements in $a\in A$ and $b\in B$ corresponding to whether or not $a$ is related to $b$.

    2. List the elements of $A\times B$.

    3. List the elements of $R = \{(a,b)\in A\times B \vert a\,\,R\,\,b\}$.

  2. Let $A = \{x\in{\bf {Z}}\vert 1\leq x \leq 6\}$. The element $a_{1}\in A$ is related to the element $a_{2}\in A$ by relation $R$ if $a_{1} \vert a_{2}$.

    1. List the elements of $A\times A$.

    2. List the elements of $R = \{(a_{1},a_{2})\in A\times A \vert a\,\,R\,\,a\}$.

  3. Let $A = \{2,3,4,5,6\}$, and let $B=\{5,6,7,8,9\}$. Let $R$ be a relation from $A$ to $B$ defined by $a\in A$ is related to $b\in B$ if $a$ and $b$ share a common prime divisor. List the elements of $R$.

  4. Let $P$ be the set of all people. Let $R$ be a relation defined by: $p_{1}\in P$ is related to $p_{2}$ in $P$ if $p_{1}$ is either a child or parent of $p_{2}$. Give a chain of relations that connect the following people to each other:

    For example, two siblings are related by the following chain of relations

    (sibling1, parent) and (parent, sibling2)

    1. A person to the sibling of one of her parents.

    2. Two people who have parents that are siblings (cousins).

    3. A grandparent to a grandchild.

  5. Find which of the following relationships are reflexive, which are symmetric, and which are transitive.
    1. $x,y\in\{\hbox{people}\}$. x R y = ``x lives on the same street as y.''

    2. $x,y\in\{\hbox{Professional Football Teams}\}$ x R y = ``x can beat y.''

    3. $x,y\in{\bf {R}}$. Let $a\in{\bf {R}}$ be fixed. x R y = `` $ax\in{\bf {Q}}\rightarrow ay\in{\bf {Q}}.$''

    4. $x,y\in{\bf {R}}$. x R y = `` $xy\in{\bf {Q}}.$''

    5. $x,y\in\{\hbox{Cars}\}$. x R y = ``x gets better gas mileage than y.''

  6. Let $A = \{x\in{\bf {Z}}\vert 1\leq x\leq 20\}$. Let $R$ be a relation on $A\times A$ defined by $a_{1}$ is related to $a_{2}$ if $a_{1}\equiv a_{2}\hbox{ mod }5.$ Show that $A$ is reflexive, symmetric, and transitive. Partition $A$ into $5$ subsets in such a way that the elements of each individual subset is related to all of the other elements in that subset.

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

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

Deep Saraf
2001-11-12