\documentclass[10pt]{article}

\usepackage[margin=1in]{geometry}
\usepackage[small]{titlesec}
\usepackage{palatino, mathpazo}
\usepackage{inconsolata}
\usepackage{amsmath, amssymb}
\usepackage{enumerate}
\usepackage{graphicx}

\newcommand{\ds}{\displaystyle}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Var}{\operatorname{Var}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\PP}{\mathcal{P}}

\setlength{\parindent}{0pt}
\setlength{\parskip}{1.5ex}

\title{\sc Math 2100 / 2105 / 2350 -- Homework 2}
\author{due Wednesday, \textbf{February 20}, at the beginning of class\\[10pt]
\emph{This is due on the day of Exam 1. If you would like to have these problems \underline{graded} before}\\
\emph{the Exam, I will allow you to submit it on Monday, February 18, and I will have it graded}\\
\emph{for you to pick up on Tuesday, February 19.}\\[10pt]
Sections 1.4, 1.5, 3.1, 3.2}
\date{}
\begin{document}
\maketitle

\begin{center} 
	\emph{This homework assignment was written in \LaTeX{}. You can find the source code on the course website.}
\end{center}

\textbf{Instructions:} This assignment is due at the \emph{beginning} of class. \textbf{Staple your work} together (do not just fold over the corner). Please write the questions in the correct order. If I cannot read your handwriting, you won't receive credit. Explain all reasoning.

\textbf{Mathematical Writing:} An important component of this course is learning how to write mathematics correctly and concisely. Your goal should always be the convince the reader that you are correct! That means explaining your thinking and each step in your solution. We will talk more about this when we cover formal proofs in a few weeks, but for now I expect you to do the following: explain your reasoning, don't leave out steps, and use full sentences with correct spelling and grammar (including your use of math symbols). For example, don't write ``$3 \in S \Longrightarrow 3 \not\in \overline{S}$''; instead, write ``Since $3 \in S$, it follows that $3 \not\in \overline{S}$''.

\begin{enumerate}
	\item In each of the following pairs, one of the statements implies the other. Decide \emph{without using a truth table} which one implies the other. Do this by thinking about the meaning of both sides, and, as always, \underline{explain your reasoning}.\\[5pt]
	\begin{tabular}{lll}
		(a) \hspace*{0.3in} & $q$ \hspace*{2in} & $p \to q$\\[10pt]
		(b) & $\forall y, \exists x, P(x,y)$ & $\exists x, \forall y, P(x,y)$\\[10pt]
		(c) & $s \wedge (p \to q) \wedge ((\neg p)\to q)$ & $(q \vee r)$\\[10pt]
		(d) & $(\forall x, P(x)) \vee (\forall x, \neg P(x))$ & $(\exists x, P(x)) \to (\forall x, P(x))$
	\end{tabular}
	
	\item Express each of the following statements using predicates and quantifiers. (You do not need to prove them!)
	\begin{enumerate}
		\item If $n$ is a multiple of $5$, then $n$ ends in $5$ or $n$ ends in $0$.
		\item If $n$ is not a multiple of $3$, then $n^2 - 1$ is a multiple of $3$
		\item For all odd integers $a$ and $b$, there is no real number $x$ such that $x^2 + ax + b = 0$.
		\item For every real number $y$, if $y \geq 0$, then there exists $x \in \R$ such that $x^2 = y$.
	\end{enumerate}
	
	\item Write each of the following statements as a predicate with quantifiers. For each one you should clearly state what your predicate is (e.g., $P(a,b) = ``\text{person $a$ is friends with person $b$}''$) and then write the quantified version. Be certain that your predicate has no hidden quantifiers in it. For example, $P(b) = ``\text{everyone is friends with person $b$}''$ secretly has a $\forall$ quantifier hidden in it.
	\begin{enumerate}
		\item There is a car that everyone wants to buy.
		\item Every student has a favorite food.
		\item Every dorm has an RA that nobody likes. 
	\end{enumerate}
	
	\item Write the symbolic negation of each statement in \#3, then translate the negation to English.

	\item Use a Venn Diagram to determine whether the equation below is true.
	\[
		(A \cap B) \cup (A \cap C) = A \smallsetminus (\overline{B} \cap \overline{C}).
	\]
	
	\item Write each of the following sets in set-builder notation.
	\begin{enumerate}
		\item The set $S$ of integers that are multiples of 3 and a prefect square.
		\item The set $T$ of positive integers that are bigger than $10$ and whose ones digit is a 5.
		\item The set $R$ of pairs $(a,b)$ of real numbers whose sum is a multiple of 3.
	\end{enumerate}
	
	\item List five elements in each of the following sets, unless there are fewer than 5 elements in the set (in which case, justify how you know you've listed all of the elements).
	\begin{enumerate}
		\item $A = \{x \in \R : x^2 \in \N\}$
		\item $B = \{S \subseteq \{1,2,3,4\} : \text{the sum of the elements of $S$ is even}\}$
		\item $C = \{q \in \N : q = 2k \text{ for some $k\in\N$ and }q=2\ell+1\text{ for some $\ell\in\N$}\}$
	\end{enumerate}

	\item Let $n$ be a positive integer and define $N = \{1, 2, \ldots, n\}$ to be the set of positive integers from $1$ to $n$. For example, if $n = 4$, then $N = \{1,2,3,4\}$. Each of the following answers should have the variable $n$ in it.
	\begin{enumerate}
		\item What is the size of the set $N \times N$?
		\item What is the size of the set $\{(a,b) \in N \times N : a \neq b\}$?
	\end{enumerate}
	
		\item Determine whether the statement below is true or false. If true, give a few sentences of justification (not a formal proof). If false, give specific examples of sets for which the two sides are not equal.
	\begin{center}
		For all sets $A$, $B$, and $C$: if $B \subseteq C$, then $A \times B \subseteq A \times C$.
	\end{center}
	
	\item Determine whether the statement below is true or false. If true, give a few sentences of justification (not a formal proof). If false, give specific examples of sets for which the two sides are not equal.
	\begin{center}
		For all sets $A$, $B$, and $C$: $(A \cup B) \times (A \smallsetminus B) = (A \times A) \smallsetminus (B \times B)$.
	\end{center}


\end{enumerate}
\end{document}


