Skip to main content

Beginning Activity Beginning Activity 1: Sets Associated with a Relation
A4US

As was indicated in Section 7.2, an equivalence relation on a set \(A\) is a relation with a certain combination of properties (reflexive, symmetric, and transitive) that allow us to sort the elements of the set into certain classes. This is done by means of certain subsets of \(A\) that are associated with the e lements of the set \(A\text{.}\) This will be illustrated with the following example. Let \(A = \left\{ {a, b, c, d, e} \right\}\text{,}\) and let \(R\) be the relation on the set \(A\) defined as follows:

\begin{align*} a \amp \mathrel{R} a \amp b \amp \mathrel{R} b \amp c \amp \mathrel{R} c \amp d \amp \mathrel{R} d \amp e \amp \mathrel{R} e\\ a \amp \mathrel{R} b \amp b \amp \mathrel{R} a \amp b \amp \mathrel{R} e \amp e \amp \mathrel{R} b\\ a \amp \mathrel{R} e \amp e \amp \mathrel{R} a \amp c \amp \mathrel{R} d \amp d \amp \mathrel{R} c \end{align*}

For each \(y \in A\text{,}\) define the subset \(R[y]\) of \(A\) as follows:

\begin{equation*} R[y] = \left\{ x \in A \mid x \mathrel{R} y \right\}\text{.} \end{equation*}

That is, \(R[y]\) consists of those elements in \(A\) such that \(x \mathrel{R} y\text{.}\) For example, using \(y = a\text{,}\) we see that \(a \mathrel{R} a\text{,}\) \(b \mathrel{R} a\text{,}\) and \(e \mathrel{R} a\text{,}\) and so \(R[a] = \{ a, b, e \}\text{.}\)

1.

Determine \(R[b]\text{,}\) \(R[c]\text{,}\) \(R[d]\text{,}\) and \(R[e]\text{.}\)

2.

Draw a directed graph for the relation \(R\) and explain why \(R\) is an equivalence relation on \(A\text{.}\)

3.

Which of the sets \(R[ a ]\text{,}\) \(R[ b ]\text{,}\) \(R[ c ]\text{,}\) \(R[ d ]\text{,}\) and \(R[ e ]\) are equal?

4.

Which of the sets \(R[ a ]\text{,}\) \(R[ b ]\text{,}\) \(R[ c ]\text{,}\) \(R[ d ]\text{,}\) and \(R[ e ]\) are disjoint?

As we will see in this section, the relationships between these sets are typical for an equivalence relation. The following example will show how different this can be for a relation that is not an equivalence relation.

Let \(A = \left\{ {a, b, c, d, e} \right\}\text{,}\) and let \(S\) be the relation on the set \(A\) defined as follows:

\begin{align*} b \amp \mathrel{S} b \amp c \amp \mathrel{S} c \amp d \amp \mathrel{S} d \amp e \amp \mathrel{S} e\\ a \amp \mathrel{S} b \amp a \amp \mathrel{S} d \amp b \amp \mathrel{S} c\\ c \amp \mathrel{S} d \amp d \amp \mathrel{S} c \end{align*}

5.

Draw a digraph that represents the relation \(S\) on \(A\text{.}\) Explain why \(S\) is not an equivalence relation on \(A\text{.}\)

For each \(y \in A\text{,}\) define the subset \(S[y]\) of \(A\) as follows:

\begin{equation*} S[ y ] = \left\{ { {x \in A } \mid x \mathrel{S} y} \right\} = \left\{ { {x \in A } \mid \left( {x, y} \right) \in S} \right\}\text{.} \end{equation*}

For example, using \(y = b\text{,}\) we see that \(S[b] = \{ a, b \}\) since \((a, b) \in S\) and \((b, b) \in S\text{.}\) In addition, we see that \(S[a] = \emptyset\) since there is no \(x \in A\) such that \((x, a) \in S\text{.}\)

6.

Determine \(S[ c ]\text{,}\) \(S[ d ]\text{,}\) and \(S[ e ]\text{.}\)

7.

Which of the sets \(S[ a ]\text{,}\) \(S[ b ]\text{,}\) \(S[ c ]\text{,}\) \(S[ d ]\text{,}\) and \(S[ e ]\) are equal?

8.

Which of the sets \(S[ b ]\text{,}\) \(S[ c ]\text{,}\) \(S[ d ]\text{,}\) and \(S[ e ]\) are disjoint?