Mathematical Reasoning: Writing and Proof (PreTeXt Edition)

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:

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

That is, $R[y]$ consists of those elements in $A$ such that $xRy\text{.}$ For example, using $y=a\text{,}$ we see that $aRa\text{,}$ $bRa\text{,}$ and $eRa\text{,}$ and so $R[a]=\{a,b,e\}\text{.}$

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:

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

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]=\mathrm{\varnothing }$ since there is no $x\in A$ such that $(x,a)\in S\text{.}$