From 89862ae6a0554870a7708ae73112f86d2d21fc8d Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Thu, 10 Feb 2022 01:12:45 -0500 Subject: new teachers, new work --- gupta/Makefile | 18 +++ gupta/hw1.tex | 18 +++ gupta/hw2.tex | 386 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ gupta/hw3.tex | 151 ++++++++++++++++++++++ gupta/hw4.tex | 218 ++++++++++++++++++++++++++++++++ gupta/hw5.tex | 217 ++++++++++++++++++++++++++++++++ 6 files changed, 1008 insertions(+) create mode 100644 gupta/Makefile create mode 100644 gupta/hw1.tex create mode 100644 gupta/hw2.tex create mode 100644 gupta/hw3.tex create mode 100644 gupta/hw4.tex create mode 100644 gupta/hw5.tex (limited to 'gupta') diff --git a/gupta/Makefile b/gupta/Makefile new file mode 100644 index 0000000..1188bc9 --- /dev/null +++ b/gupta/Makefile @@ -0,0 +1,18 @@ +.POSIX: +.SUFFIXES: .tex .pdf + +PDFTEX = pdftex +PDFLATEX = pdflatex + +.tex.pdf: + $(PDFTEX) $< + +all: hw1.pdf hw2.pdf hw3.pdf hw4.pdf hw5.pdf + +clean: + rm -f *.pdf *.log *.aux + +hw2.pdf: hw2.tex + $(PDFLATEX) hw2.tex + $(PDFLATEX) hw2.tex + $(PDFLATEX) hw2.tex diff --git a/gupta/hw1.tex b/gupta/hw1.tex new file mode 100644 index 0000000..5519891 --- /dev/null +++ b/gupta/hw1.tex @@ -0,0 +1,18 @@ +\noindent{\it (a)} + +I have access to eduroam and I live on campus, so my internet is stable. +I have a scanner app for pictures of paper work, and I have a mic and +camera for online lectures. I don't have any other technological +concerns. + +\noindent{\it (b)} + +I'm a first-year Math and CS double major, and I'm taking this class +because I'm interested in abstract algebra and analysis, which have this +class as a prerequisite. + +\noindent{\it (c)} + +I don't have any other concerns about this class. + +\bye diff --git a/gupta/hw2.tex b/gupta/hw2.tex new file mode 100644 index 0000000..922703a --- /dev/null +++ b/gupta/hw2.tex @@ -0,0 +1,386 @@ +\documentclass[10pt,twoside]{article} + +\usepackage{amssymb,amsmath,amsthm,amsfonts, epsfig, graphicx, dsfont, + bbm, bbold, url, color, setspace, multirow,pinlabel,tikz,pgfplots} +\usepackage[all]{xy} + +\usepackage{fancyhdr} \setlength{\voffset}{-1in} +\setlength{\topmargin}{0in} \setlength{\textheight}{9.5in} +\setlength{\textwidth}{6.5in} \setlength{\hoffset}{0in} +\setlength{\oddsidemargin}{0in} \setlength{\evensidemargin}{0in} +\setlength{\marginparsep}{0in} \setlength{\marginparwidth}{0in} +\setlength{\headsep}{0.25in} \setlength{\headheight}{0.5in} +\pagestyle{fancy} + +\onehalfspace + +\fancyhead[LO,LE]{Math 2106 - Dr. Gupta} \fancyhead[RO,RE]{Due Thursday 1/20/2022 at 11:59 pm} +\chead{\textbf{}} \cfoot{} +\fancyfoot[LO,LE]{} \fancyfoot[RO,RE]{Page \thepage\ of + \pageref{LastPage}} \renewcommand{\footrulewidth}{0.5pt} +\parindent 0in + +\makeatletter +\def\old@comma{,} +\catcode`\,=13 +\def,{% + \ifmmode% + \old@comma\discretionary{}{}{}% + \else% + \old@comma% + \fi% +} +\makeatother + +\let\implies\Rightarrow +\def\lnot{{\sim}} + +%% ------------------------------------------------------%% +%% -------------------Begin Document---------------------%% +%% ------------------------------------------------------%% +\begin{document} + +\begin{center} + \huge{\bf{Homework 2} - Holden Rohrer} +\end{center} + +\medskip + +\noindent \large{\textbf{Collaborators:}} + +\medskip + +\begin{itemize} + \item Hammack 1.1: 16, 28, 52 + \begin{itemize} + \item[16.] Write the set $\{6a + 2b ~|~ a, b \in \mathbb Z\}$ by listing its elements between curly braces. + \begin{proof}[Answer] + If and only if $x$ is in this set, $x+6$ and $x+2$ are in + this set. $0$ is in this set with $a=0$ and $b=0.$ This is + the set of even numbers $\{\ldots,-4,-2,0,2,4,\ldots\}.$ + \end{proof} + \item[28.] Write the set $\{\ldots, -\frac32, -\frac34, 0, + \frac34, \frac32, \frac94, 3, \frac{15}4, \frac92\}$ in + set-biulder notation. + \begin{proof}[Answer] + This set is $\{\frac34 x : x \in \mathbb Z\}.$ + \end{proof} + \item[52.] Sketch the set of points $\{(x,y)\in\mathbb R^2 : + (y-x^2)(y+x^2) = 0\}.$ + \begin{proof}[Answer] + This set is the union of the two graphs $y = x^2$ and $y = + -x^2.$ + \begin{figure}[h!] + \centering + \begin{tikzpicture}[scale=3] + \draw[<->] (-1,0) -- (1,0) node[right] {$x$}; + \draw[<->] (0,-1) -- (0,1) node[above] {$y$}; + \draw (0,0) parabola (1,1); + \draw (0,0) parabola (-1,1); + \draw (0,0) parabola (1,-1); + \draw (0,0) parabola (-1,-1); + \end{tikzpicture} + \end{figure} + %%TO DRAW + \end{proof} + \end{itemize} + \item Hammack 1.2: 2 + \begin{itemize} + \item[2.] Suppose $A = \{\pi,e,0\}$ and $B = \{0,1\}.$ + \begin{itemize} + \item[(a)] Write out $A\times B.$ + \begin{proof}[Answer] + $A\times B = \{(\pi,0), (\pi, 1), (e,0), (e,1), (0,0), + (1,0)\}.$ + \end{proof} + \item[(b)] Write out $B\times A.$ + \begin{proof}[Answer] + $B\times A = \{(0,\pi), (1,\pi), (0,e), (1,e), (0,0), + (1,0)\}.$ + \end{proof} + \item[(c)] Write out $A\times A.$ + \begin{proof}[Answer] + $A\times A = \{(\pi,\pi), (\pi,e), (\pi, 0), (e,\pi), + (e,e), (e,0), (0,\pi), (0,e), (0,0)\}.$ + \end{proof} + \item[(d)] Write out $B\times B.$ + \begin{proof}[Answer] + $B\times B = \{(0,0), (0,1), (1,0), (1,1)\}.$ + \end{proof} + \item[(e)] Write out $A\times \emptyset.$ + \begin{proof}[Answer] + $A\times\emptyset = \emptyset.$ + \end{proof} + \item[(f)] Write out $(A\times B)\times B.$ + \begin{proof}[Answer] + $(A\times B)\times B = \{((\pi,0),0), ((\pi, 1),0), + ((e,0),0), ((e,1),0), ((0,0),0), ((0,1),0), + ((\pi,0),1), ((\pi, 1),1), + ((e,0),1), ((e,1),1), ((0,0),1), ((0,1),1)\}.$ + \end{proof} + \item[(g)] Write out $A\times(B\times B).$ + \begin{proof}[Answer] + $A\times(B\times B) = \{(\pi,(0,0)), (\pi,(1,0)), + (e,(0,0)), (e,(1,0)), (0,(0,0)), (0,(1,0)), + (\pi,(0,1), (\pi,(1,1)), + (e,(0,1)), (e,(1,1)), (0,(0,1)), (0,(1,1))\}.$ + \end{proof} + \item[(h)] Write out $A\times B\times B.$ + \begin{proof}[Answer] + $A\times B\times B = \{(\pi,0,0), (\pi, 1,0), + (e,0,0), (e,1,0), (0,0,0), (0,1,0), + (\pi,0,1), (\pi, 1,1), + (e,0,1), (e,1,1), (0,0,1), (0,1,1)\}.$ + \end{proof} + \end{itemize} + \end{itemize} + \item Hammack 1.3: 2, 8, 10, 16 + \begin{itemize} + \item[2.] List all subsets of $\{1,2,\emptyset\}.$ + \begin{proof}[Answer] + The subsets are $\emptyset, \{1\}, \{2\}, \{\emptyset\}, + \{1,2\}, \{1,\emptyset\}, \{2,\emptyset\}, + \{1,2,\emptyset\}.$ + \end{proof} + \item[8.] List all subsets of $\{\{0,1\}, \{0,1,\{2\}\}, + \{0\}\}.$ + \begin{proof}[Answer] + The subsets are $\emptyset, \{\{0,1\}\}, \{\{0,1,\{2\}\}\}, + \{\{0\}\}, \{\{0,1\},\{0\}\}, \{\{0,1\},\{0,1,\{2\}\}\}, + \{\{0\},\{0,1,\{2\}\}\}, \{\{0,1\},\{0\},\{0,1,\{2\}\}\}.$ + \end{proof} + \item[10.] Write out $\{X\subseteq N : |X| \leq 1\}.$ + \begin{proof}[Answer] + This set is $\{-1,0,1\}.$ + \end{proof} + \item[16.] Decide if $\{(x,y) : x^2 - x = 0\} \subseteq + \{(x,y) : x-1 = 0\}$ is true or false. + \begin{proof}[Answer] + False. $(0,0)$ is in the first set but not in the second + set, so it cannot be a subset. + \end{proof} + \end{itemize} + \item Hammack 1.4: 6, 14, 16, 18, 20 + \begin{itemize} + \item[6.] Find $\mathcal P(\{1,2\})\times\mathcal P(\{3\}).$ + \begin{proof}[Answer] + This is $\{(\emptyset,\emptyset), (\{1\},\emptyset), + (\{2\},\emptyset), (\{1,2\},\emptyset), (\emptyset, \{3\}), + (\{1\}, \{3\}), (\{2\}, \{3\}), (\{1,2\}, \{3\}).$ + \end{proof} + \item[14.] Suppose $|A| = m$ and $|B| = n.$ Find + $|\mathcal P(\mathcal P(A))|.$ + \begin{proof}[Answer] + $|\mathcal P(\mathcal P(A))| = 2^{|\mathcal P(A)|} = + 2^{2^m}.$ + \end{proof} + \item[16.] Suppose $|A| = m$ and $|B| = n.$ Find + $|\mathcal P(A)\times \mathcal P(B)|.$ + \begin{proof}[Answer] + This is $|\mathcal P(A)|\cdot|\mathcal P(B)| = 2^{|\mathcal + P(A)|}2^{|\mathcal P(B)|} = 2^{nm}$ + \end{proof} + \item[18.] Suppose $|A| = m$ and $|B| = n.$ Find + $|\mathcal P(A\times \mathcal P(B))|.$ + \begin{proof}[Answer] + By similar techniques, this set has cardinality $2^{m2^n}.$ + \end{proof} + \item[20.] Suppose $|A| = m$ and $|B| = n.$ Find $|\{X\subseteq\mathcal P(A) : |X|\leq 1\}|.$ + \begin{proof}[Answer] + This is $\emptyset$ and every one-element subset of + $\mathcal P(A),$ so it has cardinality $2^m + 1.$ + \end{proof} + \end{itemize} + \item Hammack 1.6: 2 + \begin{itemize} + \item[2.] Let $A = \{0,2,4,6,8\}$ and $B = \{1,3,5,7\}$ have + universal set $U = \{0,1,2,\ldots,8\}.$ Find: + \begin{itemize} + \item[(a)] $\bar A = B.$ + \item[(b)] $\bar B = A.$ + \item[(c)] $A\cap\bar A = \emptyset.$ + \item[(d)] $A\cup\bar A = U.$ + \item[(e)] $A - \bar A = A.$ + \item[(f)] $\bar{A\cup B} = \emptyset.$ + \item[(g)] $\bar A \cap \bar B = \emptyset.$ + \item[(h)] $\bar{A\cap B} = U.$ + \item[(i)] $\bar A \times B = B^2.$ + \end{itemize} + %\begin{proof}[Answer] + %\end{proof} + \end{itemize} + \item Hammack 1.8: 4, 10, 12, 14 + \begin{itemize} + \item[4.] For each $n\in \mathbb N,$ let $A_n = \{-2n,0,2n\}.$ + \begin{itemize} + \item[(a)] $\bigcup_{i\in N} A_i = \{2n:n\in\mathbb N\}$ + \item[(b)] $\bigcap_{i\in N} A_i = \{0\}$ + \end{itemize} + \item[10.] + \begin{itemize} + \item[(a)] $\bigcup_{i\in [0,1]} [x,1]\times[0,x^2] = + \{(x,y)\in \mathbb [0,1]^2 : y \leq x^2\}.$ + \item[(b)] $\bigcap_{i\in [0,1]} [x,1]\times[0,x^2] = + \{(1,0)\},$ as can be seen from the intersection of the + $[0,1]\times[0,0]$ and $[1,1]\times[0,1]$ elements. + \end{itemize} + \item[12.] If $\bigcap_{\alpha\in I} A_\alpha = + \bigcup_{\alpha\in I} A_\alpha,$ what do you think can be + said about the relationships between the sets $A_{\alpha}?$ + \begin{proof}[Answer] + For any $\alpha,\beta \in I,$ $A_\alpha = A_\beta.$ + \end{proof} + \item[14.] If $J\neq\emptyset$ and $J\subseteq I,$ does it + follow that $\bigcap_{\alpha\in I} A_\alpha \subseteq + \bigcap_{\alpha\in J} A_\alpha?$ Explain. + \begin{proof}[Answer] + Yes, this does follow because + $\bigcap_{\alpha\in I} A_\alpha = \bigcap_{\alpha\in J} + A_\alpha \cap \bigcap_{\beta\in I - J} A_\beta + \subseteq \bigcap_{\alpha\in J} A_\alpha.$ + \end{proof} + \end{itemize} + \item Hammack 2.3: 2, 6 + \begin{itemize} + \item[2.] Convert the following sentence into the form ``{\em If + P, then Q}.'' ``For a function to be continuous, it is + sufficient that it is differentiable.'' + \begin{proof}[Answer] + ``If a function is differentiable, that function is + continuous.'' + \end{proof} + \item[6.] Convert the following sentence into the form ``{\em If + P, then Q}.'' ``Whenever a surface has only one side, it is + non-orientable.'' + \begin{proof}[Answer] + ``If a surface has one side, that surface is + non-orientable.'' + \end{proof} + \end{itemize} + \item Hammack 2.5: 10 + \begin{itemize} + \item[10.] Suppose the statement $((P\land Q)\lor R) \implies + (R\lor S)$ is false. Find the truth values of $P$, $Q,$ $R,$ + and $S.$ + \begin{proof}[Answer] + $P=Q={\rm True}$ and $R=S={\rm False}$ make this statement + false. + \end{proof} + \end{itemize} + \item Hammack 2.6: 14 + \begin{itemize} + \item[14.] Decide whether or not $P\land(Q\lor\lnot Q)$ and + $(\lnot P) \implies (Q\land\lnot Q)$ are logically + equivalent. + \begin{proof}[Answer] + These are logically equivalent. $Q\lor ~Q \equiv T$ and + $Q\land ~Q \equiv F,$ giving us simplified expressions + $P\land T \equiv P$ and $\lnot P \implies F \equiv P,$ so + these are logically equivalent expressions. + \end{proof} + \end{itemize} + \item Problems not from the textbook + \begin{enumerate} + \item Use truth tables to prove that each of the following compound propositions is \emph{not} a tautology. These implication are common logical fallacies (errors in reasoning) since the conclusion does not follow from the hypotheses. + \begin{enumerate} + \item $[(P\implies Q)\land Q]\implies P$ + \begin{proof}[Answer] + \begin{tabular}{|c|c|c|c|c|c|} + \hline + $P$ & $Q$ & $P \implies Q$ & $(P \implies Q)\land + Q$ & $[(P\implies Q)\land Q] \implies P$ \\\hline + + T & T & T & T & T\\\hline + T & F & F & F & T\\\hline + F & T & T & T & F\\\hline + F & F & T & F & T\\\hline + \end{tabular} + \end{proof} + \item $[(P\implies Q)\land\lnot{P}]\implies\lnot{Q}$ + \begin{proof}[Answer] + \begin{tabular}{|c|c|c|c|c|c|} + \hline + $P$ & $Q$ & $P \implies Q$ & $(P \implies Q)\land + \lnot P$ & $[(P\implies Q)\land \lnot P] \implies + \lnot Q$ \\\hline + + T & T & T & F & T\\\hline + T & F & F & F & T\\\hline + F & T & T & T & F\\\hline + F & F & T & T & T\\\hline + \end{tabular} + \end{proof} + \end{enumerate} + \item Use truth tables to prove that each of the following compound propositions is a tautology. These are the four most important ``rules of inference'' in propositional logic. Each rule gives a conclusion that follows from a set of hypotheses and thus give building blocks for correct proofs. + \begin{enumerate} + \item $[P\land(P\implies Q)]\implies Q$ + \begin{proof}[Answer] + \begin{tabular}{|c|c|c|c|c|c|} + \hline + $P$ & $Q$ & $P \implies Q$ & + $P\land (P \implies Q)$ & + $[P\land (P\implies Q)] \implies Q$ \\\hline + + T & T & T & T & T\\\hline + T & F & F & F & T\\\hline + F & T & T & F & T\\\hline + F & F & T & F & T\\\hline + \end{tabular} + \end{proof} + \item $[\lnot Q\land(P\implies Q)]\implies\lnot{P} $ + \begin{proof}[Answer] + \begin{tabular}{|c|c|c|c|c|c|} + \hline + $P$ & $Q$ & $P \implies Q$ & $(P \implies Q)\land + \lnot P$ & $[(P\implies Q)\land \lnot P] \implies + \lnot Q$ \\\hline + + T & T & T & F & T\\\hline + T & F & F & F & T\\\hline + F & T & T & T & F\\\hline + F & F & T & T & T\\\hline + \end{tabular} + \end{proof} + \item $[(P\implies Q)\land(Q\implies R)]\implies(P\implies R)$ + \begin{proof}[Answer] + Let $(1)$ be $(P\implies Q)\land(Q\implies R).$ + + \begin{tabular}{|c|c|c|c|c|c|c|c|} + \hline + $P$ & $Q$ & $R$ & $P \implies Q$ & + $Q \implies R$ & + $(1)$ & + $P \implies R$ & + $(1) \implies (P\implies R)$ \\\hline + + T & T & T & T & T & T & T & T\\\hline + T & T & F & T & F & F & F & T\\\hline + T & F & T & F & T & F & T & T\\\hline + T & F & F & F & T & F & F & T\\\hline + F & T & T & T & T & T & T & T\\\hline + F & T & F & T & F & F & T & T\\\hline + F & F & T & T & T & T & T & T\\\hline + F & F & F & T & T & T & T & T\\\hline + % to break up lol + \end{tabular} + \end{proof} + \item $[(P\lor Q)\land\lnot{P}]\implies Q$ + \begin{proof}[Answer] + \begin{tabular}{|c|c|c|c|c|c|} + \hline + $P$ & $Q$ & $P \lor Q$ & $(P \lor Q)\land + \lnot P$ & $[(P\lor Q)\land \lnot P] \implies Q$ + \\\hline + + T & T & T & F & T\\\hline + T & F & T & F & T\\\hline + F & T & T & T & T\\\hline + F & F & F & F & T\\\hline + \end{tabular} + \end{proof} + \end{enumerate} + \end{enumerate} +\end{itemize} + +\label{LastPage} +\end{document} diff --git a/gupta/hw3.tex b/gupta/hw3.tex new file mode 100644 index 0000000..1961ce3 --- /dev/null +++ b/gupta/hw3.tex @@ -0,0 +1,151 @@ +\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\bgroup} +\def\endanswer{\egroup\medskip} +\def\section#1{\medskip\goodbreak\noindent{\bf #1}} +\let\impl\Rightarrow + +\headline{\vtop{\hbox to \hsize{\strut Math 2106 - Dr. Gupta\hfil Due Thursday +2022-01-27 at 11:59 pm}\hrule height .5pt}} + +\centerline{\bigbf Homework 3 - Holden Rohrer} +\bigskip + +\noindent{\bf Collaborators:} None + +\section{Hammack 2.7: 2, 9, 10} + +\item{2.} Write the following as an English sentence: +$\forall x\in\bb R, \exists n\in \bb N, x^n\geq 0.$ + +\answer +For all real numbers $x,$ there is a natural number $n$ such that $x^n$ +is nonnegative. +This statement is true because, for all real numbers, $x^2 \geq 0$ and +$2\in\bb N.$ +\endanswer + +\item{9.} Write the following as an English sentence: +$\forall n\in\bb Z, \exists m\in\bb Z, m = n+5.$ + +\answer +For all integers $n,$ there is an integer $m$ which is 5 greater than +$n.$ +This statement is true because the integers are closed under addition. +\endanswer + +\item{10.} Write the following as an English sentence: +$\exists m\in\bb Z, \forall n\in\bb Z, m = n + 5.$ + +\answer +There is an integer $m$ such that for all integers $n,$ $m$ is 5 greater +than $n.$ +This statement is false because $m$ cannot equal $0+5$ and $1+5$ at the +same time. +\endanswer + +\section{Hammack 2.9: 1, 7, 10} + +\item{1.} Translate the following sentence into symbolic logic: ``If $f$ +is a polynomial and its degree is greater than 2, then $f'$ is not +constant. +\answer +Where $P$ is the set of polynomials, and $\mathop{\rm degree}(p)$ is the +degree of a polynomial $p,$ +$$\forall p\in P, \left(\mathop{\rm degree}(p) > 2\right) \impl \exists +a,b\in\bb R, f'(a) \neq f'(b).$$ +\endanswer + +\item{7.} Translate the following sentence into symbolic logic: ``There +exists a real number $a$ for which $a+x = x$ for every real number $x.$ +\answer +$$\exists a\in\bb R, \forall x\in\bb R, a+x = x.$$ +\endanswer + +\item{10.} Translate the following sentence into symbolic logic: ``If +$\sin(x) < 0,$ then it is not the case that $0\leq x\leq\pi.$ +\answer +$$\forall x\in\bb R, \sin(x) < 0 \impl \lnot(0\leq x\leq\pi).$$ +\endanswer + +\section{Hammack 2.10: 2, 5, 10} +\item{2.} Negate the following sentence: ``If $x$ is prime, then $\sqrt +x$ is not a rational number.'' + +\answer +There is a prime number $x$ such that $\sqrt x$ is a rational number. +\endanswer + +\item{5.} Negate the following sentence: ``For every positive number +$\epsilon,$ there is a positive number $M$ for which $|f(x)-b|<\epsilon$ +whenever $x > M.$ + +\answer +There is a positive number $\epsilon$ such that for all $M$ there is an +$x > M$ such that $|f(x)-b|>\epsilon$ +\endanswer + +\item{10.} If $f$ is a polynomial and its degree is greater than 2, then +$f'$ is not constant. + +\answer +There is a polynomial with degree greater than 2 such that $f'$ is +constant. +\endanswer + +\section{Hammack 4: 4, 12, 20} + +\item{4.} Prove ``Suppose $x,y\in\bb Z.$ If $x$ and $y$ are odd, then +$xy$ is odd'' with direct proof. +\answer +Suppose $x,y\in\bb Z$ and that $x$ and $y$ are odd. +Since $x$ is odd, there exists $j\in\bb Z$ such that $x = 2j+1.$ +Since $y$ is odd, there exists $k\in\bb Z$ such that $y = 2k+1.$ +$xy = (2j+1)(2k+1) = 4jk + 2j + 2k + 1 = 2(2jk + j + k) + 1.$ +Because $2jk + j + k$ is an integer, $xy$ is odd because it is one more +than two times an integer. +\endanswer + +\item{12.} Prove ``If $x\in\bb R$ and $0 1,$ $a^2 = |a|^2 > |a|,$ so +we will check $a^2|a$ for the remaining cases $\{-1,0,1\}.$ + +$n|m$ iff there is a $k\in\bb Z,$ $k\neq 0,$ $m = nk.$ +For $0,$ $0^2 = 1(0),$ so $0^2|0.$ +For $1,$ $1^2 = 1(1),$ so $1^2|1.$ +For $-1,$ $(-1)^2 = -1(-1),$ so $(-1)^2|1.$ +\endanswer + +\section{Problem not from the textbok} + +\item{1.} Prove that for all positive real numbers $x,$ the sum of $x$ and its +reciprocal is greater than or equal to 2. + +\answer +Let $x$ be a positive real number. +For all real numbers $y,$ $y^2 \geq 0,$ so $(x-1)^2 \geq 0.$ +This is equal to +$$x^2 - 2x + 1 \geq 0 \to x^2 + 1 \geq 2x \to x + 1/x \geq 2,$$ +since dividing by $x > 0$ is a valid algebraic operation. +\endanswer + +\bye diff --git a/gupta/hw4.tex b/gupta/hw4.tex new file mode 100644 index 0000000..fe80e3f --- /dev/null +++ b/gupta/hw4.tex @@ -0,0 +1,218 @@ +\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\goodbreak\noindent{\bf #1}} +\let\impl\Rightarrow +\def\nmid{\not\hskip2.5pt\mid} + +\headline{\vtop{\hbox to \hsize{\strut Math 2106 - Dr. Gupta\hfil Due Thursday +2022-02-03 at 11:59 pm}\hrule height .5pt}} + +\centerline{\bigbf Homework 4 - Holden Rohrer} +\bigskip + +\noindent{\bf Collaborators:} None + +\section{Hammack 4: 26} + +\item{26.} Prove the following with direct proof: every odd integer is a +difference of two squares. + +\answer +Let $n$ be an odd integer. +We will show that there are two perfect squares $a^2$ and $b^2$ (with +$a,b\in\bb Z$) such that $n$ is their difference. + +Because it is odd, there exists an integer $k$ such that $n = 2k+1.$ +$$(k+1)^2-k^2 = k^2+2k+1-k^2 = 2k+1 = n,$$ +so any odd integer can be written as the difference of two squares. +\endanswer + +\section{Hammack 5: 6, 12, 18, 20, 24, 28} + +\item{6.} Prove the following with contrapositive proof: suppose +$x\in\bb R.$ If $x^3-x>0,$ then $x>-1.$ + +\answer +For contrapositive proof, let $x \leq -1.$ +We will prove that $x^3-x\leq 0.$ + +We obtain $x+1 \leq 0$ and $x-1 \leq -2.$ +$$x(x-1)(x+1) \leq 0,$$ +because the product of three non-positive numbers is non-positive. +% is this sufficient?? +\endanswer + +\item{12.} Prove the following with contrapositive proof: suppose +$a\in\bb Z.$ If $a^2$ is not divisible by 4, then $a$ is odd. + +\answer +For contrapositive proof, let $a$ be not odd (even). We will show that +$a^2$ is divisible by 4. + +By the definition of even, there exists $k$ such that $a = 2k.$ +$a^2 = 4k^2,$ and $k^2\in\bb Z,$ so $a^2$ is divisible by 4. +\endanswer + +\item{18.} Prove the following with either direct or contrapositive +proof: for any $a,b\in\bb Z,$ it follows that $(a+b)^3\equiv a^3+b^3 +\pmod{3}$ + +\answer +Let $a,b\in\bb Z.$ +We will prove that $(a+b)^3\equiv a^3+b^3\pmod{3}.$ + +$$(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3 = a^3 + b^3 + 3(a^2b+ab^2),$$ +so $(a+b)^3\equiv a^3 + b^3 \pmod{3}$ by definition of modular +equivalence. +\endanswer + +\item{20.} Prove the following with either direct or contrapositive +proof: if $a\in\bb Z$ and $a\equiv 1\pmod{5},$ then $a^2\equiv +1\pmod{5}.$ + +\answer +Let $a\in\bb Z$ and $a\equiv 1\pmod{5}.$ +We will prove that $a^2\equiv 1\pmod{5}.$ + +There exists $k\in\bb Z$ such that $a = 5k+1.$ +$$a^2 = (5k+1)^2 = 25k^2 + 10k + 1 = 5(5k^2+2k) + 1,$$ +so $a^2 \equiv 1\pmod{5}.$ +\endanswer + +\item{24.} Prove the following with either direct or contrapositive +proof: if $a\equiv b \pmod{n}$ and $c\equiv d \pmod{n},$ then $ac\equiv +bd \pmod{n}.$ + +\answer +Let $a,b,c,d\in\bb R.$ +Let $a\equiv b \pmod{n}$ and $c\equiv d \pmod{n}.$ +We will show that $ac\equiv bd\pmod{n}.$ + +Therefore, there is $k\in\bb Z$ such that $a = b + nk,$ and there is +$j\in\bb Z$ such that $c = d + nj.$ +$$ac = (b+nk)(d+nj) = bd + n(jb+dk+njk),$$ +so $ac \equiv bd \pmod{n},$ because $jb+dk+njk\in\bb Z.$ +\endanswer + +\item{28.} Prove the following with either direct or contrapositive +proof: if $n\in\bb Z,$ then $4\nmid (n^2-3).$ + +\smallskip +{\bf Lemma.} +Let $n\in\bb Z.$ We will show that, for some $k\in\bb Z,$ $n^2 = 4k$ or +$n^2 = 4k+1.$ +$n$ can be written as exactly one of $4j,$ $4j+1,$ $4j+2,$ and $4j+3,$ +where $j\in\bb Z.$ + +In the first case $n = 4j,$ $n^2 = 16j^2 = 4(4j^2),$ so with $k=4j^2,$ +$n^2 = 4k.$ + +In the second case $n = 4j+1,$ $n^2 = 16j^2 + 8j + 1 = 4(4j^2+2j) + 1,$ +so with $k = 4j^2+2j,$ $n^2 = 4k + 1.$ + +In the third case $n = 4j+2,$ $n^2 = 16j^2 + 16j + 4 = 4(4j^2+4j+1),$ so +with $k = 4j^2+4j+1,$ $n^2 = 4k.$ + +In the fourth case $n = 4j+3,$ $n^2 = 16j^2 + 24j + 9 = 4(4j^2+6j+2)+1,$ +so with $k = 4j^2+6j+2,$ $n^2 = 4k+1.$ + +All of these values of $k$ are integers by integer closure. + +$n^2\neq 4k+2$ and $n^2\neq 4k+3$ for any integer $k$ because $n^2$ is +an integer and it can be written as exactly one of $4k,$ $4k+1,$ $4k+2,$ +and $4k+3.$ +\endproof + +\answer +Let $n\in\bb Z.$ +By the lemma, $n^2 = 4k$ or $n^2 = 4k+1.$ +In the case $n^2 = 4k,$ $n^2 - 3 = 4k - 3 = 4(k-1) + 1,$ +which is not divisible by $4.$ +In the case $n^2 = 4k+1,$ $n^2 - 3 = 4k - 2 = 4(k-1) + 2,$ +which is not divisible by $4.$ +\endanswer + +\section{Hammack 6: 4, 6, 8} + +\item{4.} Prove the following by contradiction: $\sqrt 6$ is irrational. + +\answer +For the sake of contradiction, assume that $\sqrt 6$ is rational. +Therefore, there exist coprime $p,q\in\bb Z$ such that $\sqrt 6 = +{p\over q}.$ + +$$p = q\sqrt 6 \to p^2 = 6q^2.$$ +$p^2$ is even only if $p$ is even ($2\mid p$), so $4\mid p^2,$ so $2\mid +q^2,$ and thus $2\mid q.$ +Therefore, $(q,p) = 2\neq 1,$ meaning they're not coprime. +\endanswer + +\item{6.} Prove the following by contradiction: if $a,b\in\bb Z,$ then +$a^2-4b-2\neq 0.$ + +\answer +Let $a,b\in\bb Z,$ and for the sake of contradiction, let $a^2-4b-2 = +0.$ +$$a^2-4b-2 \equiv 0 \equiv a^2-2 \to a^2 \equiv 2 \bmod{4}.$$ +Therefore, there exists $k\in\bb Z$ such that $a^2 = 4k+2.$ +By the lemma, $a^2 \neq 4k + 2.$ +\endanswer + +\item{8.} Prove the following by contradiction: suppose $a,b,c\in\bb Z.$ +If $a^2+b^2=c^2,$ then $a$ or $b$ is even. + +\answer +Let $a,b,c\in\bb Z$ such that $a^2+b^2=c^2.$ +Suppose, for the sake of contradiction, $a$ and $b$ are odd. +There exists $j$ and $k$ such that $a=2k+1$ and $b=2j+1.$ + +Therefore, $a^2 + b^2 = (2k+1)^2 + (2j+1)^2 = 4k^2 + 4k + 1 + 4j^2 + 4j ++ 1 = 4(k^2+k+j^2+j) + 2 = c^2.$ +By the lemma, $c^2 \neq 4k + 2.$ +\endanswer + +\section{Problems not from the textbok} + +\item{1.} A perfect square is an integer $n$ for which there exists an +integer $k$ such that $n = k^2.$ Prove that if $n$ is a positive integer +such that $n\equiv 2\bmod 4$ or $n\equiv 3\bmod 4,$ then $n$ is not a +perfect square. + +\answer +This has already been proven in the above lemma. +\endanswer + +\item{2.} After a grueling slog through the snow to reach Ponce City +Market, you decide to reward yourself by buying three boxes of candy +from Collier’s. One box contains mint candies, one chocolate candies, +and the other is mixed. Unfortunately, all three boxes were incorrectly +labeled! What is the smallest number of candies that you need to remove +and sample to be able to correctly label all three boxes? Carefully +justify your reasoning. + +\answer +We only need to sample one candy. +We sample the box labeled ``mixed,'' and without loss of generality we +get a chocolate candy. This is the chocolate box. +This box cannot be ``mixed'' because it is labeled incorrectly, and this +box cannot be ``mint'' because the mint box doesn't have chocolate +candy. +Now, the box labeled ``mint'' must be the mixed box because it cannot be +the chocolate box (we only have one of those) and it cannot be the mixed +box because it is incorrectly labeled. +By elimination, the last box is the mixed box. +\endanswer + +\bye diff --git a/gupta/hw5.tex b/gupta/hw5.tex new file mode 100644 index 0000000..bb1bd43 --- /dev/null +++ b/gupta/hw5.tex @@ -0,0 +1,217 @@ +\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 5 - Holden Rohrer} +\bigskip + +\noindent{\bf Collaborators:} None + +\section{Hammack 7: 6, 9, 12} + +\problem{6.} Suppose $x,y\in\bb R.$ Then $x^3+x^2y = y^2+xy$ if and only if +$y = x^2$ or $y = -x.$ + +$x^2(x+y) = y(x+y).$ +\answer +$(\Rightarrow)$ + +Let $x^3 + x^2y = y^2+xy.$ +We then have $x^2(x+y) = y(x+y).$ +If $y = -x,$ $x+y = 0 \impl x^2(x+y) = y(x+y).$ +Otherwise, we can divide by $x+y$ because it is nonzero, giving +$y = x^2.$ +Therefore, $y=-x$ or $y=x^2.$ + +$(\Leftarrow)$ + +Let $y = -x$ or $y = x^2.$ +We will first consider the case $y = -x,$ then the case $y = x^2.$ + +With $y = -x,$ $x^3 + x^2y = x^3 - x^3 = 0 = x^2 - x^2 = y^2 + xy.$ + +If $y = x^2,$ $x^3 + x^2y = x^3 + x^4 = x^3 + x^4 = xy + y^2.$ +\endanswer + +\problem{9.} Suppose $a\in\bb Z.$ Prove that $14\mid a$ if and only if +$7\mid a$ and $2\mid a.$ + +\answer +$(\Rightarrow)$ + +Let $14\mid a.$ +This gives $a = 14k$ for some integer $k.$ +$a = 2(7k),$ so with $7k\in\bb Z,$ we get $2\mid a.$ +Similarly, $a = 7(2k),$ so with $2k\in\bb Z,$ we get $7\mid a.$ + +$(\Leftarrow)$ + +Let $7\mid a$ and $2\mid a.$ +These give $a = 7j$ for some $j$ and $a = 2k$ for some integers $j$ and +$k.$ +A product of odd number $7$ and odd number $j$ cannot be even (and $a$ +is even because $2\mid a$), so $j$ must be even. +Thus, there exists $l\in\bb Z$ such that $j = 2l.$ +This gives $a = 7(2l) = 14l \to 14\mid a.$ +\endanswer + +\problem{12.} There exist a positive real number $x$ for which $x^2 < \sqrt +x.$ + +\answer +Observe that $x = 1/4$ gives $x^2 = 1/16$ and $\sqrt x = 1/2,$ so $1/16 +< 1/2.$ +\endanswer + +\section{Hammack 8: 12, 22, 28} + +\problem{12.} If $A,$ $B,$ and $C$ are sets, then $A-(B\cap C) = +(A-B)\cup(A-C).$ + +\answer +$(\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).$$ +\endanswer + +\problem{22.} Let $A$ and $B$ be sets. Prove that $A\subseteq B$ if and +only if $A\cap B = A.$ + +\answer +$(\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,$ or $x\in A\impl x\in A\cap B\impl +x\in B.$ +$x\in A\impl x\in B$ is the definition of $A\subseteq B.$ +\endanswer + +\problem{28.} Prove $\{12a+25b:a,b\in\bb Z\} = \bb Z.$ + +\answer +Let $A = \{12a+25b:a,b\in\bb Z\}.$ If $x\in A,$ $x\in\bb Z$ because the +integers are closed under addition and mulitplication. + +If $x\in\bb Z,$ let $b = x$ and $a = -2x,$ giving us $12(-2x) + 25x = +x\in A.$ + +Therefore, since $A\subseteq\bb Z$ and $\bb Z\subseteq A,$ these two +sets are equal. +\endanswer + +\section{Hammack 9: 6, 28, 30, 34} +Prove or disprove each of the following statements. + +\problem{6.} If $A,$ $B,$ $C,$ and $D$ are sets, then $(A\times +B)\cup(C\times D) = (A\cup C)\times(B\cup D).$ + +\answer +{\bf Disproof.} + +Let $A = B = \{1\}$ and $C = D = \{2\}.$ +The set $A\times B = \{(1,1)\}.$ +The set $C\times D = \{(2,2)\}.$ +And the set $A\cup C = B\cup D = \{1,2\}.$ + +$$(A\times B)\cup(C\times D) = \{(1,1),(2,2)\} \neq +\{(1,1),(1,2),(2,1),(2,2)\} = (A\cup C)\times(B\cup D).$$ +\endanswer + +\problem{28.} Suppose $a,b\in\bb Z.$ If $a\mid b$ and $b\mid a,$ then $a = +b.$ + +\answer +We will show this by contrapositive. +Let $a\neq b.$ We will show that $a\nmid b$ or $b\nmid a.$ + +WLOG, $a > b.$ +Immediately, $a\nmid b.$ +\endanswer + +\problem{30.} There exist integers $a$ and $b$ for which $42a + 7b = 1.$ + +\answer +{\bf Disproof.} + +Let $a,b\in\bb Z.$ +For the sake of contradiction, assume $42a + 7b = 1.$ +Dividing by 7, $6a + b = 1/7.$ +By closure of the integers, $6a+b\in\bb Z,$ and $1/7\not\in\bb Z,$ +giving a contradiction. +\endanswer + +\problem{34.} If $X\subseteq A\cup B,$ then $X\subseteq A$ or $X\subseteq +B.$ + +\answer +{\bf Disproof.} + +Let $A = \{1\},$ $B = \{2\},$ and $X = A\cup B.$ +Immediately, $X\subseteq A\cup B.$ +And then, $2\in X,$ but $2\not\in A,$ so $X\not\subseteq A.$ +Also, $1\in X,$ but $1\not\in B,$ so $X\not\in B.$ +\endanswer + +\section{Problem not from the textbok} + +\problem{1.} Let $A,$ $B,$ and $C$ be arbitrary sets. Prove that if +$A-C\not\subseteq A-B,$ then $B\not\subseteq C.$ + +\answer +We will prove this by contrapositive. +Let $B\subseteq C.$ We will show that $A-C\subseteq A-B.$ + +If $x\in B,$ $x\in C,$ so by contrapositive, if $x\not\in C,$ $x\not\in +B.$ + +Let $y\in A-C.$ +By definition of setminus, $y\in A$ and $y\not\in C.$ +As established, this implies $y\not\in B.$ +Therefore, with $y\in A$ and $y\not\in B,$ $y\in A-B,$ so +$A-C\subseteq A-B.$ +\endanswer + +\bye -- cgit