\documentclass[12pt]{article} \usepackage{amsmath,amsthm,amsfonts,amssymb,latexsym, hyperref} \newtheorem{problem} {Problem} \begin{document} \begin{center} \textbf{Relations.} \end{center} Definition. Suppose that each of $A$ and $B$ is a set. Then the Cartesian product $A \times B$ is defined to be: $$A \times B = \{(a,b) | a \in A, b \in B \}.$$ \ Definition. The set $R$ is a relation from $A$ to $B$ means that $R \subset A \times B$. If $(a,b) \in R$ then ``$a$ is related to $b$'' is often denoted by $a R b$. \ Definition. If $R$ is a relation from the set $A$ to the set $B$ then the domain (Dom) and range (Rng) of $R$ are defined as the following: \begin{eqnarray*} \mbox{Dom}(R) & = & \{ a \in A | \mbox{ there exists a } b \in B \mbox{ such that } (a,b) \in R \} \\ \mbox{Rng}(R) & = & \{ b \in B | \mbox{ there exists an } a \in A \mbox{ such that } (a,b) \in R \}. \end{eqnarray*} \ Definition. A relation $f$ from the set $A$ to the set $B$ is said to be a function if for each $x \in \mbox{Dom}(f)$ there is a unique element $y \in B$ so that $(x,y) \in f$. Notation. If $f$ is a function and $(x,y) \in f$ then the unique element $y$ is denoted by $f(x)$. \ Definition. If $R$ is a relation from the set $A$ to the set $B$ then the inverse relation, written as $R^{-1}$, is a relation from the set $B$ to the set $A$ defined by: $$R^{-1} = \{ (b,a) | (a,b) \in A \}.$$ \ Definition. If $R$ is a relation from the set $A$ to the set $B$ and $S$ is a relation from the set $B$ to the set $C$ then the composition of $S$ and $R$ relations, written as $S \circ R$, is a relation from the set $A$ to the set $C$ defined by: $$S \circ R = \{ (a,c) | \mbox{ there exists } b \in B \mbox{ so that } (a,b) \in R, (b, c) \in S \}.$$ \ Example 6.1. Let $R = \{(n,m) \Big| |n-3| + |m-5| = 20; n, m \in \mathbb{Z} \}$. Then $R$ is a relation. \qquad a.) Find the domain and range of $R$. \qquad b.) Find $R^{-1}$. \qquad c.) Find $(R^{-1})^{-1}$. \ Example 6.2. Let $R = \{(n,m) | n < m; n, m \in \mathbb{Z} \}$. Then $R$ is a relation. \qquad a.) Find the domain and range of $R$. \qquad b.) Find $R^{-1}$. \ Following are some helpful properties of relations, you may already have seen some of these in working with functions. They generalize properties of functions. You may wish to prove them: Property 6.1. Suppose that $f: A \rightarrow B$ is a function and $g=f^{-1}$ is also a function then: \begin{eqnarray*} g(f(x))& = & x \ \ \mbox{ for each } x \in \mbox{Dom}(f) \\ f(g(y))& = & y \ \ \mbox{ for each } y \in \mbox{Rng}(f). \end{eqnarray*} Question. Is it necessary that $g$ be a function for the theorem to hold? \ Property 6.2. If $R$ is a relation from the set $A$ to the set $B$ then $$(R^{-1})^{-1} = R.$$ \ Property 6.3. If $f$ is a function from the set $A$ to the set $B$ and $g$ is a function from the set $B$ to the set $C$, then $$(g \circ f)^{-1} = (f^{-1}) \circ (g^{-1}).$$ \ Examples. (i) Give an example to show that $f \circ g \ne g \circ f$. (ii) Give an example of a function whose inverse is not a function. \ \begin{center} \textbf{Equivalence Relations.} \end{center} Definitions. Suppose that $R$ is a relation from the set $A$ to itself. We will use the notation $a\sim b$ to mean that $a$ and $b$ are in $A$ and $a$ is related to $b$ or equivalently $(a,b) \in R$. Then: $R$ is said to be \textit{reflexive} if $ x \sim x$ for all $x \in A$. $R$ is said to be \textit{symmetric} if it is true that if $x \sim y$ then $y \sim x$. $R$ is said to be \textit{transitive} if it is true that if $x \sim y$ and $y \sim z$ then $x \sim z$. \ Definition. A relation from a set into itself is said to be an \textit{equivalence relation} if it is reflexive, symmetric and transitive. \ Definition. Let $R = \{(a,b) | a \sim_R b\}$ be an equivalence relation on the set $A$. Then for each $x \in A$, we define $[x]_R = \{ y | y \sim_R x \}$; this is called the equivalence class of $x$. If the relation is understood from the context, then the subscript may be omitted. \ Exercise 6.1. Let $A = \mathbb{Z}$ and $n$ be a positive integer; let $R$ be the relation so that $x \sim y$ if and only if $n|(y-x)$. Show that $R$ is an equivalence relation. (Notation. We use the notation $y = x \mod(n)$ to indicate this specific relation $R$. Another notation is $x \equiv_n y$. If the integer $n$ is understood then the notation $x \equiv y$ may be used.) Notation: $\mathbb{Z}_n = \{ [m]_{\equiv_n} | m \in \mathbb{Z} \}$. Calculate $|\mathbb{Z}_n|$. [Hint: Do it for 2, 3, 4, ... first, then generalize.] \ Theorem 6.4. Let $R$ be an equivalence relation on the set $A$. Then the following are equivalent. \qquad 1. $[x] \cap [y] \ne \varnothing$; \qquad 2. $x \sim y$; \qquad 3. $[x] = [y]$. \ Exercise 6.2. a. Let $A = \mathbb{R}$ and $\mathbb{Q}$ be the rational numbers; let $R$ be the relation so that $x \sim y$ if and only if $(y-x) \in \mathbb{Q}$. Show that $R$ is an equivalence relation. Determine $[\sqrt 2]_R$; which of the following numbers are in $[\sqrt 2 ]$: $\frac 12$, $ \sqrt 8$, $\sqrt 3$. b. Let $B = \mathbb{R^+}$ and $\mathbb{Q}$ be the rational numbers; let $S$ be the relation on $B$ so that $x \sim_S y$ if and only if $\frac xy \in \mathbb{Q}$. Show that $S$ is an equivalence relation. Determine $[\sqrt 2]_S$. Again determine which of the following numbers are in $[\sqrt 2]_S$: $\frac 12$, $ \sqrt 8$, $\sqrt 3$ \ Exercise 6.3. Let $A = \mathbb{Z} \times \{\mathbb{Z} - \{0\} \}$; let $\equiv$ be the relation so that $(a,b) \equiv (c,d) $ if and only if $ad = cb$. Show that $\equiv$ is an equivalence relation. Determine $[(1,1)], [(2,3)], [(-3, 5)]$ (give a formula if you can). \ Exercise 6.4. Let $\mathbb{Z}_n = \{[x]_{\equiv_n} | x \in \mathbb{Z} \}$. Determine the cardinality $|\mathbb{Z}_n|$ of $\mathbb{Z}_n$. \ Definition. Suppose that $S$ is a set and $\Gamma$ an index set (often $\Gamma$ will be the positive integers); then the collection of sets $\{S_{\gamma}\}_{\gamma \in \Gamma}$ is called a \textit{partition} of $S$ if and only if: (i) $S = \cup_{\gamma \in \Gamma} S_{\gamma}$; (ii) $S_{\gamma} \cap S_{\delta} = \varnothing$ whenever $\gamma \ne \delta$; (iii) $S_{\gamma} \ne \varnothing \mbox{ for all } \gamma \in \Gamma$. \ Theorem 6.5. Suppose $S$ is a set and $\{S_{\gamma}\}_{\gamma \in \Gamma}$ is a partition of $S$ and the relation $R$ on $S$ defined by $x \sim y$ if and only if $\{x, y \} \subset S_{\gamma}$ for some $\gamma \in \Gamma$. Then $R$ is an equivalence relation on $S$. Suppose $S$ is a set and $\equiv$ is an equivalence relation on $S$, then $\{ [x]_{\equiv} \ | \ x \in S \}$ is a partition of $S$. \ Exercise 6.6. Let $S$ denote the set of all finite subsets of $\mathbb{R}$ and let $A \sim B$ mean that $|A| = |B|$. Show that $\sim$ is an equivalence relation on $S$. \ Definitions: Suppose $A$ and $B$ are sets and $f:A \rightarrow B$ is a function. \noindent The function $f$ is said to be \textit{onto} (or \textit{surjective}) if for each $b \in B$ there is an $a \in A$ so that $f(a) = b$. \noindent The function $f$ is said to be \textit{one-to-one} (or \textit{injective}) if whenever $f(x) = f(y)$ we have $x=y$. \ Definition. Suppose that $ \equiv_A$ is an equivalence relation on the set $A$, $ \equiv_B$ is an equivalence relation on the set $B$; $\mathcal{A}$ and $\mathcal{B}$ are the sets of equivalence classes: \begin{eqnarray*} \mathcal{A} & = & \{ [a] | a \in A \} \\ \mathcal{B} & = & \{ [b] | b \in B \} \end{eqnarray*} Suppose further that $f: A \rightarrow B$ is a function. Then $F: \mathcal{A} \rightarrow \mathcal{B}$ defined by \begin{eqnarray*} F([x]_{\equiv_A}) & = & [f(x)]_{\equiv_B} \end{eqnarray*} is \textit{well-defined} means that whenever $x \equiv_A y$ we have $f(x) \equiv_B f(y)$. \ Exercise 6.7. Determine which of the following are well defined functions: \qquad a. $F: \mathbb{Z}_5 \rightarrow \mathbb{Z}_5$ where $F([x]_5) = [2x+1]_5$. \qquad b. $F: \mathbb{Z}_5 \rightarrow \mathbb{Z}_5$ where $F([x]_5) = [x^2]_5$. \qquad c. $F: \mathbb{Z}_5 \rightarrow \mathbb{Z}_4$ where $F([x]_5) = [2x+1]_4$. \qquad d. $F: \mathbb{Z}_3 \rightarrow \mathbb{Z}_6$ where $F([x]_3) = [2x+1]_6$. \qquad e. $F: \mathbb{Z}_3 \rightarrow \mathbb{Z}_6$ where $F([x]_3) = [5x+3]_6$. \qquad f. $F: \mathbb{Z}_3 \rightarrow \mathbb{Z}_6$ where $F([x]_3) = [2x^2+7]_6$. \qquad g. $F: \mathbb{Z}_3 \rightarrow \mathbb{Z}_6$ where $F([x]_3) = [x^2]_6$. \ Exercise 6.8. For each of a-g of exercise, for the ones that are well defined determine if the function is one-to-one or onto. Then for the following functions, determine if they are well defined, if so determine if they are one-to-one or onto. \qquad h. $F: \mathbb{Z}_{31} \rightarrow \mathbb{Z}_{31}$ where $F([x]_{31}) = [x + 16]_{31}$. \qquad i. $F: \mathbb{Z}_{31} \rightarrow \mathbb{Z}_{31}$ where $F([x]_{31}) = [7x + 16]_{31}$. [Hint: $gcd(7, 31) = 1$ and values for $x$ and $y$ so that $31x+7y = 1$ can be easily obtained by observing that $7\cdot 9 = 63 = 31\cdot 2 + 1$.] \qquad j. $F: \mathbb{Z}_{30} \rightarrow \mathbb{Z}_{30}$ where $F([x]_{30}) = [x + 16]_{30}$. \qquad k. $F: \mathbb{Z}_{30} \rightarrow \mathbb{Z}_{30}$ where $F([x]_{30}) = [5x + 16]_{30}$. \qquad l. $F: \mathbb{Z}_{30} \rightarrow \mathbb{Z}_{5}$ where $F([x]_{30}) = [7x + 16]_{5}$. \qquad m. $F: \mathbb{Z}_{5} \rightarrow \mathbb{Z}_{30}$ where $F([x]_{30}) = [6x + 16]_{5}$. \end{document}