\documentclass{article}
\usepackage{fullpage}
\usepackage{amsmath,amssymb,proof, multirow,multicol}
\usepackage{hyperref}
\title{CSC165, Winter 2015\\
Assignment 2\\
Due  Mar 06, 11:59 p.m.}
\renewcommand{\today}{~}
\hypersetup{pdfpagemode=Fullscreen,
  colorlinks=true,
  linkfileprefix={}}
  
  
\newcommand*{\floor}[2][]{#1\lfloor{#2}#1\rfloor}
\newcommand*{\ceil}[2][]{#1\lceil{#2}#1\rceil}

  
\begin{document}
\maketitle

%\noindent The aim of this assignment is for you to practice using quantifiers,
%implications, logical connectives and expressions.  

\begin{itemize}
	\item You may work in groups of no more than \textbf{two} students, and you should 
	produce a single solution in a PDF file named \texttt{a2.pdf}, submitted to
	\href{https://markus.cdf.toronto.edu/csc165-2015-01}{MarkUs}. Submissions must be \textbf{typed}. 
	\item The size of the PDF file \textbf{must} be less than \textbf{1MB}.
	\item \textbf{Late submission policy}: Each \textbf{group} can benefit from 
	\textbf{one} time 24-hour	grace period with no penalty.
	
	If you use your grace period for one assignment, then change your group for the 
	next one, and your new group-mate has not use his/her grace period, the new 
	group \textbf{can} submit late by 24 hours. 
	However, if both students in the group have used their grace period, the new group 
	\textbf{cannot} submit late. 
\end{itemize}
\vspace{2\baselineskip}

\noindent IMPORTANT: You \textbf{must} use the proof structures and format of this course. 
Otherwise, you won't get full mark even if your answers are correct. 

\begin{enumerate}
\setlength\itemsep{2em}
\item \textbf{Prove} or \textbf{disprove} each of the following claims.

\begin{enumerate}
\setlength\itemsep{1em}
	\item $\forall x\in\mathbb R, \forall y\in\mathbb R, \ceil{x+y}=\ceil{x}+\ceil{y}$.
	
	(Note that $\ceil{x}$ is the ceiling function. See Section 1.5 in the course notes for the definition)
	\item For all integers $x, y$, and $z$, if $x \nmid yz$ then $x \nmid y$ and $x \nmid z$. 
	
	(Note that the symbol $\nmid $ denotes ``does not divide'')
\end{enumerate}


\item Use \textbf{proof by contradiction} to prove that for all prime numbers $x, y$, and $z$, $x^2 + y^2 \neq z^2$.

Hint: It might be helpful to recall that $a^2 - b^2=(a-b)(a+b)$. 


\item Consider the definition of the floor function:
\[{\bf Def_1:}\forall x\in\mathbb R, \forall y\in\mathbb Z, (y=\floor{x}) \Leftrightarrow (y\leq x)\wedge 
			(\forall z\in\mathbb Z, (z\leq x) \Rightarrow (z\leq y)).\]
Use the proof structures of this course and ${\bf Def_1}$ to prove the following claims
\begin{enumerate}
	\setlength\itemsep{2em}
	\item ${\bf S_1:}\:\forall n\in\mathbb Z,\forall y\in\mathbb R, (0\leq y)\wedge (y<1)\Rightarrow (\floor{n+y}=n)$. 
	
	\textbf{Note}: In your proof, you may ONLY use those properties of 
	the floor function that are specified by ${\bf Def_1}$.
	
	\item ${\bf S_2:}\:\forall x\in\mathbb R,\exists y\in\mathbb R, (0\leq y)\wedge (y<1)\wedge (x=\floor{x}+y)$. 
	
	\textbf{Note}: In your proof, you may ONLY use those properties of 
	the floor function that are specified by ${\bf Def_1}$.

	\item ${\bf S_3:}\:\forall x\in\mathbb R,\forall n\in\mathbb Z, (\floor{x+n}=\floor{x}+n)$.
	
	\textbf{Note}: In your proof, you may ONLY use those properties of the floor function 
	that are specified by ${\bf Def_1}$, ${\bf S_1}$, and ${\bf S_2}$.
\end{enumerate}

\end{enumerate}

\end{document}
