path: root/gupta/hw2.tex

\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}