API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Feb 10th, 2016
57
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 24.51 KB | None | 0 0
raw download clone embed print report
  1. \doc
  2. \textbf{Sec. 2.1}
  3.  
  4. \begin{enumerate}
  5. \item[9.] Show that each of the following formulas yields a well-defined function.
  6.  
  7. (a) $f : \mathbb{Z}_{8} \rightarrow \mathbb{Z}_{8}$ defined by $f([x]_{8}) = [mx]_{8}$ for any $m \in \mathbb{Z}$
  8.  
  9. (b) $g : \mathbb{Z}_{8} \rightarrow \mathbb{Z}_{12}$ defined by $g([x]_{8}) = [6x]_{12}$
  10.  
  11. (c) $h : \mathbb{Z}_{12} \rightarrow \mathbb{Z}_{4}$ defined by $h([x]_{12}) = [x]_{4}$
  12.  
  13. \textbf{Solution:}
  14.  
  15. (a) Let $x,y \in \mathbb{Z}$.
  16.  
  17. By the definition of a well-defined function, we know it is sufficient to show
  18.  
  19. that if $[x]_8 = [y]_8 \Rightarrow f([x]_8) = f([y]_8)$, then $f$ is well-defined.
  20.  
  21. Suppose $[x]_8 = [y]_8$. Then $x \equiv y$ (mod $8)$, so $\dfrac{x-y}{8} = k$ for some $k \in \mathbb{Z}$. Multiplying both sides by $m$ gives $\dfrac{mx-my}{8} = mk \in \mathbb{Z}$ by closure.
  22.  
  23. Thus $mx \equiv my$ (mod $8)$, so we have $[mx]_8 = [my]_8$. Therefore $f$ is well-defined. $\Box$
  24.  
  25. (b) Suppose $[x]_8 = [y]_8$. Then $x \equiv y$ (mod $8)$, so $\dfrac{x-y}{8} = k$ for some $k \in \mathbb{Z}$. Multiplying both sides by $4$ gives $\dfrac{x-y}{2} = 4k \in \mathbb{Z}$ by closure.
  26.  
  27. Multiplying by $\dfrac{6}{6}$ on the LHS gives $\dfrac{6x-6y}{12} = 4k \in \mathbb{Z}$.
  28.  
  29. Thus $6x \equiv 6y$ (mod $12)$, so we have $[6x]_{12} = [6y]_{12}$. Therefore $g$ is well-defined. $\Box$
  30.  
  31. (c) Suppose $[x]_{12} = [y]_{12}$. Then $x \equiv y$ (mod $12)$, so $\dfrac{x-y}{12} = k$ for some $k \in \mathbb{Z}$. Multiplying both sides by $3$ gives $\dfrac{x-y}{4} = 3k \in \mathbb{Z}$ by closure.
  32.  
  33. Thus $x \equiv y$ (mod $4)$, so we have $[x]_4 = [y]_4$. Therefore $h$ is well-defined. $\Box$
  34.  
  35. \bigbreak
  36.  
  37. \item[10.] In each of the following cases, give an example to show that the formula does not define a function.
  38.  
  39. (b) $g : \mathbb{Z}_{2} \rightarrow \mathbb{Z}_{5}$ defined by $g([x]_{2}) = [x]_{5}$
  40.  
  41. (d) $p : \mathbb{Z}_{12} \rightarrow \mathbb{Z}_{5}$ defined by $p([x]_{12}) = [2x]_{5}$
  42.  
  43. \textbf{Solution:}
  44.  
  45. (b) Note that $g([1]_2) = [1]_5$ and $[1]_2 = [3]_2$.
  46.  
  47. But $g([3]_2) = [3]_5$, thus $g([x]_2)$ splits outputs when $[1]_2$ and $[3]_2$ are inputs.
  48.  
  49. Therefore $g([x]_2) = [x]_5$ is not a well defined function. $\Box$
  50.  
  51. (d) Note that $p([11]_{12}) = [2\cdot 11]_5 = [22]_5 = [2]_5$ and $[11]_{12} = [23]_{12}$.
  52.  
  53. But $p([23]_{12}) = [2\cdot 23]_5 = [46]_5 = [1]_5$, thus $p([x]_{12})$ splits outputs when $[11]_{12}$ and $[23]_{12}$ are inputs.
  54.  
  55. Therefore $p([x]_{12}) = [2x]_{5}$ is not a well defined function. $\Box$
  56.  
  57. \bigbreak
  58.  
  59. \item[16.] Let $f : A \rightarrow B$ be a function. Prove that $f$ is onto if and only if there exists a function $g : B \rightarrow A$ such that $f \circ g = I_{B}$.
  60.  
  61. \textbf{Solution:}
  62.  
  63. ($\Rightarrow$) Suppose $f$ is surjective, so that the range of $f$ is equal to the codomain of $f$. Also, $f$ is a well defined function which means that for all $a \in A$, $f(a)$ produces exactly one output.
  64.  
  65. Now we can define $g$ as the function that takes $f(a) \in B$ and maps it back to $a$, or $g(f(a))=a$. If $f$ produces a collision, or $f(b)=f(c)$ for some $b,c \in A$ with $b \neq c$, then we can define $g(f(b))$ going to $b$ or $c$ in an arbitrary way but note that we do not let both $g(f(b))=b$ and $g(f(b))=c$; $g(f(b))$ and $g(f(c))$ are each equal to the same single value.
  66.  
  67. Thus, we see that if $d$ is an arbitrary element in $B$, $g(d)$ will give the pre-image of $d$ in $A$, so $f(g(d)) = f(e)$ where $e$ is a pre-image of $d$. Then by definition of a pre-image we have that $f(e) = d$. In other words, $f \circ g = I_B.$
  68.  
  69. ($\Leftarrow$) Suppose $f \circ g = I_B$, which means that for all $b \in B$, $f(g(b)) = b.$ This means that every $b$ has a pre-image in $A$ through $f$. So the range of $f$ covers all of $B$.
  70.  
  71. Therefore the codomain of $f$ is equal to the range of $f$, so $f$ is surjective. $\Box$
  72.  
  73. \bigbreak
  74.  
  75. \item[18.] Let $A$ be a nonempty set, and let $f : A \rightarrow B$ be a function. Prove that $f$ is one-to-one if and only if there exists a function $g : B \rightarrow A$ such that $g \circ f = I_{A}$.
  76.  
  77. \textbf{Solution:}
  78.  
  79. ($\Rightarrow$) Suppose $f$ is injective, meaning that if $a$ and $b$ are arbitrary elements in $A$ and $f(a) = f(b)$, then $a=b$. So $f$ maps any element in $A$ to a distinct element in $B$.
  80.  
  81. Now we still let $a$ be an arbitrary element in $A$; we can then say that $f(a) = c$ for some $c \in B$. Also, we define $g$ as the function that takes an element in $B$ and maps it to the element in $A$ for which $f$ mapped that back to $B$. So $g(c) = a.$ Note that no $c \in B$ is mapped to twice by $F$, because $f$ is injective. Thus $g$ has no splits as we defined it.
  82.  
  83. In addition, if there is any $h \in B$ such that $h$ does not have a pre-image in $A$ through $f$, then let $g(h) = d$ for some $d \in A$. Thus $g$ is a well defined function and for any $e \in A$, $f(e) = k$ for some $k \in B$ and $g(k) = e$. So we see that $g(f(e))=g(k)=e$, or $g \circ f = I_A$.
  84.  
  85.  
  86. ($\Leftarrow$) Suppose $g \circ f = I_A$, or for any $a \in A$, $g \circ f = g(f(a)=a$.
  87.  
  88. Now if for some $x,y \in A$ we see that $f(x) = f(y),$ then we can apply $g$ to both sides. Thus we see that $g(f(x))=g(f(y))$. Then $x=y$.
  89.  
  90. Hence if $f(x)=f(y)$ then $x=y$ and $f$ is injective by definition. $\Box$
  91.  
  92. \end{enumerate}
  93.  
  94. \bigbreak
  95.  
  96. \textbf{Sec. 2.2}
  97.  
  98. \begin{enumerate}
  99. \item[1.] It is shown in Theorem $2.2.7$ that if $f : S \rightarrow T$ is a function, then there is a one-to-one correspondence between the elements of $f(S)$ and the equivalence classes of $S / f$. For each of the following functions, find $f(S)$ and $S / f$ and exhibit the one-to-one correspondence between them.
  100.  
  101. (b) $g : \mathbb{Z} \rightarrow \mathbb{Z}_{12}$ given by $g(n) = [8n]_{12}$ for all $n \in \mathbb{Z}$
  102.  
  103. (d) $k : \mathbb{Z}_{12} \rightarrow \mathbb{Z}_{12}$ defined by $k([x]_{12}) = [5x]_{12}$
  104.  
  105. \textbf{Solution:}
  106.  
  107. (b) Note that $g(n) = [8n]_{12}$, so that all of the outputs will be multiples of $8$ in $\mathbb{Z}_{12}$. Also, we know that $[8n]_{12} = [r]_{12}$ when $8n = 12m+r$ for $m \in \mathbb{Z}$ and $0 \leq r < 12$.
  108.  
  109. Dividing this equation by $4$ gives $2n = 3m+\dfrac{r}{4}$, but since $2n,3m \in \mathbb{Z}$ by closure we must conclude that $\dfrac{r}{4} \in \mathbb{Z}$. Since $0 \leq r < 12$, then $r=0,4,8$.
  110.  
  111. So $g(\mathbb{Z})=\{[0]_{12}, [4]_{12}, [8]_{12}\}$.
  112.  
  113. Given that $g(\mathbb{Z})$ is a set with three equivalence classes we can designate $[0]_3$ as the set that outputs $[0]_{12}$, $[1]_3$ as the set that outputs $[8]_{12}$, and $[2]_3$ as the set that outputs $[4]_{12}$.
  114.  
  115. So we have
  116.  
  117. $[0]_{3} = \{\dots, -6, -3, 0, 3, 6, \dots\}$
  118.  
  119. $[1]_{3} = \{\dots, -5, -2, 1, 4, \dots\}$
  120.  
  121. $[2]_{3} = \{\dots, -4, -1, 2, 5, \dots\}$
  122.  
  123. giving that $\mathbb{Z} / g = \{[0]_3, [1]_3, [2]_3\}$. Note that for each class in $g(\mathbb{Z})$ there is a set in the factor class.
  124.  
  125. (d) Consider $k([x]_{12}) = [5x]_{12}$. We see that $5$ and $12$ are relatively prime, so we have
  126.  
  127. $k(\mathbb{Z}_{n}) = \{[0]_{12}, [1]_{12}, [2]_{12}, [3]_{12}, [4]_{12}, [5]_{12}, [6]_{12}, [7]_{12}, [8]_{12}, [9]_{12}, [10]_{12}, [11]_{12}\}$
  128.  
  129. To find the factor set, designate
  130.  
  131. $[[0]]_{12}, [[1]]_{12}, [[2]]_{12}, [[3]]_{12}, [[4]]_{12}, [[5]]_{12}, [[6]]_{12}, [[7]]_{12}, [[8]]_{12}, [[9]]_{12}, [[10]]_{12}, [[11]]_{12}$
  132.  
  133. to be the sets that gives those outputs respectively.
  134.  
  135. $[[0]]_{12} = \{\dots, [-24]_{12}, [-12]_{12}, [0]_{12}, [12]_{12}, [24]_{12},\dots\}$
  136.  
  137. $[[1]]_{12} = \{\dots, [-19]_{12}, [-7]_{12}, [5]_{12}, [17]_{12},\dots\}$
  138.  
  139. $[[2]]_{12} = \{\dots, [-14]_{12}, [-2]_{12}, [10]_{12}, [22]_{12},\dots\}$
  140.  
  141. $[[3]]_{12} = \{\dots, [-21]_{12}, [-9]_{12}, [3]_{12}, [15]_{12},\dots\}$
  142.  
  143. $[[4]]_{12} = \{\dots, [-16]_{12}, [-4]_{12}, [8]_{12}, [20]_{12},\dots\}$
  144.  
  145. $[[5]]_{12} = \{\dots, [-23]_{12}, [-11]_{12}, [1]_{12}, [13]_{12},\dots\}$
  146.  
  147. $[[6]]_{12} = \{\dots, [-18]_{12}, [-6]_{12}, [6]_{12}, [18]_{12},\dots\}$
  148.  
  149. $[[7]]_{12} = \{\dots, [-13]_{12}, [-1]_{12}, [11]_{12}, [23]_{12},\dots\}$
  150.  
  151. $[[8]]_{12} = \{\dots, [-20]_{12}, [-8]_{12}, [4]_{12}, [16]_{12},\dots\}$
  152.  
  153. $[[9]]_{12} = \{\dots, [-15]_{12}, [-3]_{12}, [9]_{12}, [21_{12},\dots\}$
  154.  
  155. $[[10]]_{12} = \{\dots, [-22]_{12}, [-10]_{12}, [2]_{12}, [14]_{12},\dots\}$
  156.  
  157. $[[11]]_{12} = \{\dots, [-17]_{12}, [-5]_{12}, [7]_{12}, [19]_{12},\dots\}$
  158.  
  159. This gives that
  160.  
  161. $\mathbb{Z}_{12} / k = \{[[0]]_{12}, [[1]]_{12}, [[2]]_{12}, [[3]]_{12}, [[4]]_{12}, [[5]]_{12}, [[6]]_{12}, [[7]]_{12}, [[8]]_{12}, [[9]]_{12}, [[10]]_{12}, [[11]]_{12}\}$ $\Box$
  162.  
  163. Once again the factor set has the same number of elements as $k(\mathbb{Z}_{12})$ showing a one-to-one correspondence. $\Box$
  164.  
  165. \bigbreak
  166.  
  167. \item[2.] Repeat Exercise $1$ for each of the following functions.
  168.  
  169. (b) $g : \mathbb{Z}_{24} \rightarrow \mathbb{Z}_{24}$ defined by $g([x]_{24}) = [4x]_{24}$
  170.  
  171. (d) $q : \mathbb{Z}_{24} \rightarrow \mathbb{Z}_{12}$ defined by $q([x]_{24}) = [4x]_{12}$
  172.  
  173. \textbf{Solution:}
  174.  
  175. (b) Consider $g([x]_{24}) = [4x]_{24}$. We see that all of the outputs are multiples of $4$. Furthermore, $[4x]_{24} = [r]_{24}$ when $4x = 24m+r$ for some $m \in \mathbb{Z}$ and $0 \leq r < 24$.
  176.  
  177. Dividing this equation by $4$ gives $x = 6m+\dfrac{r}{4}$, and we know $x,6m \in \mathbb{Z}$ which means $\dfrac{r}{4} \in \mathbb{Z}$. Thus $r=0,4,8,12,16,20$.
  178.  
  179. So $g(\mathbb{Z}_{24}) = \{[0]_{24}, [4]_{24}, [8]_{24}, [12]_{24}, [16]_{24}, [20]_{24}\}$.
  180.  
  181. To find the factor set, designate
  182.  
  183. $[[0]]_{24}, [[1]]_{24}, [[2]]_{24}, [[3]]_{24}, [[4]]_{24}, [[5]]_{24}$
  184.  
  185. to be the sets that give
  186.  
  187. $[0]_{24}, [4]_{24}, [8]_{24}, [12]_{24}, [16]_{24}, [20]_{24}$
  188.  
  189. as outputs, respectively.
  190.  
  191. $[[0]]_{24} = \{\dots, [-12]_{24}, [-6]_{24}, [0]_{24}, [6]_{24}, [12]_{24},\dots\}$
  192.  
  193. $[[1]]_{24} = \{\dots, [-11]_{24}, [-5]_{24}, [1]_{24}, [7]_{24},\dots\}$
  194.  
  195. $[[2]]_{24} = \{\dots, [-10]_{24}, [-4]_{24}, [2]_{24}, [8]_{24},\dots\}$
  196.  
  197. $[[3]]_{24} = \{\dots, [-9]_{24}, [-3]_{24}, [3]_{24}, [9]_{24},\dots\}$
  198.  
  199. $[[4]]_{24} = \{\dots, [-8]_{24}, [-2]_{24}, [4]_{24}, [10]_{24},\dots\}$
  200.  
  201. $[[5]]_{24} = \{\dots, [-7]_{24}, [-1]_{24}, [5]_{24}, [11]_{24},\dots\}$
  202.  
  203. Thus $\mathbb{Z}_{24} / g = \{[[0]_{24}], [[1]_{24}], [[2]_{24}], [[3]_{24}], [[4]_{24}], [[5]_{24}]\}$
  204.  
  205. And again we see the one-to-one correspondence between $g(\mathbb{Z}_{24})$ and $\mathbb{Z}_{24} / g$.
  206.  
  207. (d) Starting with $q([x]_{24}) =[4x]_{12}$, we observe that all outputs are multiples of $4$. Hence, $[4x]_{12} = [r]_{12}$ when $4x = 12m+r$ for some $m \in \mathbb{Z}$ and $0 \leq r < 12$.
  208.  
  209. Dividing this equation by $4$ gives $x = 3m+\dfrac{r}{4}$ and because $x,3m \in \mathbb{Z}$ we conclude that $\dfrac{r}{4} \in \mathbb{Z}$. Thus $r = 0,4,8$.
  210.  
  211. Therefore, $q(\mathbb{Z}_{24}) = \{[0]_{12}, [4]_{12}, [8]_{12}\}$.
  212.  
  213. To find the factor set, designate $[[0]_{24}], [[1]_{24}], [[2]_{24}]$ to be the sets that give $[0]_{12}, [4]_{12}$, and $[8]_{12}$ as outputs respectively.
  214.  
  215. $[[0]]_{24} = \{\dots, [-6]_{24}, [-3]_{24}, [0]_{24}, [3]_{24}, [6]_{24},\dots\}$
  216.  
  217. $[[1]]_{24} = \{\dots, [-5]_{24}, [-2]_{24}, [1]_{24}, [4]_{24},\dots\}$
  218.  
  219. $[[2]]_{24} = \{\dots, [-4]_{24}, [-1]_{24}, [2]_{24}, [5]_{24},\dots\}$
  220.  
  221. Thus $\mathbb{Z}_{24} / q = \{[[0]_{24}], [[1]_{24}], [[2]_{24}]\}$.
  222.  
  223. We now see that the factor set has a one-to-one correspondence with $q(\mathbb{\mathbb{Z}}_{24})$. $\Box$
  224.  
  225. \bigbreak
  226.  
  227. \item[8.] For integers $m,n$, define $m \sim n$ if and only if $n \mid m^{k}$ and $m \mid n^{j}$ for some positive \\ integers $k$ and $j$.
  228.  
  229. (a) Show that $\sim$ is an equivalence relation on $\mathbb{Z}$.
  230.  
  231. (b) Determine the equivalence classes $[1], [2], [6]$ and $[12]$.
  232.  
  233. (c) Give a characterization of the equivalence class $[m]$.
  234.  
  235. \textbf{Solution:}
  236.  
  237. (a) Let $\mathbb{Z}^+$ be the set of positive integers.
  238.  
  239. \begin{enumerate}
  240. \item[(R)] Let $a \in \mathbb{Z}$. Then $a \mid a^i$ and $a \mid a^j$ for $i,j \in \mathbb{Z}^+$. Thus for all $a \in \mathbb{Z}$, $a \sim a$ which shows that $\sim$ is reflexive.
  241.  
  242. \item[(S)] Suppose $b,c \in \mathbb{Z}$ and that $b \sim c$, giving that $c \mid b^i$ and $b \mid c^j$ for some $i,j \in \mathbb{Z}^+$.
  243.  
  244. Then $c \sim b$ because $b \mid c^i$ and $c \mid b^j$, showing that $\sim$ is symmetric.
  245.  
  246. \item[(T)] Suppose $a,b,c \in \mathbb{Z}$ and $a \sim b$, $b \sim c$. So $b \mid a^i, a \mid b^j, c \mid b^k, b \mid c^l$ for some $i,j,k,l \in \mathbb{Z}^+$.
  247.  
  248. Therefore $bm=a^i, an=b^j, ch = b^k, bg=c^l$ for some $m,n,h,g \in \mathbb{Z}$. Note that $a^{ik} = b^k m^k = chm^k = (hm^k)c$ and $ik, hm^k$ are integers by closure so we see that $c \mid a^z$ for $z=ik$. Also, $c^{lj} = b^j g^j = ang^j = (ng^j)a$. Note that $lj$ and $ng^j$ are integers by closure so $a \mid c^y$ for $y=lj$. Hence, we see that $a \sim c$ so this relation is transitive on the integers. $\Box$
  249.  
  250. \end{enumerate}
  251.  
  252. We have shown that $\sim$ is reflexive, symmetric, and transitive. Therefore $\sim$ is an equivalence relation on $\mathbb{Z}$. $\Box$
  253.  
  254. (b) $[1] = \{m \in \mathbb{Z} : m \sim 1\} = \{m \in \mathbb{Z} : 1 \mid m^k, \: m \mid 1^j\}$
  255.  
  256. We know that $1^k = 1$ for all $k$, and only $1 \mid 1$ or $-1 \mid 1$ so $m = \{\pm 1 \}$. Thus
  257.  
  258. $[1] = \{\pm 1 \}$ \\
  259.  
  260. $[2] = \{m \in \mathbb{Z} : m \sim 2\} = \{m \in \mathbb{Z} : 2 \mid m^k, \: m \mid 2^j\}$
  261.  
  262. Note that if $m$ is an even integer, then $m$ can be divided by $2^k$ for some $k \in \mathbb{Z}$. Also, any even integer to the first power is divisible by 2. Furthermore, any odd integer raised to a positive integer is still odd by closure. Thus if $m$ is odd then $2 \nmid m^j$ for $j \geq 1 \in \mathbb{Z}$. So $[2]$ contains all of the even integers with no odd integers.
  263.  
  264. $[2] = \{\dots, -4, -2, 0, 2, 4, \dots\}$ \\
  265.  
  266. $[6] = \{m \in \mathbb{Z} : m \sim 6\} = \{m \in \mathbb{Z} : 6 \mid m^k, \: m \mid 6^j\} = \{m \in \mathbb{Z} : (2\cdot 3) \mid m^k, \: m \mid (2\cdot 3)^j\}$
  267.  
  268. This means that $m$ must have $2$ and $3$ in its prime factorization, and the exponents on $2$ and $3$ are positive, so for $m \sim 6$, $m$ must be a multiple of $6$.
  269.  
  270. $[6] = \{\dots, -12, -6, 0, 6, 12, \dots\}$ \\
  271.  
  272. Note that $12 \sim 6$ because $6 \mid 12^1$ and $12 \mid 6^2$. Since this is an equivalence relation, we have
  273.  
  274. $[12] = [6]$ $\Box$ \\
  275.  
  276. (c) $[m] = \{a \in \mathbb{Z} : a \sim m\} = \{a \in \mathbb{Z} : m \mid a^k, \: a \mid m^j\}$
  277.  
  278. Now as in part $(b)$ we can see that $m \sim a$ iff each prime number of $a$'s prime factorization is in $m$'s prime factorization and each prime number of $m$'s prime factorization is in $a$'s prime factorization.
  279.  
  280. Thus, if $m = p_{1}^{b_{1}} \cdot p_{2}^{b_{2}} \cdots p_{n}^{b_{n}}$ for $p_i$ being distinct prime numbers
  281.  
  282. and $b_i \geq 1 \in \mathbb{Z}$ for $i = 1, 2, \dots, n,$ we have
  283.  
  284. $[m] = \{a \in \mathbb{Z} : a = \pm p_{1}^{c_{1}} \cdot p_{2}^{c_{2}} \cdots p_{n}^{c_{n}}, \: c_i \geq 1 \in \mathbb{Z}\}$ $\Box$
  285.  
  286. \bigbreak
  287.  
  288. \item[12.] Let $T = \{(x,y,z) \in \mathbb{R}^3 \mid (x,y,z) \neq (0,0,0)\}$. Define $\sim$ on $T$ by $(x_1, y_1, z_1) \sim (x_2, y_2, z_2)$ if there exists a nonzero real number $\lambda$ such that $x_1 = \lambda x_2$, $y_1 = \lambda y_2$, and $z_1 = \lambda z_2$.
  289.  
  290. (a) Show that $\sim$ is an equivalence relation on $T$.
  291.  
  292. (b) Give a geometric description of the equivalence class of $(x,y,z)$.
  293.  
  294. \textbf{Solution:}
  295.  
  296. (a)
  297. \begin{enumerate}
  298.  
  299. \item[(R)] Let $(x,y,z) \in T$. So $x = \lambda x$, $y = \lambda y$, and $z = \lambda z$. We let $\lambda = 1$ and observe that $(x,y,z) \sim (x,y,z)$, so $\sim$ is reflexive on $T$.
  300.  
  301. \item[(S)] Let $(x,y,z),(x_1,y_1,z_1) \in T$ and $(x,y,z) \sim (x_1,y_1,z_1)$. Thus $x = \lambda x_1$, $y = \lambda y_1$, and $z = \lambda z_1$ and since at least one element of each ordered triple is nonzero, we see that $\lambda$ cannot be zero. Hence, $x_1 = \dfrac{1}{\lambda}x$, $y_1 = \dfrac{1}{\lambda}y$, $z_1 = \dfrac{1}{\lambda}z$. Now for $\lambda_1 = \dfrac{1}{\lambda}$ we have $x_1 = \lambda_1x$, $y_1 = \lambda_1y$, $z_1 = \lambda_1z$. So $(x_1,y_1,z_1) \sim (x,y,z)$ showing that $\sim$ is symmetric on $T$.
  302.  
  303. \item[(T)] Let $(x,y,z),(x_1,y_1,z_1),(x_2,y_2,z_2) \in T$ with $(x,y,z) \sim (x_1,y_1,z_1)$ and
  304.  
  305. $(x_1,y_1,z_1) \sim (x_2,y_2,z_2)$. So $x = \lambda x_1$, $y = \lambda y_1$, $z = \lambda z_1$, $x_1 = \lambda_1 x_2$, $y_1 = \lambda_1 y_2$, and $z_1 = \lambda_1 z_2$.
  306.  
  307. By substitution we see that $x= \lambda \lambda_1 x_2, y = \lambda \lambda_1 y_2$, and $z = \lambda \lambda_1 z_2$. Note that $\lambda \lambda_1 \in \mathbb{R}$. Therefore $(x,y,z) \sim (x_2,y_2,z_2)$ which shows that $\sim$ is transitive on $T$.
  308.  
  309. \end{enumerate}
  310.  
  311. We have shown that $\sim$ is reflexive, symmetric, and transitive on $T$. Therefore $\sim$ is an equivalence relation on $T$. $\Box$
  312.  
  313. (b) Take any $(x,y,z) \in T$ and then plot this point in the $3$-space Cartesian plane. Create a line from the origin (but not including the origin) to the point $(x,y,z)$. Now extend this line to magnitude $\infty$ in both directions.
  314.  
  315. We see that the equivalence class of $(x,y,z)$ consists of all the points that fall on the line that was just created. Once again, the origin is not included. $\Box$
  316.  
  317. \end{enumerate}
  318.  
  319. \bigbreak
  320.  
  321. \textbf{Sec. 2.3}
  322.  
  323. \begin{enumerate}
  324. \item[3.] Write $\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 3 & 4 & 10 & 5 & 7 & 8 & 2 & 6 & 9 & 1 \end{pmatrix}$ as a product of disjoint cycles and as a product of transpositions. Construct its associated diagram, find its inverse, and find its order.
  325.  
  326. \textbf{Solution:}
  327.  
  328. If we look at the given permutation we can easily convert it to cycle notation by starting with $1$ and looking at what $1$ maps to, and then what element that mapped to, etc...
  329.  
  330. If a cycle ends before we have covered every element, we will start a new cycle with the next lowest number not yet mapped to. Note that a cycle ends when it starts to repeat. So we have \\
  331.  
  332. $\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 3 & 4 & 10 & 5 & 7 & 8 & 2 & 6 & 9 & 1 \end{pmatrix} = (1 \: 3 \: 10)(2 \: 4 \: 5 \: 7)(6 \: 8)$ \\
  333.  
  334. This permutation in cycle notation shows each element only in one cycle, so it is displayed as a product of disjoint cycles.
  335.  
  336. Now by using Proposition $2.3.10$ from our textbook we can write this product of disjoint cycles as a product of transpositions. \\
  337.  
  338. $(1 \: 3 \: 10)(2 \: 4 \: 5 \: 7)(6 \: 8) = (1 \: 3)(3 \: 10)(2 \: 4)(4 \: 5)(5 \: 7)(6 \: 8)$ \\
  339.  
  340. The permutation is now expressed as a product of transpositions.
  341.  
  342. Now we can look at the original permutation in cycle notation and switch the order of the elements in each disjoint cycle to get the permutation's inverse. \\
  343.  
  344. $[(1 \: 3 \: 10)(2 \: 4 \: 5 \: 7)(6 \: 8)]^{-1} = (1 \: 10 \: 3)(2 \: 7 \: 5 \: 4)(6 \: 8)$ \\
  345.  
  346. Since this permutation consists of $3$ disjoint cycles of length $4,3,2$, we see that the least common multiple of the lengths of these cycles is $12$ so the order of this permutation is $12$.
  347.  
  348. The permutation can be represented by the following diagrams.
  349.  
  350. \begin{tikzpicture}[->,scale=.7]
  351. \node (1) at (90:1cm) {$1$};
  352. \node (3) at (-30:1cm) {$3$};
  353. \node (10) at (210:1cm) {$10$};
  354.  
  355. \draw (70:1cm) arc (70:-10:1cm);
  356. \draw (-50:1cm) arc (-50:-130:1cm);
  357. \draw (190:1cm) arc (190:110:1cm);
  358. \end{tikzpicture}
  359.  
  360. \begin{tikzpicture}[->,scale=.7]
  361. \node (2) at (90:1cm) {$2$};
  362. \node (7) at (0:1cm) {$7$};
  363. \node (5) at (-90:1cm) {$5$};
  364. \node (4) at (180:1cm) {$4$};
  365.  
  366. \draw (70:1cm) arc (70:20:1cm);
  367. \draw (-20:1cm) arc (-20:-70:1cm);
  368. \draw (-110:1cm) arc (-110:-160:1cm);
  369. \draw (160:1cm) arc (160:110:1cm);
  370. \end{tikzpicture}
  371.  
  372. \begin{tikzpicture}[->,scale=.7]
  373. \node (6) at (90:1cm) {$6$};
  374. \node (8) at (-90:1cm) {$8$};
  375.  
  376. \draw (70:1cm) arc (70:-70:1cm);
  377. \draw (-110:1cm) arc (-110:-250:1cm);
  378. \end{tikzpicture}
  379.  
  380. \begin{tikzpicture}[->,scale=.7]
  381. \node (9) at (90:1cm) {$9$};
  382.  
  383. \draw (70:1cm) arc (70:-250:1cm);
  384. \end{tikzpicture}
  385.  
  386. \bigbreak
  387.  
  388. \item[12.] Prove that $(a \: b)$ cannot be written as a product of two cycles of length three.
  389.  
  390. \textbf{Solution:}
  391.  
  392. Suppose that $(a \: b)$ can be written as a product of two cycles of length three. So we have $(a \: b) = (c \: d \: e)(f \: g \: h)$ for $c,d,e,f,g,h$ as valid elements in the cycle.
  393.  
  394. We get
  395.  
  396. \begin{align*}
  397. (a \: b) &= (c \: d \: e)(f \: g \: h) \\
  398. &= (c \: d)(d \: e)(f \: g \: h) \\
  399. &= (c \: d)(d \: e)(f \: g)(g \: h) \\
  400. \end{align*}
  401.  
  402. Note that both sides of this equation are now written as products of transpositions. Hence, we see that the LHS is an odd permutation but the RHS is even. Therefore we have a contradiction because an odd permutation cannot equal an even permutation, meaning that our original assumption is false and this means that $(a \: b)$ cannot be written as a product of two cycles of length three. $\Box$
  403.  
  404. \bigbreak
  405.  
  406. \item[13.] Let $\tau \in S_n$ be the cycle $(1,2,\ldots,k)$ of length $k$, where $k \leq n$.
  407.  
  408. (a) Prove that if $\sigma \in S_n,$ then $\sigma \tau \sigma^{-1} = (\sigma(1), \sigma(2), \ldots, \sigma(k))$. Thus $\sigma \tau \sigma^{-1}$ is a \\ cycle of length $k$.
  409.  
  410. (b) Let $\rho$ be any cycle of length $k$. Prove that there exists a permutation $\sigma \in S_n$ such that $\sigma \tau \sigma^{-1} = \rho$.
  411.  
  412. \textbf{Solution:}
  413.  
  414. (a)
  415.  
  416. (b) Suppose $\rho$ is any cycle of length $k$ in $S_n$. We know that $\tau = (1 \: 2 \: \dots \: k)$ of cycle length $k$. In addition, $\rho = (a_1 \: a_2 \: \dots \: a_k)$ is any cycle of length $k$ in $S_n$. By part (a) we know $\sigma \tau \sigma^{-1} = (\sigma(1) \: \sigma(2) \: \dots \: \sigma(k))$ which is also a cycle of length $k$.
  417.  
  418. Now if we define $\sigma$ such that $\sigma(i) = a_i$ for $i = 1, 2, \dots, k$, we finally see that $\sigma \tau \sigma^{-1} = (\sigma(1) \: \sigma(2) \: \dots \: \sigma(k)) = (a_1 \: a_2 \: \dots \: a_k) = \rho.$
  419.  
  420. \bigbreak
  421.  
  422. \item[15.] For $\alpha, \beta \in S_n$, let $\alpha \sim \beta$ iff there exists $\sigma \in S_n$ such that $\sigma \alpha \sigma^{-1} = \beta$. Show that $\sim$ is an equivalence relation on $S_n$.
  423.  
  424. \textbf{Solution:}
  425.  
  426. \begin{enumerate}
  427.  
  428. \item[(R)] Let $\alpha \in S_n$ and $I_n$ be the identity permutation on $S_n$ with the inverse of $I_n$ as ${I_n}^{-1}$ and $I_n {I_n}^{-1} = I_n$. Observe that $I_n = {I_n}^{-1}.$
  429.  
  430. Note that $I_n \alpha {I_n}^{-1} = \alpha$. So for any $\alpha \in S_n$, $\alpha \sim \alpha$ which shows that $\sim$ is reflexive on $S_n$.
  431.  
  432. \item[(S)] Let $a,b \in S_n$ such that $a \sim b$, which means there exists a $\sigma, \sigma^{-1} \in S_n$ such that $\sigma \alpha \sigma^{-1} = b$. Note that $I_n$ is the identity permutation on $S_n$.
  433.  
  434. We then have
  435.  
  436. \begin{align*}
  437. \sigma \alpha \sigma^{-1} \sigma &= b \sigma \\
  438. \sigma \alpha I_n &= b \sigma \\
  439. \sigma^{-1} \sigma \alpha &= \sigma^{-1} b \sigma \\
  440. I_n \alpha &= \sigma^{-1} b \sigma \\
  441. \alpha &= \sigma^{-1} b \sigma \\
  442. \end{align*}
  443.  
  444. If we now define $\beta = \sigma^{-1}$ then $\beta^{-1} = \sigma$. So we can see that $\alpha = \beta b \beta^{-1}$ and $\beta, \beta^{-1} \in S_n$, which shows that $b \sim a$ and hence $\sim$ is symmetric on $S_n$.
  445.  
  446. \item[(T)] Let $a,b,c \in S_n$ such that $a \sim b$ and $b \sim c$.
  447.  
  448. This implies that there exists $\sigma, \sigma_1, \sigma^{-1}, {\sigma_1}^{-1}$ such that $\sigma a \sigma^{-1} = b$ and $\sigma_1 b {\sigma_1}^{-1} = c$.
  449.  
  450. Thus $b = {\sigma_1}^{-1} c \sigma_1$ and by substitution we get \\
  451.  
  452. \begin{align*}
  453. \sigma a \sigma^{-1} &= {\sigma_1}^{-1} c \sigma_1 \\
  454. \sigma a \sigma^{-1} \sigma &= {\sigma_1}^{-1} c \sigma_1 \sigma \\
  455. \sigma^{-1} \sigma a I_n &= \sigma^{-1} {\sigma_1}^{-1} c \sigma_1 \sigma \\
  456. I_n a I_n &= \sigma^{-1} {\sigma_1}^{-1} c \sigma_1 \sigma \\
  457. a &= \sigma^{-1} {\sigma_1}^{-1} c \sigma_1 \sigma \\
  458. \end{align*}
  459.  
  460. Now we say $\sigma_1 \sigma = \beta$. Then by the in-class exercise 2.3A, we have that $\beta^{-1} = \sigma^{-1} {\sigma_1}^{-1}$, so $a = \beta^{-1} c \beta$. Lastly, let $\alpha = \beta^{-1}$ and $\alpha^{-1} = \beta$ giving that $\alpha c \alpha^{-1} = a$ and $\alpha, \alpha^{-1} \in S_n$. This shows that $c \sim a$ and by symmetry $a \sim c$, which means $\sim$ is transitive on $S_n$.
  461.  
  462. \end{enumerate}
  463.  
  464. We have shown that $\sim$ is reflexive, symmetric, and transitive on $S_n$. Therefore $\sim$ is an equivalence relation on $S_n$. $\Box$
  465.  
  466. \end{enumerate}
  467.  
  468. \vspace{.3in}
  469.  
  470. (\underline{\textbf{Note:}} Our group collaborated with Groups 2 and 4 during office hours in order to finalize the exercises from Sec. 2.2, 8. and Sec. 2.3, 13. This should explain any similarities between solutions on each of our assignments.)
  471.  
  472. \end{document}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!