Worksheet Worksheet
Definition 5.1.1.
Let \(X, Y\) be sets. A subset \(\mathcal{R}\) of \(X\times Y\) is known as a relation from \(X\) to \(Y\). If \(x\in X, y\in Y\) such that \((x,y)\in \mathcal{R}\text{,}\) we say that \(x\) and \(y\) are related and sometimes write \(x \mathcal{R} y\text{.}\) We call \(X\) the domain of the relation and \(Y\) the codomain of the relation.
Activity 5.1.2.
Consider some pairs of sets we’ve already studied. Write down some (small) relations between them.
Then, consider the set
\begin{equation*}
\mathcal{R} = \setof{(x,y)\in \Z\times \N}{x^2 + y^2 = z^2\text{ for some }z\in \Z}.
\end{equation*}
Describe this relation; what is its domain? Its codomain? Give some examples of ordered pairs in \(\mathcal{R}\text{.}\)
Many phenomena we’ve explored so far can be thought of in relational terms.
Activity 5.1.3.
Describe the relation exhibited below:
\begin{equation*}
\mathcal{S} = \setof{(S,T)\in\mathcal{P}(U)\times \mathcal{P}(U)}{S\subseteq T}.
\end{equation*}
Activity 5.1.4.
Consider the relations below.
\begin{equation*}
\mathcal{D} = \setof{(m,n)\in\Z\times\Z}{n=mk\text{ for some } k\in\Z}, \text{ and}
\end{equation*}
\begin{equation*}
\mathcal{E} = \setof{(m,n)\in\Z\times\Z}{m=n}.
\end{equation*}
What is the domain of \(\mathcal{D}\text{?}\) The codomain? What about for \(\mathcal{E}\text{?}\)
Given \(a\in \Z\text{,}\) do we have \((a,a)\in \mathcal{D}\text{?}\) How about \((a,a)\in \mathcal{E}\text{?}\) Justify.
Given \(a,b\in\Z\text{,}\) if \((a,b)\in \mathcal{D}\text{,}\) must we have \((b,a)\in \mathcal{D}\text{?}\) If \((a,b)\in \mathcal{E}\text{,}\) must we have \((b,a)\in\mathcal{E}\text{?}\) Justify.
Given \(a,b,c\in\Z\text{,}\) if \((a,b)\in \mathcal{D}\) and \((b,c)\in\mathcal{D}\text{,}\) must we have \((a,c)\in \mathcal{D}\text{?}\) If \((a,b),(b,c)\in\mathcal{E}\text{,}\) must \((a,c)\in\mathcal{E}\text{?}\) Justify.
The properties observed in
Activity 5.1.4 define a particularly important class of relations. As these relations generalize the notion of equality, they are typically called
equivalence relations.
Definition 5.1.5.
Let \(\mathcal{R}\) be a relation on a set \(X\) (that is, \(\mathcal{R}\subseteq X\times X\)).
We say that \(\mathcal{R}\) is reflexive if for all \(x\in X\text{,}\) \((x,x)\in \mathcal{R}\text{.}\)
We say that \(\mathcal{R}\) is symmetric if whenever \((x,y)\in \mathcal{R}\) we must have \((y,x)\in \mathcal{R}\text{.}\)
We say that \(\mathcal{R}\) is transitive if whenever \((x,y), (y,z)\in \mathcal{R}\) we must have \((x,z)\in \mathcal{R}\text{.}\)
A relation that is reflexive, symmetric, and transitive is called an equivalence relation. If \(\mathcal{R}\) is an equivalence relation on \(X\text{,}\) and given \(x\in X\text{,}\) the set
\begin{equation*}
\overline{x} = \setof{y\in X}{(x,y)\in \mathcal{R}}
\end{equation*}
is known as the equivalence class of \(x\text{;}\) we call \(x\) the representative of the equivalence class.
We have seen examples of equivalence relations already.
Activity 5.1.7.
Which relation from
Activity 5.1.4 is an equivalence relation? Describe the equivalence classes. Justify.
Problem 5.1.8.
Consider the following relations. Determine whether each is reflexive, symmetric, or transitive. Identify which relations are equivalence relations and which are not. For those which describe equivalence relations, identify the relation’s equivalence classes.
Let \(P\) be the set of all people in the world, and define a relation \(\mathcal{B}\) on \(P\) by \((x,y)\in \mathcal{B}\) if and only if \(x\) and \(y\) have the same birthday.
Let \(U\) be a set and define \(\mathcal{S}\) on \(U\times U\) by \((S,T)\in \mathcal{S}\) if and only if \(S\subsetneq T\text{.}\) What if we defined \(\mathcal{S}'\) by \((S,T)\in \mathcal{S}'\) if and only if \(S\subseteq T\text{?}\)
Let \(\mathcal{L}\subseteq \R^2\) be the relation \((x,y)\in\mathcal{L}\) if and only if \(x\lt y\text{.}\)
Let \(G = (V,E)\) be a graph, and define \(\mathcal{A}\) on \(V^2\) to be defined by \((u,v)\in \mathcal{A}\) if and only if \(u = v\) or \(\set{u,v}\in E\text{.}\)
We next collect some properties of equivalence classes.
Theorem 5.1.9.
Let \(X\) be a set and \(\mathcal{R}\) an equivalence relation on \(X\text{.}\) Given \(x\in X\text{,}\) we have \(x\in \overline{x}\text{.}\)
Theorem 5.1.10.
Let \(X\) be a set and \(\mathcal{R}\) an equivalence relation on \(X\text{.}\) Given \(x,y\in X\text{,}\) we have \((x,y)\in \mathcal{R}\) if and only if \(\overline{x} = \overline{y}\text{.}\)
Theorem 5.1.11.
Let \(X\) be a set and \(\mathcal{R}\) an equivalence relation on \(X\text{.}\) Given \(x,y\in X\text{,}\) we have \(\overline{x} = \overline{y}\) or \(\overline{x}\cap \overline{y} = \emptyset\text{.}\)
Given an equivalence relation
\(\mathcal{R}\) on a set
\(X\text{,}\) the equivalence classes of
\(\mathcal{R}\) can be thought of as
partitioning the set
\(X\text{;}\) recall
Definition 4.4.9. However, the story is more interesting, as every partition gives rise to an equivalence relation.
Theorem 5.1.12.
Let \(X\) be a set and \(\mathcal{R}\) an equivalence relation on \(X\text{.}\) Then the equivalence classes of \(R\) partition \(X\text{.}\)
Theorem 5.1.13.
Let \(X\) be a set and \(\set{C_\alpha}_{\alpha\in\Lambda}\) a partition of \(X\text{.}\) Define a relation \(\mathcal{R}\) as follows: given \(x,y\in X\text{,}\) \((x,y)\in \mathcal{R}\) if and only if there exists \(\alpha \in \Lambda\) such that \(x,y\in C_\alpha\text{.}\)
Then \(\mathcal{R}\) is an equivalence relation on \(X\text{.}\)
