\documentclass{article}
\usepackage{fullpage,amsmath}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{listings}
\usepackage{mathtools}

\DeclarePairedDelimiter\abs{\lvert}{\rvert}%
\DeclarePairedDelimiter\norm{\lVert}{\rVert}%



\title{CSC165, Summer 2014\\
Assignment 4\\
Weight: 8\% \\
Due Jul. 4th, 2:00 p.m.}
\renewcommand{\today}{~}
\hypersetup{pdfpagemode=Fullscreen,
  colorlinks=true,
  linkfileprefix={}}
\begin{document}
\maketitle

The goal of this assignment is for you to keep practicing writing proofs. Our goal this semester is for you to learn to write proofs by the end of the course, and the only way to learn to write proofs is through practice. \textbf{In your proofs, justify each step}. If you are asked to prove or disprove a claim, first determine whether the claim is true, and then prove that it is true or prove that it is false (i.e., that its negation is true), depending on which is correct.

You may work in groups of no more than two students, and \textbf{you should submit a TEX file named \texttt{a4.tex} and a PDF file named \texttt{a4.pdf} that was produced by compiling your  \texttt{a4.tex}} and that contains the answers to the questions below. These files should be submitted using
\href{https://markus.cdf.toronto.edu/csc165-2014-05/main?locale=en}{MarkUs}. \textbf{Please make sure that your files are named \texttt{a4.tex} and \texttt{a4.pdf}. You will lose marks for not submitting correctly-named files.}

For this assignment, you will \textbf{not} receive 20\% of the marks for leaving questions blank or writing ``I cannot answer this.''

You are allowed to use (i.e., put in your justifications), without proof, the following facts:

\begin{itemize}
	\item $\forall x \in \mathbb{R}, x^2 \ge 0$
	\item For $a, b, c$ real, $a>0$, $[b^2-4ac < 0] \implies [\forall x, ax^2+bx+c>=0]$
	\item $f(n) = 1/n$ is a decreasing function for $n>0$. In other words, 
		$$\forall n_1 \in \mathbb{N}, \forall n_2 \in \mathbb{N}, n_2 > n_1 \implies 1/n_2 < 1/n_1$$.
\end{itemize}

\section{Problems}

\begin{enumerate}
	\item   Prove or disprove \textbf{using a detailed structured proof, justifying every step}:
		$$\forall x \in \mathbb{Z}, \forall y \in \mathbb{Z}, [x(x+1) = y(y+1)] \Leftrightarrow [x = y]$$

	\item  Prove or disprove \textbf{using a detailed structured proof, justifying every step}:
		$$\forall x \in \mathbb{R}, \forall y \in \mathbb{R}, [(x^2 y  < 0) \land (x \neq 0)]  \Leftrightarrow [x^{100} y < 0]$$

	\item  As of Jun.17, I predict that Brazil, Germany, Italy, and Argentina will make it to the semi-finals of the FIFA World Cup. Suppose you have a group of 25 footballers from those four countries. Prove that out of those 25, there is a group of at least 6 footballers who come from the same country. \textit{It is not necessary to use the detailed structured proof format, but you still must justify every step.}


	\item  Prove or disprove the following equivalence. If you decide it is true and so need  to prove it, do not use a truth table. Justify every step in your derivation using the equivalences in Section 2.17 of the notes.
		$$ [ ( \lnot Q \land P) \lor \lnot Q ] \Leftrightarrow [(\lnot Q \land \lnot R) \lor (\lnot Q \land R)]$$


	\item  Let $R^{+}$ be the set of positive real numbers. Prove or disprove \textbf{using a detailed structured proof, justifying every step}:
		$$ \exists \epsilon \in \mathbb{R}^{+}, \forall B \in \mathbb{N}, \forall n \in \mathbb{N}, [n > B] \implies \left[\abs*{\frac{2n^2+15n}{n^2}-2} < \epsilon\right]$$

	%\item (16 pts.) Let $f(x) = \frac{2x+10}{x+3}. Prove or disprove: 
	%	$$\forall \epsilon \in \mathbb{R}, \exists \delta \in \mathbb{R},  [\epsilon > 0] \implies  [[x-1 < \delta] \implies |f(x)-$$



	\item  Assume that $D \subset \mathbb{N}$ and $D \neq \emptyset$. Prove or disprove \textbf{using a detailed structured proof, justifying every step}: 
		$$[\forall x \in D, \exists y \in \mathbb{N},  y < x] \Leftrightarrow [0 \not \in D]$$


	


	


\end{enumerate}


\end{document}
