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$.
      • Answer:
      • $ D$ is reflexive since any integer divides itself.
      • $ D$ is not symmetric since, for example, $ 2 \mid 4$ but $ 4 \not\ \mid 2$.
      • $ D$ is transitive. Proof:
        Let $ a$, $ b$, and $ c$ be arbitrary integers. Assume $ a \mid b$ and $ b \mid c$.
        By the definition of divides, $ \exists m, n \in {\bf {Z}}$ such that $ a = mb$ and $ b = nc$.
        By substitution, $ a = m(nc) = (mn)c$. And since $ mn \in {\bf {Z}}$ by closure of $ {\bf {Z}}$ under multiplication, $ a \mid c$ by definition of divides.
        Therefore, $ D$ is transitive by the definition of transitive.
      • $ D$ is not antisymmetric since, for example, $ 1 \mid -1$ and $ -1 \mid 1$, but $ 1 \neq -1$.
    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)$.
      • Answer:
      • # is reflexive since given any $ S \in P(X)$, $ n(S) = n(S)$.
      • # is symmetric since given any $ S, T \in P(X)$, if $ n(S)=n(T)$ then $ n(T)=n(S)$.
      • # is transitive since given any $ S, T, V \in P(X)$, if $ n(S)=n(T)$ and $ n(T)=n(V)$, then $ n(S)=n(V)$ by transitivity of equals.
      • # is not antisymmetric since $ \{a\} \char93 \{b\}$ and $ \{b\} \char93 \{a\}$, but $ \{a\} \neq \{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)$.
      • Answer:
      • $ R$ is not reflexive since $ n(\emptyset) \not < n(\emptyset)$.
      • $ R$ is not symmetric since $ n(\emptyset) < n(\{a\})$, but $ n(\{a\}) \not < n(\emptyset)$.
      • $ R$ is transitive since given any $ S, T, V \in P(X)$, if $ n(S)<n(T)$ and $ n(T)<n(V)$, then $ n(S)<n(V)$ by transitivity of less than.
      • $ R$ is antisymmetric since given any $ S, T \in P(X)$, if $ n(S)<n(T)$ and $ n(T)<n(S)$, then $ T=S$. This may seem silly, since there are no possible sets such that their sizes are both less than and greater than each other. However, this fact makes the implication vacuously true -- we can't find a counterexample, so it has to be true!
    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)$.
      • Answer:
      • $ T$ is not reflexive since $ n(\emptyset) = n(\emptyset)$.
      • $ T$ is symmetric since given any $ S, V \in P(X)$, if $ n(S) \neq n(V)$, then $ n(V) \neq n(S)$ because $ \neq$ is symmetric.
      • $ T$ is not transitive since, for example, $ n(\{a\}) \neq n(\{a,b\})$, and $ n(\{a,b\}) \neq n(\{c\})$, but $ n(\{a\}) = n(\{c\})$.
      • $ T$ is not antisymmetric since, for example, $ n(\{a\}) \neq n(\{a,b\})$ and $ n(\{a,b\}) \neq n(\{a\})$, but $ \{a\} \neq \{a,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$ )$.
      • Answer:
      • $ I$ is reflexive since given any boolean formula $ a$, $ a \lor \sim a$ is true, which means $ a \to a$ is true.
      • $ I$ is not symmetric since, for example, $ p \to (p \lor q)$ is true, but $ (p \lor q) \to p$ is not true.
      • $ I$ is transitive since, given any boolean formulas $ a, b,$ and $ c$, if $ a \to b$ is true and $ b \to c$ is true, then $ a \to c$ is true by hypothetical syllogism.
      • $ I$ is not antisymmetric since, for example, $ p \to (p \wedge p)$ is true, and $ (p \wedge p) \to p$ is true, but $ p \wedge p \neq p$. The two formulas are equivalent, but not equal.
  3. Note: there may be other possible answers besides the ones given here.
    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.
      • Answer: $ R = \{(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (2, 3), (2, 1), (3, 2)\}$.
    2. symmetric and transitive, but not reflexive.
      • Answer: $ R = \{(1, 2), (2, 1), (1, 1), (2, 2)\}$.
    3. reflexive, symmetric, transitive, and antisymmetric.
      • Answer: $ R = \emptyset \quad$ OR $ \quad R = \{(1,1),(2,2),(3,3),(4,4),(5,5)\}$.
  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.
      • Answer: We need to show $ Q$ is reflexive, symmetric, and transitive.
      • Reflexive: Let $ x$ be an arbitrary real number. Since $ x-x=0$, and 0 is an integer, $ x \ Q \ x$. Therefore, $ Q$ is reflexive by the definition of reflexive.
      • Symmetric: Let $ x$ and $ y$ be arbitrary reals such that $ x \ Q \ y$. Therefore, $ x-y\in{\bf {Z}}$. Since $ x-y$ is an integer, we can write $ k = x-y$ for some integer $ k$. Therefore, $ y-x = -(x-y) = -k$, and $ -k$ is an integer by closure of $ {\bf {Z}}$ under negation, which means $ y \ Q \ x$. So we proved $ (x \ Q \ y) \to (y \ Q \ x)$. Therefore, $ Q$ is symmetric by the definition of symmetric.
      • Transitive: Let $ x,y,z$ be arbitrary reals such that $ x \ Q \ y$ and $ y \ Q \ z$. Therefore, $ \exists m, n \in Z$ such that $ x-y=m$ and $ y-z=n$. Adding these two equations together, we obtain $ x-z=m+n$. Since $ m+n\in{\bf {Z}}$ by closure of $ {\bf {Z}}$ under addition, we know that $ x \ Q \ z$. So we showed $ (x \ Q \ y) \wedge (y \ Q \ z) \to (x \ Q \ z)$. Therefore, $ Q$ is transitive by the definition of transitive.
    2. Describe the equivalence classes of $ Q$.
      • Answer: There is one equivalence class for each real number in the interval $ [0, 1)$. For each real number $ r$, $ [r] = \{r + k \mid k \in {\bf {Z}}\}$. That is, given a real number $ r$, the equivalence class for $ r$ is the set of all real numbers that can be obtained by adding any integer (positive, negative, or zero) to $ r$.
  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?
      • Answer: $ P$ represents the direct prerequisites for computer science classes at UMD.
    2. Write $ P$ in matrix form.
      • Answer:
          106 114 214 250 311 330 351
        106 0 1 0 0 0 0 0
        114 0 0 1 0 0 0 0
        214 0 0 0 0 1 1 1
        250 0 0 0 0 1 1 1
        311 0 0 0 0 0 0 0
        330 0 0 0 0 0 0 0
        351 0 0 0 0 0 0 0
    3. Draw the directed graph for $ P$.



      \includegraphics[scale=.8]{hw14fig1}


    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.
      • Answer:
          106 114 214 250 311 330 351
        106 1 1 1 0 1 1 1
        114 0 1 1 0 1 1 1
        214 0 0 1 0 1 1 1
        250 0 0 0 1 1 1 1
        311 0 0 0 0 1 0 0
        330 0 0 0 0 0 1 0
        351 0 0 0 0 0 0 1
    5. Draw the Hasse diagram for $ P'$.



      \includegraphics[scale=.8]{hw14fig2}

    6. Find the least, minimal, greatest, and maximal element(s) for $ P'$ if they exist.
      • Answer:
      • Least element: none.
      • Minimal elements: 106, 250.
      • Greatest element: none.
      • Maximal elements: 330, 311, 351.

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 hw14ans

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

Phillip Kirlin 2004-05-10

Web Accessibility