1 files changed, 288 insertions, 0 deletions
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