From 18a1af1b1fbc5ae3572e011b267caa7bef293f62 Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Fri, 29 Apr 2022 18:54:17 -0400 Subject: added all new homework for Neha's class --- gupta/Makefile | 2 +- gupta/hw10.tex | 240 ++++++++++++++++++++++++++++++++++++++++ gupta/hw11.tex | 134 ++++++++++++++++++++++ gupta/hw12.tex | 88 +++++++++++++++ gupta/hw6.tex | 227 ++++++++++++++++++++++++++++++++++++++ gupta/hw7.tex | 294 +++++++++++++++++++++++++++++++++++++++++++++++++ gupta/hw8.tex | 312 ++++++++++++++++++++++++++++++++++++++++++++++++++++ gupta/hw9.tex | 192 ++++++++++++++++++++++++++++++++ gupta/portfolio.tex | 288 ++++++++++++++++++++++++++++++++++++++++++++++++ 9 files changed, 1776 insertions(+), 1 deletion(-) create mode 100644 gupta/hw10.tex create mode 100644 gupta/hw11.tex create mode 100644 gupta/hw12.tex create mode 100644 gupta/hw6.tex create mode 100644 gupta/hw7.tex create mode 100644 gupta/hw8.tex create mode 100644 gupta/hw9.tex create mode 100644 gupta/portfolio.tex (limited to 'gupta') diff --git a/gupta/Makefile b/gupta/Makefile index 1188bc9..2adfb32 100644 --- a/gupta/Makefile +++ b/gupta/Makefile @@ -7,7 +7,7 @@ PDFLATEX = pdflatex .tex.pdf: $(PDFTEX) $< -all: hw1.pdf hw2.pdf hw3.pdf hw4.pdf hw5.pdf +all: hw1.pdf hw2.pdf hw3.pdf hw4.pdf hw5.pdf hw6.pdf hw7.pdf hw8.pdf hw9.pdf hw10.pdf hw11.pdf hw12.pdf portfolio.pdf clean: rm -f *.pdf *.log *.aux diff --git a/gupta/hw10.tex b/gupta/hw10.tex new file mode 100644 index 0000000..20a0a33 --- /dev/null +++ b/gupta/hw10.tex @@ -0,0 +1,240 @@ +\newfam\bbold +\def\bb#1{{\fam\bbold #1}} +\font\bbten=msbm10 +\font\bbsev=msbm7 +\font\bbfiv=msbm5 +\textfont\bbold=\bbten +\scriptfont\bbold=\bbsev +\scriptscriptfont\bbold=\bbfiv +\font\bigbf=cmbx12 at 24pt + +\def\answer{\smallskip{\bf Answer.}\par} +\def\endproof{\leavevmode\hskip\parfillskip\vrule height 6pt width 6pt +depth 0pt{\parfillskip0pt\medskip}} +\let\endanswer\endproof +\def\section#1{\vskip18pt plus 6pt minus 6pt\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in% +\noindent{\bf #1}} +\let\impl\to +\def\nmid{\hskip-3pt\not\hskip2.5pt\mid} +\def\problem#1{\bigskip\par\penalty-100\item{#1}} + +\headline{\vtop{\hbox to \hsize{\strut Math 2106 - Dr. Gupta\hfil Due Thursday +2022-04-07 at 11:59 pm}\hrule height .5pt}} + +\centerline{\bigbf Homework 10 - Holden Rohrer} +\bigskip + +\noindent{\bf Collaborators:} None + +\section{Judson 3.5: 2, 7, 14, 28, 13, 35, 45, 48} + +\problem{2.} +Which of the following multiplication tables defined on the set $G = +\{a,b,c,d\}$ form a group? Support your answer in each case. + +\answer + +$(a)$ is not a group because it does not have an identity element. + +$(b)$ is a group because it has an identity element ($a$), and every +element has an inverse (itself), and I have verified it is associative. % prove later + +$(c)$ is a group because it has an identity element ($a$), and every +element has an inverse ($(a,b,c,d)\mapsto(a,d,c,b)$). I have also +verified that this multiplication table is associative. + +$(d)$ is not a group because it has an identity element ($a$), but $d$ +has no inverse. + +\endanswer + +\problem{7.} +Let $S = \bb R\setminus \{-1\}$ and define a binary operation on $S$ by +$a*b = a+b+ab.$ Prove that $(S,*)$ is an abelian group. + +\answer +This group has identity $0$ because $a*0 = a+0+0a = a.$ +Every element has an inverse $-{a\over a+1}$ which is defined because +$a\neq -1,$ so $a+1\neq 0.$ $$-{a\over a+1}*a = -{a\over a+1} + a - +{a^2\over a+1} = {a^2+a\over a+1} - {a\over a+1} - {a^2\over a+1} = 0.$$ +The operation is also associative. $a*b = (a+1)(b+1),$ so +$$(a*b)*c = (a+1)(b+1)(c+1) = a*(b*c).$$ +\endanswer + +\problem{14.} +Given the groups $\bb R^*$ and $\bb Z,$ let $G = \bb R^* \times \bb Z.$ +Define a binary operation $\circ$ on $G$ by +$(a,m)\circ (b,n) = (ab, m+n).$ +Show that $G$ is a group under this operation. + +\answer +This operation is associative because multiplication and addition are +associative, so $((a,m)\circ (b,n)) \circ (c,l) = (a,m)\circ ((b,n)\circ +(c,l)) = (abc,m+n+l).$ + +The element $(a,m)$ has inverse $(1/a,-m),$ and the group has identity +$(1,0).$ +\endanswer + +\problem{28.} +Prove the remainder of Proposition 3.21: if $G$ is a group and +$a,b\in G,$ then the equation $xa = b$ has a unique solution in $G.$ + +\answer +By definition of the group $a$ has an inverse $a^{-1}\in G,$ so +multiplying the right side by $a^{-1}$ gives +$$xaa^{-1} = xe = x = ba^{-1}.$$ +\endanswer + +\problem{31.} + +Show that if $a^2 = e$ for all elements $a$ in a group $G,$ then $G$ +must be abelian. + +\answer +Let $G$ be a group such that $g^2 = e$ for all elements $g\in G.$ +We will show that $G$ is abelian. +Let $a,b\in G.$ We will show that $ab = ba.$ +$$ab = eabe = bbabaa = b(ba)(ba)a = ba.$$ +\endanswer + +\problem{35.} + +Find all the subgroups of the symmetry group of an equilateral triangle. + +\answer +We have the trivial subgroup $\langle e\rangle,$ the rotation subgroup +$\langle \rho_1 \rangle,$ the reflection subgroups $\langle +\mu_1\rangle,$ $\langle\mu_2\rangle,$ $\langle\mu_3\rangle,$ and the +group $G.$ +\endanswer + +\problem{45.} + +Prove that the intersection of two subgroups of a group $G$ is also a +subgroup of $G.$ + +\answer +Let $H$ and $I$ be two subgroups of $G.$ +We will show that $H\cap I$ is a subgroup by showing the three +conditions. + +Let $a,b\in H\cap I.$ We will show that $ab\in H\cap I.$ +From definition of $a,b,$ we know that $a,b\in H,$ so $ab\in H.$ +Similarly, $a,b\in I,$ so $ab\in I.$ +By definition of $H$ and $I$ as subgroups, $a^{-1}\in I,$ and $a^{-1}\in +H,$ so $a^{-1}\in I\cap H.$ +Finally, because $I$ and $H$ are subgroups, $e\in I$ and $e\in H,$ so +$e\in H\cap I.$ + +Therefore, $ab\in H\cap I,$ and $H\cap I$ is a subgroup. +\endanswer + +\problem{48.} + +Let $G$ be a group and $g\in G.$ Show that +$$Z(G) = \{x\in G: gx = xg\hbox{ for all }g\in G\}$$ +is a subgroup of $G.$ This subgroup is called the center of $G.$ + +\answer +To show that this is a subgroup, we need to show that $x,y\in Z(G)$ +implies $xy\in Z(G),$ that $x^{-1}\in Z(G),$ and that $e\in Z(G).$ + +Let $x,y\in Z(G)$ and $z\in G.$ We already know that $xy\in G,$ so we +will show that $xyz = zxy.$ +Because $y\in Z(G),$ $yz = zy.$ +Similarly, because $x\in Z(G),$ $x(yz) = (zy)x,$ so $xyz = zxy.$ +We have shown that $Z(G)$ is closed under group operations. + +We will also show that since $xz = zx,$ we have $x^{-1}z = zx^{-1}.$ +We left multiply and right multiply by $x^{-1}$ to get +$$x^{-1}xzx^{-1} = x^{-1}zxx^{-1} \to zx^{-1} = x^{-1}z.$$ + +$e\in Z(G)$ because $eg = g = ge.$ + +We have now shown that $Z(G)$ is a subgroup. +\endanswer + +\section{Judson 4.5: 2a-c, 5, 23} + +\problem{2a-c.} +Find the order of each of the following elements: (a) $5\in\bb Z_{12},$ +(b) $\sqrt 3\in\bb R,$ and (c) $\sqrt 3\in\bb R^*.$ + +\answer +\item{a.} +Because 5 is coprime to 12, the order of this element is 12. + +\item{b.} +This element has infinite order. + +\item{c.} +This element has infinite order. +\endanswer + +\problem{5.} +Find the order of every element in $\bb Z_{18}.$ +\answer +The coprime elements $\{1,5,7,11,13,17\}$ have order 18. + +The elements $\{2,4,8,10,14,16\}$ have order 9. + +The elements $\{3,9,15\}$ have order 6. + +The elements $\{6,12\}$ have order 3. + +The element $9$ has order 2. + +And the element $0$ has order 1. +\endanswer + +\problem{23.} +Let $a,b\in G.$ Prove the following statements. + +\item{a.} The order of $a$ is the same as the order of $a^{-1}.$ + +\answer +Let $a$ be an element of order $n.$ +This means $a^m \neq e$ for $1\leq m < n,$ but $a^n = e.$ +By definition of inverses, $(a^{-1})^n a^n = e \to (a^{-1})^n = e.$ +Similarly, $(a^{-1})^m a^m = e.$ +Where $1\leq m < n,$ we have $a^m \neq e.$ +We assume for the sake of contradiction $(a^{-1})^m = e.$ +We would obtain $a^m = e$ giving a contradiction, so +$(a^{-1})^m \neq e,$ and $a^{-1}$ is order $n.$ + +\endanswer + +\item{b.} For all $g\in G,$ $|a| = |g^{-1}ag|.$ + +\answer + +We will show that $|a| = |g^{-1}ag|.$ +Thus, we will show $(g^{-1}ag)^n = e$ if and only if $a^n = e.$ + +$(\Rightarrow)$ + +Let $a^n = e.$ +$$(g^{-1}ag)^n = g^{-1}a^ng = g^{-1}g = e.$$ + +$(\Leftarrow)$ + +Let $(g^{-1}ag)^n = g^{-1}a^ng = e.$ +This implies $g^{-1}a^n = g^{-1},$ so $a^n = e.$ + +\endanswer + +\item{c.} The order of $ab$ is the same as the order of $ba.$ + +\answer + +To show that $|ab| = |ba|,$ we will show that $(ab)^n = e$ if and only +if $(ba)^n = e.$ +WLOG, we will show that $(ab)^n = e$ only if $(ba)^n = e.$ + +Let $(ab)^n = e.$ +$$(ab)^{n+1} = (ab)^n(ab) = ab = a(ba)^nb \Longrightarrow (ba)^n = e.$$ + +\endanswer + +\bye diff --git a/gupta/hw11.tex b/gupta/hw11.tex new file mode 100644 index 0000000..c2b2b7f --- /dev/null +++ b/gupta/hw11.tex @@ -0,0 +1,134 @@ +\newfam\bbold +\def\bb#1{{\fam\bbold #1}} +\font\bbten=msbm10 +\font\bbsev=msbm7 +\font\bbfiv=msbm5 +\textfont\bbold=\bbten +\scriptfont\bbold=\bbsev +\scriptscriptfont\bbold=\bbfiv +\font\bigbf=cmbx12 at 24pt + +\def\answer{\smallskip{\bf Answer.}\par} +\def\endproof{\leavevmode\hskip\parfillskip\vrule height 6pt width 6pt +depth 0pt{\parfillskip0pt\medskip}} +\let\endanswer\endproof +\def\section#1{\vskip18pt plus 6pt minus 6pt\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in% +\noindent{\bf #1}} +\let\impl\to +\def\nmid{\hskip-3pt\not\hskip2.5pt\mid} +\def\problem#1{\bigskip\par\penalty-100\item{#1}} + +\headline{\vtop{\hbox to \hsize{\strut Math 2106 - Dr. Gupta\hfil Due Thursday +2022-04-14 at 11:59 pm}\hrule height .5pt}} + +\centerline{\bigbf Homework 11 - Holden Rohrer} +\bigskip + +\noindent{\bf Collaborators:} None + +\section{Judson 5.4: 1b, 2c, 2p, 3a, 3c, 24} + +\problem{1b.} + +Write the following permutation in cycle notation: +$$\pmatrix{1&2&3&4&5\cr 2&4&1&5&3}.$$ + +\answer +This is $(1 2 4 5 3).$ +\endanswer + +\problem{2c.} + +Compute $(1 4 3)(2 3)(2 4).$ + +\answer +$$\pmatrix{1&2&3&4\cr 2&3&1&4}$$ +\endanswer + +\problem{2p.} + +Compute $[(1 2 3 5)(4 6 7)]^{-1}.$ + +\answer +$$\pmatrix{1&2&3&4&5&6&7\cr 5&1&2&7&3&4&6}$$ +\endanswer + +\problem{3a.} +Express the following permutation as a product of transpositions and +identify it as even or odd: $(1 4 3 5 6).$ + +\answer +$$(1 4 3 5 6) = (1 4)(4 3)(3 5)(5 6),$$ +and since there are 4 transpositions, this is an even permutation. +\endanswer + +\problem{3c.} + +Express the following permutation as a product of transpositions and +identify it as even or odd: $(1 4 2 6)(1 4 2).$ + +\answer +$$(1 4 2 6)(1 4 2) = (1 4)(4 2)(2 6)(1 4)(4 2),$$ +and since there are 5 transpositions, this is an odd permutation. + +\problem{24.} + +Show that a 3-cycle is an even permutation. + +\answer +Let us have a 3-cycle $(a_1 a_2 a_3).$ +This can be written as $(a_1 a_2)(a_2 a_3)$ because $a_2$ ends in the +position of $a_3,$ $a_1$ ends in the position of $a_2,$ and $a_3$ ends +in the position of $a_1.$ +This is two transpositions, so this is an even permutation. +\endanswer + +\section{Judson 6.5: 5d, 5b} + +\problem{5d.} + +List the left and right cosets of the subgroups of $A_4$ in $S_4.$ + +\answer +The left and right cosets are $\{A_4, (1\,2)A_4\}.$ +\endanswer + +\problem{5b.} + +List the left and right cosets of the subgroups of $\langle 3\rangle$ in +$U(8).$ + +\answer +$\langle 3\rangle = \{{\rm id}, 3\},$ and since this group is abelian, +it has the same left and right cosets. +$5\langle 3\rangle = \{5, 7\},$ and this completes the partition of the +group. +\endanswer + +\section{Problem not from the textbook} + +\problem{1.} + +Let $H$ be a subgroup of $G$ and suppose that $g_1,g_2\in G.$ +Prove that $g_1H = g_2H$ if and only if $g_2\in g_1H.$ + +\answer +Let $H$ be a subgroup of $G$ and $g_1,g_2\in G.$ +We will show that $g_1H = g_2H$ if and only if $g_2\in g_1H.$ + +$(\Rightarrow)$ + +Let $g_1H = g_2H.$ +We will show that $g_2\in g_1H.$ + +$e\in H,$ so $g_2e = g_2\in g_2H,$ and by equality, $g_2\in g_1H.$ + +$(\Leftarrow)$ + +Let $g_2 \in g_1H.$ +This means there is $h\in H$ such that $g_2 = g_1h.$ +We then know that $g_2H = g_1hH = g_1H$ because $hH = H$ by group +closure. + +\endanswer +\bye diff --git a/gupta/hw12.tex b/gupta/hw12.tex new file mode 100644 index 0000000..5ae4d54 --- /dev/null +++ b/gupta/hw12.tex @@ -0,0 +1,88 @@ +\newfam\bbold +\def\bb#1{{\fam\bbold #1}} +\font\bbten=msbm10 +\font\bbsev=msbm7 +\font\bbfiv=msbm5 +\textfont\bbold=\bbten +\scriptfont\bbold=\bbsev +\scriptscriptfont\bbold=\bbfiv +\font\bigbf=cmbx12 at 24pt + +\def\answer{\smallskip{\bf Answer.}\par} +\def\endproof{\leavevmode\hskip\parfillskip\vrule height 6pt width 6pt +depth 0pt{\parfillskip0pt\medskip}} +\let\endanswer\endproof +\def\section#1{\vskip18pt plus 6pt minus 6pt\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in% +\noindent{\bf #1}} +\let\impl\to +\def\nmid{\hskip-3pt\not\hskip2.5pt\mid} +\def\problem#1{\bigskip\par\penalty-100\item{#1}} + +\headline{\vtop{\hbox to \hsize{\strut Math 2106 - Dr. Gupta\hfil Due Thursday +2022-04-26 at 11:59 pm}\hrule height .5pt}} + +\centerline{\bigbf Homework 12 - Holden Rohrer} +\bigskip + +\noindent{\bf Collaborators:} None + +\section{Ross Chapter 2, 8.1d, 8.2c, 8.7b} + +\problem{8.1d} Prove that $\lim {n+6\over n^2-6} = 0.$ + +\answer +Let $\epsilon > 0.$ +We will show $N$ such that for all $n>N,$ $|{n+6\over n^2-6}-0| < +\epsilon.$ + +Where $n>6,$ +$$|{n+6\over n^2-6}| = {n+6\over n^2-6},$$ +and $n^2-6>n^2-36,$ so +$${n+6\over n^2-6} < {n+6\over n^2-36} = {1\over n-6}.$$ +Choosing $n > N = 6+1/\epsilon,$ and since $n-6 > N-6,$ +$${1\over n-6} < {1\over N-6} = {1\over 6+1/\epsilon-6} = {1\over +1/\epsilon} = \epsilon,$$ +showing that $\lim {n+6\over n^2-6} = 0.$ +\endanswer + +\problem{8.2c} Find the limit of $c_n = {4n+3\over 7n-5}$ and then prove +your claim. + +\answer + +$c_n$ converges to $4/7.$ + +Let $\epsilon > 0.$ +For all +$$n > N = {41\over 49\epsilon} + {5\over 7},$$ +we can show that $|c_n-4/7| < \epsilon.$ +$$|c_n-4/7| = \left|{4n+3\over 7n-5}-{4\over 7}\right| = \left|{28n+21 - +(28n-20)\over 49n-35}\right| = \left|{41\over 49n-35}\right|,$$ +and from $n > N,$ (and where $N\geq 1$) $49n-35 > 49N-35 > 0,$ so +$$\left|{41\over 49n-35}\right| > {41\over 49N-35} = +{41\over 49({41\over 49\epsilon}+{5\over 7})-35} = +{41\over {41\over\epsilon} + 35-35} = +{41\epsilon\over 41} = \epsilon.$$ +We have now shown that $\lim c_n = 4/7.$ + +\endanswer + +\problem{8.7b} Show that $s_n = (-1)^n n$ does not converge. + +\answer +{\bf Disproof.} + +Assume for the sake of contradiction that $s_n$ converges to $s.$ +Let $\epsilon = 1.$ +We must have $N$ such that for all $n>N,$ $|s_n-s| < 1$ (implying also +$|s_{n+1}-s| < 1$). +However, +$$|s_n-s_{n+1}| = |s_n-s+s-s_{n+1}| \leq |s_n-s| + |s_{n+1}-s| < 1 + 1 = +2.$$ +Yet, $|s_{n+1}-s_n| = |(-1)^n(-(n+1)-n)| = 2n+1,$ +and where $n>1,$ we obtain $2n+1>3$ and from the earlier inequality +$2n+1<2,$ completing a contradiction. +We have then shown that $s_n$ does not converge. +\endanswer + +\bye diff --git a/gupta/hw6.tex b/gupta/hw6.tex new file mode 100644 index 0000000..4362d26 --- /dev/null +++ b/gupta/hw6.tex @@ -0,0 +1,227 @@ +\newfam\bbold +\def\bb#1{{\fam\bbold #1}} +\font\bbten=msbm10 +\font\bbsev=msbm7 +\font\bbfiv=msbm5 +\textfont\bbold=\bbten +\scriptfont\bbold=\bbsev +\scriptscriptfont\bbold=\bbfiv +\font\bigbf=cmbx12 at 24pt + +\def\answer{\smallskip{\bf Answer.}\par} +\def\endproof{\leavevmode\hskip\parfillskip\vrule height 6pt width 6pt +depth 0pt{\parfillskip0pt\medskip}} +\let\endanswer\endproof +\def\section#1{\medskip\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in% +\noindent{\bf #1}} +\let\impl\to +\def\nmid{\hskip-3pt\not\hskip2.5pt\mid} +\def\problem#1{\par\penalty-100\item{#1}} + +\headline{\vtop{\hbox to \hsize{\strut Math 2106 - Dr. Gupta\hfil Due Thursday +2022-02-17 at 11:59 pm}\hrule height .5pt}} + +\centerline{\bigbf Homework 6 - Holden Rohrer} +\bigskip + +\noindent{\bf Collaborators:} None + +\section{Hammack 10: 4, 8, 20, 26} +Prove the following statements with either induction, strong induction, +or proof by smallest counterexample. + +\problem{4.} If $n\in\bb N,$ then $1\cdot 2 + 2\cdot 3 + 3\cdot 4 + +4\cdot 5 + \cdots + n(n+1) = {n(n+1)(n+2)\over 3}.$ + +\answer +We will show that $\sum_{k=1}^n k(k+1) = {n(n+1)(n+2)\over 3}$ by +induction. + +For the case $n = 1,$ $1\cdot 2 = {1(1+1)(1+2)\over 3} = 6/3 = 2.$ + +In the inductive case, assume that this statement is true for some $n +\geq 1,$ giving +$$\sum_{k=1}^n k(k+1) = {n(n+1)(n+2)\over 3}.$$ +We will show that this statement is true for $n+1:$ +$$\sum_{k=1}^{n+1} k(k+1) = {(n+1)(n+2)(n+3)\over 3}.$$ +This is true only if +$$\sum_{k=1}^{n+1} k(k+1) - \sum_{k=1}^n k(k+1) = (n+1)(n+2) = +{(n+1)(n+2)(n+3)\over 3} - {n(n+1)(n+2)\over 3}.$$ + +$${(n+1)(n+2)(n+3)\over 3} - {n(n+1)(n+2)\over 3} = +{(n+3-n)(n+1)(n+2)\over 3} = (n+1)(n+2),$$ +thus proving the statement for $n+1.$ + +Therefore, this identity is true for all $j\in\bb N.$ +\endanswer + +\problem{8.} If $n\in\bb N,$ then ${1\over 2!} + {2\over 3!} + {3\over +4!} + \cdots + {n\over (n+1)!} = 1 - {1\over (n+1)!}$ + +\answer +We will show this statement for all $n\in\bb N$ by induction. + +In the base case $n = 1,$ ${1\over 2!} = 1/2 = 1 - {1\over 2!},$ so the +statement is true. + +In the inductive case, assume that the statement is true for some $n\geq +1.$ We will show the statement for $n+1:$ +$${1\over 2!} + {2\over 3!} + \cdots + {n+1\over (n+2)!} = 1 - {1\over +(n+2)!}.$$ +Then, +$$1-{1\over (n+2)!} = 1-{n+2\over(n+2)!}+{n+1\over (n+2)!} = 1-{1\over +(n+1)!} + {n+1\over (n+2)!}.$$ +By the inductive hypothesis, +$$1-{1\over (n+1)!} + {n+1\over (n+2)!} = {1\over 2!} + {2\over 3!} + +\cdots + {n\over (n+1)!} + {n+1\over (n+2)!},$$ +proving our inductive step. + +Therefore, for all $j\in\bb N,$ this identity is true. +\endanswer + +\problem{20.} Prove that $(1+2+3+\cdots+n)^2 = 1^3 + 2^3 + 3^3 + \cdots ++ n^3$ for every $n\in\bb N.$ + +\answer +We will show this identity for all $n\in\bb N$ by induction. + +In the base case, $1^2 = 1^3,$ so the statement is immediate. + +In the inductive case, assume $(1+2+3+\cdots+k)^2 = 1^3 + 2^3 + 3^3 + +\cdots + k^3$ for some $k\in\bb N.$ +We will show that $(1+2+3+\cdots+k+(k+1))^2 = 1^3 + 2^3 + 3^3 + \cdots + +(k+1)^3.$ + +$$(1+2+\cdots+k+(k+1))^2 = (1+2+\cdots+k)^2 + 2(1+2+\cdots+k)(k+1) + +(k+1)^2.$$ +With the result $1+2+\cdots+k = {k(k+1)\over 2},$ +we get this equal to +$$(1+2+\cdots+k)^2 + k(k+1)(k+1) + 1(k+1)^2,$$ +and from the inductive hypothesis, this is equal to +$$1^3 + 2^3 + \cdots + k^3 + k(k+1)(k+1) + 1(k+1)^2 = 1^3 + 2^3 + \cdots ++ k^3 + (k+1)^3.$$ + +We have thus proven that for any $n\in\bb N,$ $(1+2+3+\cdots+n)^2 = 1^3 ++ 2^3 + 3^3 + \cdots + n^3.$ +\endanswer + +\problem{26.} Concerning the Fibonacci sequence, prove that +$\sum_{k=1}^n F_k^2 = F_nF_{n+1}.$ + +\answer +We will show this identity, for all $n\in\bb Z$ s.t. $n\geq 1,$ by +induction. + +For $n=1,$ $F_1^2 = 1 = F_1F_2.$ + +Assume for some $n\geq 1,$ $\sum_{k=1}^n F_k^2 = F_nF_{n+1}.$ +We will show the statement for $n+1:$ +$$\sum_{k=1}^{n+1} F_k^2 = F_{n+1}F_{n+2}.$$ +We get the following from the definition of the Fibonacci numbers above +2: +$$F_{n+1}F_{n+2} = F_{n+1}(F_n + F_{n+1}) = F_{n+1}^2 + F_{n+1}F_n,$$ +and from our inductive hypothesis, +$$F_{n+1}^2 + F_{n+1}F_n = F_{n+1}^2 + \sum_{k=1}^n F_k^2 = +\sum_{k=1}^{n+1} F_k^2,$$ +completing our inductive step. + +This shows that for all $j\in\bb Z,$ where $j\geq 1,$ +$$\sum_{k=1}^j F_k^2 = F_jF_{j+1}.$$ +\endanswer + +\section{Hammack 11.1: 4, 14, 15} + +\problem{4.} +Let $A = \{a,b,c,d\}.$ Suppose $R$ is the relation +$$\vbox{\halign{&\quad$#$\quad\cr + R&=&\{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(a,c),(c,a),\cr + &&(a,d),(d,a),(b,c),(c,b),(b,d),(d,b),(c,d),(d,c)\}\cr +}}$$ +Is R Reflexive? Symmetric? Transitive? If a property does not hold, say +why. + +\answer +This is reflexive, symmetric, and transitive. +\endanswer + +\problem{14.} +Suppose $R$ is symmetric and transitive relation on set $A,$ and there +is an element $a\in A$ for which $aRx$ for every $x\in A.$ Prove that +$R$ is reflexive. + +\answer +For every $x\in A,$ $aRx$ is given and $xRa$ by symmetry. By +transitivity, $xRx$ for every element, so the relationship is reflexive. +\endanswer + +\problem{15.} Prove or disprove: if a relation is symmetric and +transitive, then it is also reflexive. + +\answer +The empty relation $\emptyset$ is vacuously symmetric and transitive but +on a nonempty set containing $x,$ the empty relation doesn't contain +$(x,x).$ +\endanswer + +\section{Hammack 11.2: 6, 8, 10, 12} + +\problem{6.} Let $A = \{1,2,3,4,5,6\},$ and consider the following +equivalence relation on $A:$ $$R = +\{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(2,3),(3,2),(4,5),(5,4),(4,6), +(6,4),(5,6),(6,5)\}.$$ +List the equivalence classes of $R.$ + +\answer +The equivalence classes are $\{2,3\},$ $\{4,5,6\},$ and $\{1\}.$ +\endanswer + +\problem{8.} Define a relation $R$ on $\bb Z$ as $xRy$ if and only if +$x^2+y^2$ is even. Prove $R$ is an equivalence relation. Describe its +equivalence classes. + +\answer +$R$ is reflexive, symmetric, and transitive, so it is an equivalence +relation. +The relation is reflexive because $x^2 + x^2 = 2(x^2),$ and $x^2\in\bb +Z,$ so the sum is even. +The relation is symmetric because $x^2 + y^2 = y^2 + x^2,$ so the left +side is even if and only if the right side is even. +And for some $j,k\in\bb Z,$ $xRy$ and $yRz$ implies $x^2+y^2 = 2j$ and +$y^2+z^2 = 2k,$ so $x^2 + y^2 + y^2 + z^2 - 2y^2 = x^2 + z^2 = +2(j+k-y^2).$ +The number $j+k-y^2\in\bb Z,$ so $xRz,$ and the relation is transitive. + +The equivalence classes are the even numbers and the odd numbers. +\endanswer + +\problem{10.} Suppose $R$ and $S$ are two equivalence relations on a set +$A.$ Prove that $R\cap S$ is also an equivalence relation. + +\answer +The equivalence relations $R$ and $S$ on $A$ are, by definition, +reflexive, symmetric, and transitive. +$R\cap S$ is therefore reflexive because $x\in A$ implies $(x,x)\in R$ +and $(x,x)\in S,$ (by reflection), so $(x,x)\in R\cap S.$ + +Only if $xRy$ and $xSy,$ $x(R\cap S)y,$ and by symmetry, $yRx$ and +$ySx,$ so $y(R\cap S)x,$ giving symmetry of the new relation. + +Similarly, if $x(R\cap S)y$ and $y(R\cap S)z,$ $xRy$ and $xRz,$ so by +transitivity, $xRz,$ and similarly, $xSz,$ so $x(R\cap S)z,$ making the +intersection of any equivalence relations also an equivalence relation. +\endanswer + +\problem{12.} Prove or disprove: If $R$ and $S$ are two equivalence +relations on a set $A,$ then $R\cup S$ is also an equivalence relation +on $A.$ + +\answer +{\bf Disproof.} + +Let $R$ be a relation with equivalence classes $\{1,2\}, \{3\}$ and $S$ +be a relation with equivalence classes $\{1\}, \{2,3\}.$ $\{(1,2), +(2,3)\} \subseteq R\cup S,$ but $(1,3)\not\in R\cup S$ because +$1\mathbin{\not\hskip-3pt R} 3$ and $1\mathbin{\not\hskip-2pt S} 3.$ +\endanswer + +\bye diff --git a/gupta/hw7.tex b/gupta/hw7.tex new file mode 100644 index 0000000..231e3fd --- /dev/null +++ b/gupta/hw7.tex @@ -0,0 +1,294 @@ +\newfam\bbold +\def\bb#1{{\fam\bbold #1}} +\font\bbten=msbm10 +\font\bbsev=msbm7 +\font\bbfiv=msbm5 +\textfont\bbold=\bbten +\scriptfont\bbold=\bbsev +\scriptscriptfont\bbold=\bbfiv +\font\bigbf=cmbx12 at 24pt + +\def\answer{\smallskip{\bf Answer.}\par} +\def\endproof{\leavevmode\hskip\parfillskip\vrule height 6pt width 6pt +depth 0pt{\parfillskip0pt\medskip}} +\let\endanswer\endproof +\def\section#1{\medskip\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in% +\noindent{\bf #1}} +\let\impl\to +\def\nmid{\hskip-3pt\not\hskip2.5pt\mid} +\def\problem#1{\par\penalty-100\item{#1}} + +\headline{\vtop{\hbox to \hsize{\strut Math 2106 - Dr. Gupta\hfil Due Thursday +2022-03-03 at 11:59 pm}\hrule height .5pt}} + +\centerline{\bigbf Homework 7 - Holden Rohrer} +\bigskip + +\noindent{\bf Collaborators:} None + +\section{Hammack 11.3: 2, 4} + +\problem{2.} +List all the partitions of the set $A = \{a,b,c\}.$ Compare your answer +to the answer to Exercise 6 of Section 11.2 +\answer +All partitions are $\{\{\{a,b,c\}\}, \{\{a,b\},\{c\}\}, +\{\{a\},\{b,c\}\}, \{\{b\}, \{a,c\}\}, \{\{a\},\{b\},\{c\}\}\}.$ +There is exactly one of these for each of the equivalence relations on +exercise 6. +\endanswer + +\problem{4.} +Suppose $P$ is a partition of set $A.$ Define a relation $R$ on $A$ by +declaring $xRy$ if and only if $x, y \in X$ for some $X\in P.$ Prove $R$ +is an equivalence relation on $A.$ +Then prove that $P$ is the set of equivalence classes of $R.$ +\answer +We want to show that $R$ is an equivalence relation. We will show that +it is reflexive, symmetric, and transitive. + +\smallskip +(Reflexive) + +Let $a\in A.$ We will show that $aRa.$ +$P$ is a partition of $A,$ so $\bigcup_{p\in P} p = A,$ and so there +must be $X\in A$ s.t. $a,a\in X.$ +We thus obtain $aRa.$ + +\smallskip +(Symmetric) + +Let $a,b\in A$ such that $aRb.$ We will show that $bRa.$ +From the definition of $R,$ there is $X\in P$ s.t. $a\in X$ and $b\in +X.$ +Since $b,a\in X,$ $bRa.$ + +\smallskip +(Transitive) +Let $a,b,c\in A$ such that $aRb$ and $bRc.$ We will show tht $aRc.$ +From the definition of $R,$ there are $X,Y\in P$ s.t. $a,b\in X$ and +$b,c\in Y,$ but if we assume $X\neq Y,$ since $P$ is a partition, $X\cap +Y = \emptyset,$ so either $b\not\in X$ or $b\not\in Y,$ so we must know +that $X = Y.$ +Therefore, $c\in X,$ ($a,c\in X$) and $aRc.$ + +\medskip +We also want to show that the equivalence classes of $R$ is $P.$ +Let $Q$ be the equivalence classes of $R,$ defined as +$\{\{x\in A: xRa\} : a\in A\}.$ +We will show that $P = Q.$ + +\smallskip +$(Q\subseteq P)$ + +Let $a\in A.$ +By definition of $Q,$ $X = \{x\in A: xRa\} \in Q.$ +$xRa$ iff $x,a\in Y$ for some $Y\in P.$ + +We will show that $X\subseteq Y$ and $Y\subseteq X$ to show that $X = +Y$ and thus $X\in P.$ + +$x\in X$ gives $xRa,$ so $x\in Y,$ so $X\subseteq Y.$ +$x\in Y$ gives $xRa,$ so $x\in X,$ and $Y\subseteq X.$ +Therefore, $X = Y,$ and we have shown $Q\subseteq P.$ + +\smallskip +$(Q\supseteq P)$ + +Let $a\in A.$ +As established earlier, for some $X\in P,$ the element $a\in X,$ and +$xRa$ iff $x\in X,$ so $X = \{x\in A: xRa\} \in Q,$ proving $P\subseteq +Q.$ + +We have now shown that $R$ is an equivalence relation and the +equivalence classes of $R$ is $P.$ + +\endanswer + +\section{Hammack 11.4: 4, 6} + +\problem{4.} +Write the addition and multiplication tables for $\bb Z_6.$ +\answer + +{\tabskip5pt +\line{\hfil +\vbox{\halign{&\strut $#$\cr + \times &[0]&[1]&[2]&[3]&[4]&[5]\cr + [0] &[0]&[0]&[0]&[0]&[0]&[0]\cr + [1] &[0]&[1]&[2]&[3]&[4]&[5]\cr + [2] &[0]&[2]&[4]&[0]&[2]&[4]\cr + [3] &[0]&[3]&[0]&[3]&[0]&[3]\cr + [4] &[0]&[4]&[2]&[0]&[4]&[2]\cr + [5] &[0]&[5]&[4]&[3]&[2]&[1]\cr +}} +\hfil +\vbox{\halign{&\strut $#$\cr + + &[0]&[1]&[2]&[3]&[4]&[5]\cr + [0]&[0]&[1]&[2]&[3]&[4]&[5]\cr + [1]&[1]&[2]&[3]&[4]&[5]&[0]\cr + [2]&[2]&[3]&[4]&[5]&[0]&[1]\cr + [3]&[3]&[4]&[5]&[0]&[1]&[2]\cr + [4]&[4]&[5]&[0]&[1]&[2]&[3]\cr + [5]&[5]&[0]&[1]&[2]&[3]&[4]\cr +}}\hfil +}} +\endanswer + +\problem{6.} +Suppose $[a],[b]\in\bb Z_6,$ and $[a]\cdot[b]=[0].$ Is it necessarily +true that either $[a] = [0]$ or $[b]=[0]?$ + +\answer +No, it isn't. $[4],[3]\in\bb Z_6,$ and $[4]\neq [0]$ and $[3]\neq [0],$ +but $[4]\cdot[3]=[12]=[0].$ +\endanswer + +\section{Hammack 12.1: 4, 6, 9, 12} + +\problem{4.} +There are eight different functions $f: \{a,b,c\}\to\{0,1\}.$ List them +all. Diagrams will suffice. +\answer +$\{(a,0), (b,0), (c,0)\}$ + +$\{(a,0), (b,0), (c,1)\}$ + +$\{(a,0), (b,1), (c,0)\}$ + +$\{(a,0), (b,1), (c,1)\}$ + +$\{(a,1), (b,0), (c,0)\}$ + +$\{(a,1), (b,0), (c,1)\}$ + +$\{(a,1), (b,1), (c,0)\}$ + +$\{(a,1), (b,1), (c,1)\}$ + +\endanswer + +\problem{6.} +Suppose $f: \bb Z \to \bb Z$ is defined as $f = \{(x,4x+5) : x\in\bb +Z\}.$ State the domain, codomain and range of $f.$ Find $f(10).$ +\answer +The domain and codomain are $\bb Z,$ and the range is $\{4x+5 : x\in\bb +Z\}.$ +$f(10) = 45.$ +\endanswer + +\problem{9.} +Consider the set $f=\{(x^2,x), x\in\bb R\}.$ Is this a function from +$\bb R$ to $\bb R?$ Explain. +\answer +$(1,-1)\in f,$ and $(1,1)\in f,$ so this is not a function because it +has multiple outputs for one input. +\endanswer + +\problem{12.} +Is the set $\theta = \{\left((x,y),(3y,2x,x+y)\right) : x,y\in\bb R\}$ a +function? If so, what is its domain, codomain, and range? +\answer +The domain is $\bb R^2,$ the codomain is $\bb R^3,$ and the range is +$\{(3y,2x,x+y) : x,y\in\bb R\} = \{(x,y,z)\in\bb R^3 : 6z-3y-2x = 0\}.$ +\endanswer + +\section{Hammack 12.2: 4, 12, 14} + +\problem{4.} +A function $f: \bb Z \to \bb Z \times \bb Z$ is defined as $f(n) = (2n, +n+3).$ Verify whether this function is injective and whether it is +surjective. +\answer +This function is injective but not surjective. + +\smallskip +(Injective) + +Let $m,n\in\bb Z$ such that $f(n)=f(m)$ or $(2n,n+3)=(2m,m+3).$ +Therefore, $2n=2m \to n = m.$ + +\smallskip +(Surjective) + +$(0, 4) \not\in f(\bb Z),$ so this function is not surjective. + +\endanswer + +\problem{12.} +Consider the function $\theta:\{0,1\}\times\bb N \to \bb Z$ defined as +$\theta(a,b) = a-2ab+b.$ Is $\theta$ injective? Is it surjective? +Bijective? Explain. +\answer + +\smallskip +(Injective) + +Let $a,c\in\{0,1\}$ and $b,d\in\bb N$ such that $\theta(a,b) = +\theta(c,d).$ We will show that $a=c$ and $b=d.$ +We will deal with three cases: + +($a=1$ and $c=1$) + +$\theta(1,b) = 1-2b+b = 1-2d+d = \theta(1,d).$ +The equality $1-2b+b = 1-2d+d$ becomes $b = d,$ showing that the +function is injective. + +($a=0$ and $c=0$) + +$\theta(0,b) = b = d = \theta(0,d),$ easily showing that $b=d$ and the +function is injective. + +(WLOG, $a=1$ and $c=0$) + +$\theta(1,b) = 1-2b+b = d = \theta(0,d).$ +With $b,d\in\bb Z,$ $b+d \geq 2,$ so the rearranged equation +$1 = b+d$ is impossible. + +\smallskip +(Surjective) + +Let $n\in\bb Z.$ We will show that for some $a\in\{0,1\}$ and $b\in\bb +N,$ $\theta(a,b) = n.$ +We will deal with two cases: + +($n > 0$) + +Let $a = 0$ and $b = n.$ +$\theta(0,n) = 0-2(0)(n)+n = n.$ + +($n \leq 0$) + +Let $a = 1$ and $b = -n+1.$ +$\theta(1, -n+1) = 1-2(1)(-n+1) + (-n+1) = 1+2n-2-n+1 = n.$ + +Because $\theta$ is both injective and surjective, it is bijective. +\endanswer + +\problem{14.} +Consider the function $\theta: {\cal P}(\bb Z) \to {\cal P}(\bb Z)$ +defined as $\theta(X) = \bar X.$ Is $\theta$ injective? Is it +surjective? Bijective? Explain. +\answer + +$\theta$ is injective and surjective. + +\smallskip +(Injective) + +Let $X$ and $Y$ be subsets of $\bb Z$ such that $\theta(X) = \theta(Y).$ +$\bar X = \bar Y$ implies $\bar{\bar X} = +\bar{\bar Y}$ and $X = Y.$ + +\smallskip +(Surjective) + +Let $X$ be a subset of $\bb Z.$ $\bar X$ maps through $\theta$ to +$X.$ $\theta(\bar X) = \bar{\bar X} = X.$ + +We have shown that $\theta$ is injective, surjective, and, therefore, +bijective. + +\endanswer + +\bye diff --git a/gupta/hw8.tex b/gupta/hw8.tex new file mode 100644 index 0000000..400ab7b --- /dev/null +++ b/gupta/hw8.tex @@ -0,0 +1,312 @@ +\newfam\bbold +\def\bb#1{{\fam\bbold #1}} +\font\bbten=msbm10 +\font\bbsev=msbm7 +\font\bbfiv=msbm5 +\textfont\bbold=\bbten +\scriptfont\bbold=\bbsev +\scriptscriptfont\bbold=\bbfiv +\font\bigbf=cmbx12 at 24pt + +\def\answer{\smallskip{\bf Answer.}\par} +\def\endproof{\leavevmode\hskip\parfillskip\vrule height 6pt width 6pt +depth 0pt{\parfillskip0pt\medskip}} +\let\endanswer\endproof +\def\section#1{\vskip18pt plus 6pt minus 6pt\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in% +\noindent{\bf #1}} +\let\impl\to +\def\nmid{\hskip-3pt\not\hskip2.5pt\mid} +\def\problem#1{\bigskip\par\penalty-100\item{#1}} + +\headline{\vtop{\hbox to \hsize{\strut Math 2106 - Dr. Gupta\hfil Due Thursday +2022-03-17 at 11:59 pm}\hrule height .5pt}} + +\centerline{\bigbf Homework 8 - Holden Rohrer} +\bigskip + +\noindent{\bf Collaborators:} None + +\section{Hammack 12.4: 2, 4, 6, 8} + +\problem{2.} Suppose $A = \{1,2,3,4\},$ $B = \{0,1,2\},$ $C=\{1,2,3\}.$ +Let $f: A\to B$ be +$$f = \left\{(1,0), (2,1), (3,2), (4,0) \right\},$$ +and $g: B\to C$ be $g = \left\{(0,1),(1,1),(2,3)\right\}.$ Find +$g\circ f.$ + +\answer + +$g\circ f = \left\{(0,0), (1,0), (2,2)\right\}.$ + +\endanswer + +\problem{4.} Suppose $A = \{a,b,c\}.$ Let $f: A\to A$ be the function $f += \left\{(a,c), (b,c), (c,c)\right\},$ and let $g: A\to A$ be the +function $g = \left\{(a,a), (b,b), (c,a)\right\}.$ Find $g\circ f$ and +$f\circ g.$ + +\answer + +$g\circ f = \left\{(a,a), (b,a), (c,a)\right\},$ and $f\circ g = +\left\{(a,c), (b,c), (c,c)\right\}.$ + +\endanswer + +\problem{6.} Consider the functions $f,g: \bb R\to \bb R$ defined as +$f(x) = {1\over x^2+1}$ and $g(x) = 3x+2.$ Find the formulas for $g\circ +f$ and $f\circ g.$ + +\answer + +$f\circ g = {1\over (3x+2)^2+1}$ and $g\circ f = {3\over x^2+1}+2.$ + +\endanswer + +\problem{8.} Consider the functions $f,g: \bb Z\times \bb Z \to \bb +Z\times \bb Z$ defined as $f(m,n) = (3m-4n, 2m+n)$ and $g(m,n) = (5m+n, +m).$ Find the formulas for $g\circ f$ and $f\circ g.$ + +\answer + +$g\circ f = (3m-4(5m+n), 2m+n)$ and $f\circ g = (5(2m+n)+(3m-4n), 2m+n).$ + +\section{Hammack 12.5: 6, 8} + +\problem{6.} +The function $f: \bb Z\times\bb Z \to \bb Z\times\bb Z$ defined by the +formula $f(m,n) = (5m+4n,4m+3n)$ is bijective. Find its inverse. + +\answer +$f(m,n) = (r,s) = (5m+4n,4m+3n).$ Thus, $4r-5s = n$ and $4s-3r = m,$ +so the inverse is $g(r,s) = (4r-5s, 4s-3r).$ +\endanswer + +\problem{8.} Is the function $\theta: {\cal P}(\bb Z)\to {\cal P}(\bb +Z)$ defined as $\theta(X) = \overline X$ bijective? If so, what is its +inverse? + +\answer +Yes, $\theta$ is bijective. This was proven in the last homework. + +The inverse $\theta^{-1}$ is $\theta$ since $\theta(\theta(X)) = X.$ +\endanswer + +\section{Hammack 12.6: 6, 7, 8, 12, 14} + +\problem{6.} Given a function $f: A\to B$ and a subset $Y\subseteq B,$ +is $f(f^{-1}(Y)) = Y$ always true? Prove or give a counterexample. + +\answer +Let $f: \bb R\to\bb R$ be $f(x) = 1.$ $f(f^{-1}(\{2\})) = f(\emptyset) = +\emptyset \neq \{2\}.$ +\endanswer + +\problem{7.} Given a function $f: A\to B$ and subsets $W,X\subseteq A,$ +prove $f(W\cap X)\subseteq f(W)\cap f(X).$ + +\answer +Let there be a function $f: A\to B$ and subsets $W, X\subseteq A.$ +Let $b\in f(W\cap X).$ We will show that $b\in f(W)\cap f(X)$ to show +that $f(W\cap X)\subseteq f(W)\cap f(X).$ +From the definition of image, there is $a\in W\cap X$ s.t. $b = f(a).$ +Since $a\in W,$ $b \in f(W),$ and from $a\in X,$ $b\in f(X).$ +Therefore, $b\in f(W)\cap f(X).$ +\endanswer + +\problem{8.} Given a function $f: A\to B$ and subsets $W,X\subseteq A,$ +then $f(W\cap X) = f(W)\cap f(X)$ is false in general. Produce a +counterexample. + +\answer +Let $W = \{1\}$ and $X = \{2\},$ and $f(x) = 0.$ +We have $W\cap X = \emptyset,$ so $f(W\cap X) = \emptyset.$ +However, $f(W) = f(W) = \{0\} = f(W)\cap f(X).$ +This disproves $f(W\cap X) = f(W)\cap f(X)$ in general. +\endanswer + +\problem{12.} Consider $f: A\to B.$ Prove that $f$ is injective if and +only if $X = f^{-1}(f(X))$ for all $X\subseteq A.$ Prove that $f$ is +surjective if and only if $f(f^{-1}(Y)) = Y$ for all $Y\subseteq B.$ + +\answer + +Let $f: A\to B.$ We will show that $f$ is injective if and only if $X = +f^{-1}(f(X))$ for all $X\subseteq A.$ + + +\smallskip +$(\Rightarrow)$ + +We will show this by contraposition. +Let there be $X\in A$ such that $f^{-1}(f(X)) \neq X.$ +We will show that $f$ is not injective by showing that for some $x, y\in +A,$ where $x\neq y,$ $f(x) = f(y).$ + +For all $x\in X,$ we have $y = f(x) \in f(X)$ and $f(x) = y,$ so $x\in +f^{-1}(f(X)),$ +Therefore, we know there is $z\not\in X$ such that $z\in f^{-1}(f(X)).$ +Therefore, $f(z) \in f(X),$ and for some $w\in X,$ $f(z) = f(w),$ and +$w\neq z,$ so $f$ is not injective. + +\smallskip +$(\Leftarrow)$ + +Assume that for all $X\subseteq A,$ $f^{-1}(f(X)) = X.$ +We will show that $f$ is injective. +Let $x,y\in A$ such that $f(x) = f(y).$ +We will show that $x = y.$ + +From $f(x) = f(y),$ we know $f(\{x\}) = f(\{y\}),$ so $f^{-1}(f(\{x\})) += \{x\} = \{y\} = f^{-1}(f(\{y\})),$ +so $x = y.$ + + +\medskip +We will now show that $f$ is surjective if and only if $f(f^{-1}(Y)) = +Y$ for all $Y\subseteq B.$ + +\smallskip +$(\Rightarrow)$ + +Let $f$ be surjective. +Let $Y\subseteq B.$ +We will show that $f(f^{-1}(Y)) = Y.$ + +Since $f$ is surjective, for all $y\in Y,$ there is $x\in A$ such that +$f(x) = y,$ so $f(f^{-1}(Y)) \supseteq Y.$ +Also, for all $z\in f(f^{-1}(Y)),$ we know $z = f(x)$ where $f(x) = y$ +for some $y\in Y.$ +From these, $z = y \in Y,$ so $f(f^{-1}(Y)) \subseteq Y$ and therefore +$f(f^{-1}(Y)) = Y.$ + +\smallskip +$(\Leftarrow)$ + +Assume that for all $Y\subseteq B,$ $f(f^{-1}(Y)) = Y.$ +We will show that $f$ is surjective. +To show that $f$ is surjective, we take $b\in B$ and show that we have +$a\in A$ such that $f(a) = b.$ + +$f(f^{-1}(\{b\})) = \{b\},$ and $f^{-1}(\{b\})$ is not empty because if +it were, $f(f^{-1}(\{b\})) = f(\emptyset) = \emptyset \neq \{b\}.$ +Therefore, we pick $a\in f^{-1}(\{b\})$ and note that $f(a) = b,$ so $f$ +is surjective. + +\endanswer + +\problem{14.} Let $f: A\to B$ be a function, and $Y\subseteq B.$ Prove +or disprove: $f^{-1}(f(f^{-1}(Y))) = f^{-1}(Y).$ + +\answer +Let $f: A\to B$ be a function, and $Y\subseteq B.$ +We will show that $f^{-1}(f(f^{-1}(Y))) = f^{-1}(Y).$ + +$(\subseteq)$ + +Let $x\in f^{-1}(f(f^{-1}(Y))).$ +We will show that $x\in f^{-1}(Y).$ + +From definition of preimage, $f(x) \in f(f^{-1}(Y)),$ and from +definition of image, $x\in f^{-1}(Y).$ + +$(\supseteq)$ + +Let $x\in f^{-1}(Y).$ +We will show that $x\in f^{-1}(f(f^{-1}(Y))).$ + +From definition of preimage, for some $y\in Y,$ $f(x) = y,$ and +$y\in f(f^{-1}(Y)).$ +And thus we have $x\in f^{-1}(f(f^{-1}(Y))).$ +We have shown that $f^{-1}(f(f^{-1}(Y))) = f^{-1}(Y).$ + +\endanswer + +\section{Hammack 13.1: 2, 6, 14} + +\problem{2.} Show that sets $\bb R$ and $(\sqrt 2,\infty)$ have equal +cardinality by describing a bijection from one to the other. + +\answer +Let $f: \bb R \to (\sqrt 2,\infty)$ be $f(x) = e^x+\sqrt 2.$ We will +show that $f$ is surjective, injective, and therefore bijective. + +\smallskip +(Injective) + +Let $x,y\in\bb R$ such that $f(x) = f(y).$ We will show that $x = y.$ +$e^x+\sqrt 2 = e^y+\sqrt 2,$ so $e^x = e^y,$ and $x = y.$ +We have shown that $f$ is injective. + +\smallskip +(Surjective) + +Let $y\in (\sqrt 2,\infty).$ +We will show there exists $x\in\bb R$ such that $f(x) = y.$ +We set $x$ to $\ln(y-\sqrt2),$ and obtain $f(x) = +e^{\ln(y-\sqrt2)}+\sqrt2 = y-\sqrt2+\sqrt2 = y.$ +We have shown that $f$ is surjective. + +We now know that $f$ is bijective. +\endanswer + +\problem{6.} Show that sets $\bb N$ and $S = \{{\sqrt 2\over n}: n\in\bb +N\}$ have equal cardinality by describing a bijection from one to the +other. + +\answer +Let $f: \bb N \to S$ be defined $f(n) = {\sqrt 2\over n}.$ + +\smallskip +(Injective) + +Let $m,n\in\bb N$ such that $f(m) = f(n).$ +We will show that $m = n.$ +We obtain ${\sqrt2\over m} = {\sqrt 2\over n},$ and thus $m = n.$ +We have shown that $f$ is injective. + +\smallskip +(Surjective) + +Let $s\in S.$ +We will show that there exists $n\in\bb N$ so that $f(n) = s.$ +By definition of $S,$ we know that there is $m\in\bb N$ such that $s = +{\sqrt 2\over m}.$ +Letting $n = m,$ we have $f(n) = {\sqrt 2\over n} = s.$ +We have shown that $f$ is surjective. + +We now know that $f$ is bijective. +\endanswer + +\problem{14.} Show that sets $\bb N\times\bb N$ and $S=\{(n,m)\in\bb +N\times\bb N : n\leq m\}$ have equal cardinality by describing a +bijection from one to the other. + +\answer +Let us have $f:\bb N\times\bb N\to S$ defined as $f(n,m) = (n, n+m-1).$ +We will show that $f$ is bijective by showing that $f$ is injective and +surjective. +This will show that $|\bb N\times\bb N| = |S|.$ + +\smallskip +(Injective) + +Let $(n,m), (k,l)\in\bb N\times\bb N$ such that $f(n,m) = f(k,l).$ +$(n, n+m-1) = (k, k+l-1) \to n = k, n+m-1 = k+l-1.$ +Substituting $n = k$ into the latter constraint, $m = l.$ +Thus, $(n,m) = (k,l),$ and $f$ is injective. + +\smallskip +(Surjective) + +Let $(n,m)\in S.$ +$(n, m-n+1)\in \bb N\times \bb N$ because $n\in\bb N$ from definition of +$S$ and $n\leq m\to 1\leq m-n+1$ (and integer closure). + +$$f(n, m-n+1) = (n, n+(m-n+1)-1) = (n,m),$$ +so $f$ is surjective. + +We now know that $f$ is bijective. + +\endanswer + +\bye diff --git a/gupta/hw9.tex b/gupta/hw9.tex new file mode 100644 index 0000000..161e2a1 --- /dev/null +++ b/gupta/hw9.tex @@ -0,0 +1,192 @@ +\newfam\bbold +\def\bb#1{{\fam\bbold #1}} +\font\bbten=msbm10 +\font\bbsev=msbm7 +\font\bbfiv=msbm5 +\textfont\bbold=\bbten +\scriptfont\bbold=\bbsev +\scriptscriptfont\bbold=\bbfiv +\font\bigbf=cmbx12 at 24pt + +\def\answer{\smallskip{\bf Answer.}\par} +\def\endproof{\leavevmode\hskip\parfillskip\vrule height 6pt width 6pt +depth 0pt{\parfillskip0pt\medskip}} +\let\endanswer\endproof +\def\section#1{\vskip18pt plus 6pt minus 6pt\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in% +\noindent{\bf #1}} +\let\impl\to +\def\nmid{\hskip-3pt\not\hskip2.5pt\mid} +\def\problem#1{\bigskip\par\penalty-100\item{#1}} + +\headline{\vtop{\hbox to \hsize{\strut Math 2106 - Dr. Gupta\hfil Due Thursday +2022-03-17 at 11:59 pm}\hrule height .5pt}} + +\centerline{\bigbf Homework 8 - Holden Rohrer} +\bigskip + +\noindent{\bf Collaborators:} None + +\section{Hammack 13.2: 4, 6, 8, 13} + +\problem{4.} +Prove that the set of all irrational numbers is uncountable. +(Suggestion: consider proof by contradiction using Theorems 13.4 and +13.6) + +\answer +Theorem 13.4 tells us that the rationals are a countably infinite set. +Assume for the sake of contradiction that the irrational numbers are +countable. +By definition of the irrational numbers, the union of the rationals and +irrationals are the real numbers. +By theorem 13.6, the real numbers must then be a countable set. +However, we know that $\bb R$ is uncountably infinite, giving a +contradiction. +Therefore, the irrational numbers are uncountable. +\endanswer + +\problem{6.} +Prove or disprove: There exists a bijective function $f: \bb Q\to\bb +R.$ + +\answer +{\bf Disproof.} + +By the textbook, $\bb Q$ is countably infinite, so we have a bijection +$g: \bb N\to \bb Q.$ +For the sake of contradiction, assume there exists a bijective function +$f: \bb Q\to \bb R.$ + +We now have a bijection $g\circ f:\bb N\to \bb R,$ because the +composition of bijections is bijective. +However, this function cannot be surjective because we can construct a +real number $r$ not in the image of $g\circ f$ by setting the $i$th +digit of $r$ to be different from the $i$th digit of $g(f(i))$ (e.g. by +choosing 0 unless the $i$th digit of $g(f(i))$ is 0). +We have reached a contradiction, so $f$ must not exist. + +\endanswer + +\problem{8.} +Prove or disprove: The set $\bb Z\times\bb Q$ is countably infinite. + +\answer +{\bf Proof.} + +$\bb Q$ is countably infinite, and $\bb Z$ is countably infinite because +$\bb Z$ is the union of $\{1-n : n\in\bb N\}\cup \bb N,$ ($\bb Z$ is +countably infinite since the union of countably infinite sets is +countably infinite) so by a theorem proved in the textbook, $\bb +Z\times\bb Q$ is countably infinite. + +\endanswer + +\problem{13.} +Prove or disprove: If $A = \{X\subseteq\bb N : X\hbox{ is +finite}\},$ then $|A| = \aleph_0.$ + +\answer +{\bf Proof.} + +To all finite sets of natural numbers, we can bijectively assign a +corresponding whole number ($\bb N\cup\{0\}$) defined by its binary +representation (if $i\in X,$ the $i$th least significant bit is one, +otherwise zero). +This is necessarily surjective because all finite numbers have a finite +number of ones in binary and thus a corresponding set in $A.$ +It is also injective because any sets which differ by an element must +also differ in their binary representation by a one or a zero. + +Therefore $|A| = 1+|\bb N| = \aleph_0.$ + +\endanswer + +\section{Hammack 13.3: 8, 10} + +\problem{8.} +Prove or disprove: If $A\subseteq B$ and $A$ is countably infinite and +$B$ is uncountable, then $B-A$ is uncountable. + +\answer % assume contrapositive. b-a is countable. +We will prove this by assuming the contrapositive and showing that $B$ +is countable. +Let $B-A$ and $A\subseteq B$ be countable sets. +By theorem 13.6 and $(B-A)\cup A = B,$ (since $A\subseteq B$) $B$ is +countable. +\endanswer + +\problem{10.} +Prove that if $A$ and $B$ are finite sets with $|A|=|B|,$ then any +surjection $f:A\to B$ is also an injection. Show this is not necessarily +true if $A$ and $B$ are not finite. + +\answer + +Let $A$ and $B$ be finite sets with $|A|=|B|=n.$ +We enumerate the elements of $A$ as $a_1,a_2,\ldots,a_n.$ +Let us have some surjection $f:A\to B.$ +We then let $f(a_i) = b_i.$ +Since this is a surjection, all $n$ elements of $B$ must be listed in +$b_1,b_2,\ldots,b_n.$ +If $b_i = b_j,$ we must have $i=j$ because otherwise we have +double-counted an element in $B,$ so $B$ would contain less than $n$ +elements. +Then, we have $f(a_i) = f(a_j)$ implies $i = j$ so $a_i = a_j.$ + +\endanswer + +\section{Hammack 13.4: 4, 5} + +\problem{4.} +Let ${\cal F}$ be the set of all functions $\bb R\to\{0,1\}.$ Show that +$|\bb R|<|{\cal F}|.$ + +\answer +We will show that $|\bb R| < |{\cal F}|$ by showing a bijection between +${\cal F}$ and ${\cal P}(\bb R).$ +Let $f,g\in{\cal F}.$ +Let us define corresponding sets $R,S.$ $r\in R$ if and only if +$f(r)=1,$ and $S$ similarly defined with respect to $g.$ +This is injective because if $R=S,$ $f(r)=g(r)$ for all reals, so $f=g.$ +This is surjective because any $R\subseteq\bb R$ has a corresponding $f$ +where $f(r) = 1$ if and only if $r\in R.$ +\endanswer + +\problem{5.} +Consider the subset $B = \{(x,y): x^2+y^2\leq 1\}\subseteq\bb R^2.$ Show +that $|B| = |\bb R^2|.$ + +\answer + +We will show this by the Cantor-Bernstein-Schr\"oeder theorem. +We start with the trivial injection $f:B\to \bb R^2,$ defined $f(x,y) = +(x,y).$ + +Then we use the injection $g:\bb R^2\to B,$ defined $g(x,y) = +{(x,y)\over 1+(x^2+y^2)}.$ +We will show this is injective. +Let $g(x,y) = g(w,z).$ +${(x,y)\over 1+(x^2+y^2)} = {(w,z)\over 1+(w^2+z^2)}.$ + +${(x,y)\over 1+(x^2+y^2)} = {(w,z)\over 1+(w^2+z^2)}.$ + +\endanswer + +\section{Problem not from the textbook} + +\problem{1.} Write out the multiplication table for the group $(\bb +Z_{12}^*, +\cdot).$ (Recall that $\bb Z_{12}^* = \{[k]:\gcd(k,12)=1\}.$) + +\answer +\halign{\strut#\quad\vrule&&\quad#\quad\cr + $*$ &1 &5 &7 &11\cr\noalign{\hrule} + 1 &1 &5 &7 &11\cr + 5 &5 &1 &11&7 \cr + 7 &7 &11&1 &5 \cr + 11 &11&7 &5 &1 \cr +} + +\endanswer + +\bye diff --git a/gupta/portfolio.tex b/gupta/portfolio.tex new file mode 100644 index 0000000..25b41b3 --- /dev/null +++ b/gupta/portfolio.tex @@ -0,0 +1,288 @@ +\newfam\bbold +\def\bb#1{{\fam\bbold #1}} +\font\bbten=msbm10 +\font\bbsev=msbm7 +\font\bbfiv=msbm5 +\textfont\bbold=\bbten +\scriptfont\bbold=\bbsev +\scriptscriptfont\bbold=\bbfiv + +\def\clap#1{\hbox to 0pt{\hss #1 \hss}} +\headline{\vtop{\hbox to \hsize{\strut\rlap{Math 2106 - Dr. Gupta}\hfil +\clap{\bf Portfolio}\hfil\llap{Spring 2022}}\hrule height .5pt}} + +\def\section#1{\medskip\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in% +\noindent{\bf #1}} +\def\endproof{\leavevmode\hskip\parfillskip\vrule height 6pt width 6pt +depth 0pt{\parfillskip0pt\medskip}} +\def\problem#1{\medskip\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in\item{#1}} +\def\nmid{\hskip-3pt\not\hskip2.5pt\mid} + +\problem{1.} Direct proof + +Suppose $x,y\in\bb Z.$ If $x$ and $y$ are odd, then $xy$ is odd. +(Homework 3---Hammack 4.4) + +{\bf Proof.} + +Let $x,y\in\bb Z$ such that $x$ and $y$ are odd. +We will show that $xy$ is odd. +From the definition of odd we have integers $j,k\in\bb Z$ such that +$x=2j+1$ and $y=2k+1.$ +$$xy = (2j+1)(2k+1) = 4jk+2j+2k+1 = 2(2jk+j+k) + 1.$$ + +By integer closure, $2jk+j+k\in\bb Z,$ so by the definition of odd, we +have shown that $xy$ is odd. +We have shown that the product of odd integers is odd. +\endproof + +\problem{2.} Contrapositive proof + +Prove that if $n^2$ is even, then $n$ is even. (Quiz 3) + +{\bf Proof.} + +We will show this by contraposition. +Let $n$ be an odd number (i.e. not even). +We want to show that $n^2$ is an odd number. +Since $n$ is odd, there must exist $j\in\bb Z$ such that $n=2j+1.$ +$$n^2 = (2j+1)^2 = 4j^2+4j+1 = 2(2j^2+2j) + 1.$$ +By integer closure, $2j^2+2j\in\bb Z,$ so we have shown that $n^2$ is +odd (i.e. not even). +We have shown that if $n^2$ is even, then $n$ is even. +\endproof + +\problem{3.} Proof by contradiction + +$\sqrt 6$ is irrational. (Homework 4---Hammack 6.4) + +{\bf Proof.} + +Assume for the sake of contradiction that $\sqrt 6$ is rational. +We then have that $\sqrt 6 = {p\over q}$ for some $p,q\in\bb Z$ s.t. +$\gcd(p,q) = 1$ (there is no $m>1$ such that $m\mid p$ and $m\mid q$). + +Squaring both sides, we find +$$6 = {p^2\over q^2} \to p^2 = 6q^2 = 2(3q^2),$$ from which $3q^2\in\bb +Z$ tells us $2\mid p^2.$ + +{\bf Lemma.} +We will show that $2\mid p^2$ implies $2\mid p$ by contrapositive. +Let $2\nmid p,$ so $p = 2k + 1$ for some $k\in\bb Z.$ +We then compute $p^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1,$ and +$2k^2+2k\in\bb Z,$ so $2\nmid p^2.$ +\endproof + +By the lemma, $2\mid p$ and $4\mid p^2,$ so there exists $k\in\bb Z$ +s.t. $p^2 = 4k.$ +We then get $4k = 6q^2$ and $2k = 3q^2.$ % TODO missing proof that 2k=nm. +So $q^2$ must be even, and as we've shown $2\mid q^2$ gives $2\mid q.$ +Thus, $\gcd(p,q) = 2 \neq 1,$ giving a contradiction, meaning $\sqrt 6$ +is irrational. +\endproof + +\problem{4.} Equivalence proof + +Let $A$ and $B$ be sets. Prove that $A\subseteq B$ if and only if $A\cap +B = A.$ (Homework 5---Hammack 8.22) + +{\bf Proof.} + +$(\Rightarrow)$ + +Let $A\subseteq B.$ Let $x\in A.$ By subset, $x\in B.$ And if and only +if $x\in A$ and $x\in B,$ $x\in A\cap B,$ so $A = A\cap B.$ + +$(\Leftarrow)$ + +Let $A\cap B = A.$ This implies $A\subseteq A\cap B.$ +Let $x\in A.$ +By subset, we know that $x\in A\cap B,$ and from that, $x\in B.$ +This is the definition of $A\subseteq B.$ +\endproof + +\problem{5.} A proof involving sets + +Let $A,$ $B,$ and $C$ be arbitrary sets. Prove that if $A-C\not\subseteq +A-B,$ then $B\not\subseteq C.$ (Homework 5 --- Problem 1) + +{\bf Proof.} + +We will show this by contrapositive. +Let $A$, $B,$ and $C$ be arbitrary sets such that $B\subseteq C.$ +We will show that $A-C\subseteq A-B.$ + +$(\subseteq)$ + +Let $x\in A - (B\cap C).$ +This gives us $x\in A$ and $x\not\in B\cap C.$ +We get $x\not\in B$ or $x\not\in C.$ +WLOG, let $x\not\in B.$ +$x\in A$ and $x\not\in B,$ so $x\in A-B,$ so $x\in (A-B)\cup(A-C).$ + +$(\supseteq)$ + +Let $x\in (A-B)\cup (A-C).$ +This gives $x\in A-B$ or $x\in A-C.$ +WLOG, let $x\in A-B.$ +Therefore, $x\in A$ and $x\not\in B.$ +This implies $x\not\in B\cap C,$ so $x\in A-(B\cap C).$ + +Since we have $A-(B\cap C) \subseteq (A-B)\cup(A-C)$ and $(A-B)\cup(A-C) +\subseteq A-(B\cap C),$ +we obtain $$A-(B\cap C) = (A-B)\cup(A-C).$$ +\endproof + +\problem{6.} An induction (or strong induction) proof + +Concerning the Fibonacci sequence, prove that $\sum_{k=1}^n F_k^2 = +F_nF_{n+1}.$ (Homework 6---Hammack 10.26) + +{\bf Proof.} + +First, we define the Fibonacci numbers as $F_1 = F_2 = 1,$ and for +$k>2,$ $F_k = F_{k-1} + F_{k-2}.$ + +We will show this identity for all $n\in\bb Z,$ where $n\geq 1,$ by +induction. +For $n=1,$ $\sum_{k=1}^n F_k^2 = F_1^2 = 1 = 1\cdot 1 = F_1F_2.$ + +We now assume for some $j\geq 1,$ +$$\sum_{k=1}^j F_k^2 = F_jF_{j+1},$$ +and we will show that $\sum_{k=1}^{j+1} F_k^2 = F_{j+1}F_{j+2}$ to +complete the inductive step. +Adding $F_{j+1}^2$ to the inductive hypothesis and simplifying gives +$$\sum_{k=1}^{j+1} F_k^2 = F_jF_{j+1} + F_{j+1}F_{j+1} = +F_{j+1}(F_j+F_{j+1}) = F_{j+1}F_{j+2},$$ +by definition of the Fibonacci numbers. + +We have shown by induction that for all $n\in\bb Z,$ s.t. $n\geq 1,$ +$$\sum_{k=1}^n F_k^2 = F_nF_{n+1}.$$ +\endproof + +\problem{7.} Proof a relation is an equivalence relation + +Suppose $R$ and $S$ are two equivalence relations on a set $A.$ Prove +that $R\cap S$ is also an equivalence relation. (Homework 6---Hammack 11.2.10) + +{\bf Proof.} + +The equivalence relations $R$ and $S$ on $A$ are, by definition, +reflexive, symmetric, and transitive. +We will now show that $R\cap S$ is reflexive, symmetric, and transitive +(so it is an equivalence relation). + +\smallskip +(Reflexive) + +$R$ and $S$ are reflexive, so for all $a\in A,$ we know $(a,a)\in R$ and +$(a,a)\in S.$ +Therefore, $(a,a)\in R\cap S,$ so $R\cap S$ is reflexive. + +\smallskip +(Symmetric) + +Let $(x,y)\in R\cap S.$ +By symmetry, $(x,y)\in R$ implies $(y,x)\in R.$ +Similarly, this implies $(y,x)\in S.$ +From these, $(y,x)\in R\cap S,$ so $R\cap S$ is symmetric. + +\smallskip +(Transitive) + +Let $(x,y),(y,z)\in R\cap S.$ We will show $(x,z)\in R\cap S.$ + +$(x,y),(y,z)\in R,$ and by transitivity, $(x,z)\in R.$ +Similarly, $(x,z)\in S,$ so $(x,z)\in R\cap S.$ +We have shown that $R\cap S$ is transitive. + +\smallskip +We have now shown that $R\cap S$ is an equivalence relation. +\endproof + +\problem{8.} Injectivity or surjectivity of a function + +A function $f: \bb Z\to \bb Z\times\bb Z$ is defined as $f(n) = +(2n,n+3).$ Verify whether this function is injective and whether it is +surjective (Homework 7---Hammack 12.2.4). + +{\bf Proof.} +This function is injective but not surjective. + +\smallskip +(Injective) + +Let $m,n\in\bb Z$ such that $f(n) = f(m)$ or $(2n,n+3) = (2m,m+3).$ +Then, $2n=2m,$ and rearranging, $n=m.$ +This shows $f$ is injective. + +\smallskip +(Surjective) + +We will show there is no $n$ such that $f(n) = (0,0),$ thereby showing +$f$ is not surjective. +$(2n, n+3) = (0,0)$ implies $2n = 0$ and $n = 0,$ but $n+3 = 0+3 = 3 +\neq 0,$ thereby dissatisfying the second part of the ordered pair. +$f$ is not surjective. + +We have shown $f$ is injective but not surjective. \endproof + +\problem{9.} A proof that something is a group + +Let $S = \bb R\setminus \{-1\}$ and define a binary operation on $S$ by +$a*b = a+b+ab.$ Prove that $(S,*)$ is an abelian group. (Homework +10---Judson 3.5.7) + +{\bf Proof.} + +First, we show that the group operation is closed on $S.$ +Clearly, if $a,b\in S,$ then $a,b\in\bb R$ and $a*b\in\bb R$ by closure +of the reals. +However, we must show that $a+b+ab \neq -1.$ +For the sake of contradiction, we assume $a+b+ab=-1.$ +Rearranging, $0 = a+b+ab+1 = (a+1)(b+1),$ implying $a+1=0$ or $b+1=0.$ +Without loss of generality, we treat $a+1=0$ and obtain $a=-1,$ meaning +$a\not\in S,$ giving a contradiction, and showing that $*$ is closed on +$S.$ + +Now, we show that $(S,*)$ is abelian. +Again, let $a,b\in S.$ +We compute $a*b = a+b+ab = b+a+ba = b*a,$ by commutativity of addition +and multiplication on the reals. + +Next, we must show that $0$ is the identity element of $(S,*).$ +With $a\in S,$ +$$0*a = 0+a+0a = a,$$ +and since $*$ is commutative, $a*0 = a,$ so $0$ is the identity. + +Last, we must show that for all $a\in S,$ we have $a^{-1}$ such that +$a*a^{-1} = 0$ (this also implies $a^{-1}*a = 0$ by commutativity). +Let +$$a^{-1} = -{a\over 1+a} = {1\over 1+a}-1,$$ +which is guaranteed to exist because $a\neq -1,$ so $1+a\neq 0.$ +Also $a^{-1}\in S$ because ${1\over 1+a}\neq 0,$ so ${1\over 1+a}-1 = +a^{-1}\neq -1,$ and $a^{-1}\in\bb R$ by real closure, so $a^{-1}\in S.$ + +Computing the product, +$$a*a^{-1} = a-{a\over 1+a} - {a^2\over 1+a} = {a(1+a)\over 1+a} - +{a+a^2\over 1+a} = 0,$$ +so $a^{-1}\in S$ exists for all $a\in S.$ + +\problem{10.} A proof of your own choosing + +Let $a,b\in G.$ Prove that the order of $ab$ is the same as the order of +$ba$ (Homework 10---Judson 4.5.23c) + +{\bf Proof.} + +To show that $|ab|=|ba|,$ we will show that $(ab)^n=e$ if and only if +$(ba)^n=e.$ +WLOG, we only need show that $(ba)^n=e$ if $(ab)^n=e.$ + +Let $(a,b)^n = e.$ +$(ab)^{n+1}$ can be written as $(ab)^n ab = eab$ and as $a(ba)^nb.$ +Setting these equal, +$$ab = a(ba)^nb \Rightarrow a^{-1}abb^{-1} = a^{-1}a(ba)^nbb^{-1} +\Rightarrow e = (ba)^n.$$ + +\bye -- cgit