path: root/gupta/portfolio.tex

\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