
\documentclass[letterpaper, reqno,11pt]{article}
\usepackage[margin=1.0in]{geometry}
\usepackage{color,latexsym,amsmath,amssymb}

\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\begin{document}
\pagenumbering{arabic}
\title{Math 120 Homework 1}
\date{}
\newtheorem{thm}{Theorem}
\maketitle
%
\vspace{-16 mm}
\begin{itemize}

\item Due Friday September 13 th at 10:00. Homework should be submitted using Canvas. 
%
%
\item {\bf Collaboration Policy}: You are welcome (and encouraged) to work on the homework in groups. However, each student must write up the homework on their own, and must use their own wording (i.e.~don't jusy copy the solutions from your friend). If you do collaborate with others, please list the name of your collaborators at the top of the homework.

\item You are encouraged (though not required) to type up your solutions. If you choose to do this, I strongly recommend that you use the typesetting software LaTeX. LaTeX is used by the entire mathematics community, and if you intend to go into math, you’ll need to learn it sooner or later. ``The Not So Short Introduction to LaTeX'' is a good place to start. This guide can be found at http://tug.ctan.org/info/lshort/english/lshort.pdf . You can also download the .tex source file for this homework and take a look at that.

\item Each homework problem should be correct as stated. Occasionally, however, I might screw something up and give you an impossible homework problem. If you believe a problem is incorrect, please email me. If you are right, the first person to point out an error will get +1 on that homework, and I will post an updated version. 
\end{itemize}


\subsection*{Sets}
\medskip
\noindent {\bf 1.} Let $S=\{1,2,3,4,5\}$, $T=\{1, 3, 6\}$. What is \\
{\bf a.} $S\cap T$\\ 
{\bf b.} $S\cup T$\\
{\bf c.} $S\backslash T$\\
{\bf d.} $T\backslash S$

\medskip

\noindent {\bf 2 a.} Give an example of sets $S$ and $T$ where $S\backslash T = T \backslash S$. \\
{\bf b.} Give an example of sets $S$ and $T$ where $S\backslash T \neq T \backslash S$. 

\medskip

\noindent {\bf 3.} Give an example of sets $S$ and $T$ so that $S$ and $T$ have infinitely many elements, but $S\cap T$ has finitely many elements.

\medskip

\noindent{\bf Definition.} If $a$ and $b$ are integers, we say that $a$ is \emph{divisible} by $b$ if there exists an integer $c$ so that $a = bc$. For example, $6$ is divisible by $3$ since we can write $6 = 3\cdot 2$. Similarly, $6$ is divisible by $-3$ since we can write $6 = (-3)\cdot(-2)$. $6$ is also divisible by 6, since we can write $6 = 6\cdot 1$. However $6$ is not divisible by $4$ since there is no integer $c$ that satisfies the equation $6 = 4\cdot c$.

\medskip

\noindent{\bf Definition.} An integer $n\in\ZZ$ is called \emph{even} if it is divisible by 2. If an integer is not even, it is called \emph{odd}. An integer $n\in\ZZ$ is even if and only if there exists an integer $m\in\ZZ$ so that $n=2m$. An integer $n\in\ZZ$ is odd if and only if there exists an integer $m\in\ZZ$ so that $n=2m+1$. 

\medskip

\noindent{\bf 4. a)} Prove that if $n$ is an even integer, then $n^2$ is even. \\
{\bf b)} Prove that if $n$ is an odd integer, then $n^2$ is odd.

\medskip

\noindent{\bf 5. a)} Prove that if $n$ is an integer and $n^2$ is even, then $n$ is even.\\
{\bf b)} Prove that if $n$ is an integer and $n^2$ is odd, then $n$ is odd.\\
\emph{hint}: Question 4 might be useful.

\medskip

\noindent{\bf 6.} Prove that if $q\in\NN$ is even, then $q/2 \leq q-1$.

\medskip

\noindent{\bf Definition.} Recall our definition of the rational numbers from lecture: A rational number can be thought of as a pair of integers $(p,q)$, where $q\neq 0$. We say that the pair $(p,q)$ represents the same rational number as the pair $(p^\prime,q^\prime)$ if $pq^\prime = p^\prime q$  (equivalently, $p/q = p^\prime/q^\prime$).

\medskip

\noindent{\bf 7.} Let $(p,q)$ represent a rational number. Prove that there exists a pair $(p^\prime,q^\prime)$ representing the same rational number, so that not both of $p^\prime$ and $q^\prime$ are even. 

\medskip

\noindent{\bf 8.} Suppose that there exist integers $p$ and $q$ so that the rational number $p/q$ satisfies $(p/q)^2 = 2$. Show that this contradicts the things you have already proved in problems 1-7. 

\medskip

\noindent\emph{Hint:} A useful fact is that if $(p/q)^2 = 2$, then $p^2 = 2q^2$. Try combining this equality with the results from problems 5 and 7. This problem is more difficult than the previous ones, and the proof has a few steps. I encourage you to think about it for a while and to collaborate with your classmates if you have difficulty with it.

\medskip

\noindent{\bf Remark:} You have just proved that the square root of two is not rational. Good job!


\end{document}