Imagine that you are in 30-year high school reunion gathering and all guests are your high school classmates. Some of your high school classmate fell in love with others 30 years ago. We can describe this social dynamic by means of a mathematical concept called relation. We form an ordered pair (John, Emily) to mean that John fell in love with Emily 30 years ago. (Is this the same as (Emily, John)?)
Friends in Facebook can also be described using relation as well. We form an order pair (John, Emily) to meant that Emily is a friend of John in Facebook. (Is this the same as (Emily, John)?)
Let \(A\) and \(B\) be two sets. A relation \(\mathcal{R}\) between \(A\) and \(B\) is a subset of \(A \times B\). We write \((a,b) \in \mathcal{R}\) or \(a \mathcal{R} b\) if \((a,b)\) is an element of the relation. We say that \(a\) is \(\mathcal{R}\)-related to \(b\) or simply just \(a\) is related to \(b\) if the relation \(\mathcal{R}\) is clear from the context. In the event that \(A = B\), we also say that \(\mathcal{R}\) is a relation on \(A\).
Let \(P\) be the set of three people \begin{equation*}\{\text{Your mother, Your father, You}\}.\end{equation*} Let \(M\) be the set of five movies \begin{equation*}\{\text{Casablanca, The Star War series, The Godfather series, The Lord of the Rings series, The Dark Knight Serie}\}.\end{equation*} Define a relation \(\mathcal{R}\) between \(P\) and \(M\) in the following way: \((p,m) \in \mathcal{R}\) if the person \(p\) likes movie \(m\). Write down the set \(\mathcal{R}\).
Is it true that a relation \(\mathcal{R}\) between \(A\) and \(B\) is a relation between \(B\) and \(A\)? Does the order of \(A\) and \(B\) matter here? Why?
Figure 6.4 is a telephone keypad. It defines a relation from the set of digits \(\Delta = \{0,1,2,\dots,9\}\) to the set of \(26\) alphabets \(\Gamma = \{A, B, \dots, Z\}\). For an element \((n,l) \in \Delta \times \Gamma\) to be in the relation \(\mathcal{R}\), we mean that the digit \(n\) and the letter \(l\) appear on the same button. Write down all the elements in the set \(\mathcal{R}\).
Let \(A = \{0, 1\}\) be a set of two elements. How many different relations of \(A\) can you find? Write down as many as you can.
Let \(\mathcal{R}\) be a relation on two sets \(A\) and \(B\). For any element \(a\) in \(A\), the relation class of \(a\), denoted by \([a]\), is a subset of \(B\) defined by \begin{equation*}[a]= \{ b \in B \; | \; a\mathcal{R}b\}.\end{equation*}
Write down the relation class of every element in \(\Delta\) in Task 6.5
We define a relation \(\mathcal{D}\) on \(\mathbb{Z}_{\gt 0}\) as follows: \(m\mathcal{D}n\) if and only if \(m \; | \; n\). Find \([3], [4], [6], [8]\), \([3] \cap [8]\) and \([4] \cap [6]\).
We define a relation \(\mathcal{D}'\) on \(\mathbb{Z}_{\gt 0}\) as follows: \(m\mathcal{D}n\) if and only if \(n \; | \; m\). Find \([3], [4], [6], [8]\), \([3] \cap [6]\) and \([4] \cap [8]\).
We define a relation \(\mathcal{M}\) on \(\mathbb{Z}\) by \(m\mathcal{M}n\) if and only if \(4 \; | \; (n-m)\). Find \([0], [1], [2], [3], [4]\) and \([1002]\).
Let \(\mathcal{R}\) be a relation on a set \(A\).
For each one of the following relations, decide if they are reflexive, symmetric, antisymmetric or transitive, and explain your answers.
Let \(P\) be the set of all students in this class. Define a relation \(\mathcal{R}\) on \(P\) in the following way: for all \(p_1, p_2 \in P\), \(p_1 \mathcal{R} p_2\) if and only if \(p_1\) graduated from the same high school as \(p_2\).
Let \(S = \{1,2,3\}\). A relation \(\mathcal{R}\) is defined by the following set: \begin{equation*}\{(1,1),(1,2),(2,1),(2,2)\}\end{equation*}
The relation is defined on \(\mathbb{Z}\): for all \(m,n \in \mathbb{Z}\), we have \(m\mathcal{R}n\) if and only if \(m+n\) is even. What will happen if even is changed to odd?
The relation is defined on \(\mathbb{Z}\): for all \(m,n \in \mathbb{Z}\), we have \(m\mathcal{D}n\) if and only if \(m \; | \; n\).
The relation is defined on the power set \(P(\mathbb{Z})\): for all \(S, T \in P(\mathbb{Z})\), we have \(S\mathcal{R}T\) if and only if \(S \subset T\).
The relation is defined on \(\mathbb{Z}\): for all \(m,n\in \mathbb{Z}\), we have \(m\mathcal{M}n\) if and only if \(4 \; | \; (n-m)\).
A relation is called an equivalence relation if it is reflexive, symmetric, and transitive. The relation class \([a]\) will be called the equivalence class of \(a\).
Let \(\mathcal{R}\) be an equivalence relation on a set \(A\). Prove or disprove: for any \(a \in A\), \(a \in [a]\).
Let \(\mathcal{R}\) be an equivalence relation on a set \(A\). Prove or disprove: for any \(a,b \in A\), we have \(a \mathcal{R} b\) if and only if \([a] = [b]\).
Let \(\mathcal{R}\) be an equivalence relation on a set \(A\). Prove or disprove: for any \(a,b \in A\), we have \(a\) is not related to \(b\) if and only if \([a] \cap [b] = \emptyset\).
We will use the notation \(\sim\) to denote an equivalence relation for the rest of this notes.
We first extend our set operations such as union and intersection to index set.
Let \(U\) be a (universal) set. We say that \(\{A_i \; | \; i \in I\}\) is a family of subsets of \(U\) if for each \(i \in I\), we have \(A_i \subset U\). Here the set \(I\) is called the index set.
Let \(\{A_i \; | \; i \in I\}\) be a family of subsets of a set \(U\).
Let \(A_i = [0,\frac{1}{i}]\) for \(i \in \mathbb{Z}_{\gt 0}\). Find \(\displaystyle \bigcap_{i \in \mathbb{Z}_{\gt 0}} A_i\).
Let \(B_i = [0,1-\frac{1}{i})\) for \(i \in \mathbb{Z}_{\gt 0}\). Find \(\displaystyle \bigcup_{i \in \mathbb{Z}_{\gt 0}} B_i\).
Let \(\sim\) be an equivalence relation on a set \(A\). Show that \(\displaystyle A = \bigcup_{a \in A} [a]\).
Let \(\mathcal{P} = \{A_i \; | \; i \in I\}\) be family of subsets of a set \(A\). We say that \(\mathcal{P}\) is a partition of \(A\) if
For each \(n \in \mathbb{Z}\), let \(G_n = [n, n+1)\). Show that \(\mathcal{P} = \{G_n \; | \; n \in \mathbb{Z}\}\) is a partition of \(\mathbb{Z}\).
Find three other partitions of \(\mathbb{Z}\).
Partitions and equivalence relations are very much related. Given an equivalence relation, we will get a partition.
If \(\sim\) is an equivalence relation defined on a set \(A\), the set of equivalence classes \(\{[a] \; | \; a \in A\}\) forms a partition of \(A\).
Given a partition \(\mathcal{P} = \{A_i \; | \; i \in I\}\) of a set \(A\), we define a relation \(\sim_{\mathcal{P}}\) as follows. For \(x, y \in A\), define \(x \sim_{\mathcal{P}} y\) if and only if there exists \(i \in I\) such that \(x, y \in A_i\). We call \(\sim_{\mathcal{P}}\) the relation induced by the partition \(\mathcal{P}\).
Show that the relation \(\sim_{\mathcal{P}}\) induced by the partition \(\mathcal{P}\) on any set \(A\) is an equivalence relation.
