CMSC250, Spring 2004 Homework 14

Never due. Use this for practice.

  1. How many binary relations are there from a set with $ m$ elements to a set with $ n$ elements?
  2. Determine whether each of the following relations are reflexive, symmetric, transitive, antisymmetric or none of these. Justify each answer with a proof or counterexample.
    1. $ D$ is the ``divides'' relation on $ {\bf {Z}}$: for all integers $ m$ and $ n$, $ m \ D \ n \leftrightarrow m \mid n$.
    2. Let $ X = \{a, b, c\}$ and $ P(X)$ be the power set of $ X$. A binary relation # is defined on $ P(X)$ as follows: for all $ A, B \in P(X)$, $ A \ \char93 \ B \leftrightarrow n(A)=n(B)$.
    3. Let $ X = \{a, b, c\}$ and $ P(X)$ be the power set of $ X$. A binary relation R is defined on $ P(X)$ as follows: for all $ A, B \in P(X)$, $ A \ R \ B \leftrightarrow n(A)<n(B)$.
    4. Let $ X = \{a, b, c\}$ and $ P(X)$ be the power set of $ X$. A binary relation T is defined on $ P(X)$ as follows: for all $ A, B \in P(X)$, $ A \ T \ B \leftrightarrow n(A) \neq n(B)$.
    5. Let $ C$ be the set of all boolean formulas in three variables $ p,q$ and $ r$. Define $ I$ to be the ``implies'' relation on $ C$: for all boolean statements $ a$ and $ b$ in $ C$, $ (a \ I \ b) \leftrightarrow (a \to b$    is true$ )$.
  3. Let $ A = \{1, 2, 3, 4, 5\}$. For each part, define a binary relation $ R$ on set $ A$ so that $ R$ is
    1. reflexive and symmetric, but not transitive.
    2. symmetric and transitive, but not reflexive.
    3. reflexive, symmetric, transitive, and antisymmetric.
  4. Let $ Q$ be the relation on $ {\bf {R}}$ defined as follows:

       for all $\displaystyle x,y \in {\bf {R}}, \ \ x \ Q \ y \leftrightarrow x-y \in {\bf {Z}}. $

    1. Prove $ Q$ is an equivalence relation.
    2. Describe the equivalence classes of $ Q$.
  5. Let $ C = \{106, 114, 214, 250, 311, 330, 351\}$, and let the binary relation $ P$ on $ C$ be defined as follows: $ P = \{(106, 114), (114, 214), (250, 311), $(250, 330)$ , $(250, 351) $ , (214, 311)$, $ (214, 330)$, $ (214, 351)\}$.
    1. Can you figure out what relation $ P$ represents?
    2. Write $ P$ in matrix form.
    3. Draw the directed graph for $ P$.
    4. Write the transitive and reflexive closure of $ P$ in matrix form, call this new relation $ P'$. Check that $ P'$ is now a partial order relation.
    5. Draw the Hasse diagram for $ P'$.
    6. Find the least, minimal, greatest, and maximal element(s) for $ P'$ if they exist.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002 (1.62)

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 -split 0 -nonavigation -antialias_text -antialias hw14

The translation was initiated by Phillip Kirlin on 2004-05-07

Phillip Kirlin 2004-05-07

Web Accessibility