Skip to main content

Discrete Mathematical Structures

Dan Yasaki, Sebastian Pauli

Exercises 6.2.3 Exercises

1.

Give the definition for these terms. Be sure to set up any notation that is required.
  1. equivalence relation
    🔗
    🔗
  2. equivalent elements
    🔗
    🔗
  3. equivalence class
    🔗
    🔗
  4. partition of a set
    🔗
    🔗
🔗
🔗

2.

Define an equivalence relation on the set of restaurants in Greensboro.
🔗
🔗

3.

Define an equivalence relation on the set of classes offered at UNCG.
🔗
🔗

4.

Let \(\sim\) be an equivalence relation on a set \(A\text{,}\) and let \(a\) and \(b\) be elements of \(A\text{.}\) Prove that if \(a\) is equivalent to \(b\text{,}\) then the equivalence class of \(a\) is equal to the equivalence class of \(b\text{.}\) In other words, show if \(a \sim b\text{,}\) then \([a] = [b]\text{.}\)
🔗
🔗

5.

Consider the relation \(R = \{(a,b) \given a \text{ divides }b\}\) on the set \(\{1,2,3,4\}\text{.}\) Is \(R\) an equivalence relation ? Justify.
🔗
🔗

6.

Let \(R\) be the relation on the set of all people, defined by
\begin{equation*} R = \{(a, b) \given a \text{ and } b \text{ were born in the same month}\}. \end{equation*}
Prove that \(R\) is an equivalence relation.
🔗
🔗

7.

Suppose \(\sim\) is an equivalence relation on a set \(A\text{,}\) and \(a\) and \(b\) are elements of \(A\text{.}\) Prove that if \([a] \cap [b] \neq \emptyset\text{,}\) then \(a\sim b\text{.}\)
🔗
🔗

8.

Let \(R\) be the relation on \(\ZZ^2\) such that \((a,b)R(c,d)\) if and only if \(a + d = b + c\text{.}\) Is \(R\) an equivalence relation ? Justify your answer.
🔗
🔗

9.

Let \(R\) be the relation on \(\ZZ^2\) such tha \((a,b)R(c,d)\) if and only if \(ad = bc\text{.}\) Is \(R\) an equivalence relation ? Justify your answer.
🔗
🔗

10.

Which of these relations on the set of all people are equivalence relations ? Justify your answers.
  1. \(\displaystyle \{(a,b) \given a \text{ and } b \text{ are the same height}\}\)
    🔗
    🔗
  2. \(\displaystyle \{(a,b) \given a \text{ and } b \text{ live in the same state}\}\)
    🔗
    🔗
  3. \(\displaystyle \{(a,b) \given a \text{ and } b \text{ have met}\}\)
    🔗
    🔗
  4. \(\{(a,b) \given a \text{ and } b \text{ are blood relatives}\}\)
     1 
    A person who is related to another through a common ancestor, and not by marriage or adoption.
    🔗
    🔗
  5. \(\displaystyle \{(a,b) \given a \text{ and } b \text{ speak a common language}\}\)
    🔗
    🔗
🔗
🔗

11.

Which of these relations on \(\{1,2,3,4\}\) are equivalence relations ? Justify your answers.
  1. \(\displaystyle \{(1,1),(2,2),(3,3),(4,4)\}\)
    🔗
    🔗
  2. \(\displaystyle \{(1,2),(2,1),(1,3),(3,1),(1,4),(4,1)\}\)
    🔗
    🔗
  3. \(\displaystyle \{(1,1),(2,2),(1,2),(2,1),(3,3),(4,4)\}\)
    🔗
    🔗
  4. \(\displaystyle \{(1,1),(2,2),(1,2),(2,1),(1,3),(3,1),(3,3),(4,4)\}\)
    🔗
    🔗
🔗
🔗

12.

Let \(A\) and \(B\) be sets, and let \(f \colon A \to B\) be a function. Let \(R\) be the relation on \(A\) defined by
\begin{equation*} R = \{(a_1,a_2) \in A^2 \given f(a_1) = f(a_2)\}. \end{equation*}
  1. Prove that \(R\) is an equivalence relation.
    🔗
    🔗
  2. Describe the equivalence classes of \(R\text{.}\)
    🔗
    🔗
🔗
🔗
🔗
PrevTopNext