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


%%  Common macros for the course CSC165H1F,
%%  on the St. George Campus at the University of Toronto.
%%
%%  Copyright (c) 2009-2011 Francois Pitt <fpitt@cs.utoronto.ca>
%%
%%  This work may be distributed and/or modified under the conditions of
%%  the LaTeX Project Public License, either version 1.3 of this license
%%  or (at your option) any later version.
%%  The latest version of this license is in
%%      http://www.latex-project.org/lppl.txt
%%  and version 1.3 or later is part of all distributions of LaTeX
%%  version 2003/12/01 or later.
%%
%%  This work has the LPPL maintenance status "author-maintained".
%%
%%  The Current Maintainer of this work is
%%  Francois Pitt <fpitt@cs.utoronto.ca>.
%%
%%  This work consists of the file macros-165.tex.

% Trick so that math symbols are bold when text is.
\let\seiresfb\bfseries\def\bfseries{\boldmath\seiresfb}
\let\seiresdm\mdseries\def\mdseries{\unboldmath\seiresdm}

% Spacing macros with default argument.
\newcommand*{\vstretch}[1][1]{\vspace*{\stretch{#1}}}
\newcommand*{\hstretch}[1][1]{\hspace*{\stretch{#1}}}

% General fonts and characters.
\let\altemph\textsl  % alternate way to emphasize
\let\strong\textbf  % strong emphasis
\let\latinabb\emph  % abbreviations of latin phrases
\let\code\texttt  % code fragments
\let\const\textsf  % constants
\let\term\textbf  % newly-introduced (or defined) words
\let\var\mathrm  % multi-letter variables (or constants)
\let\pred\mathbf  % predicates
\newcommand*{\txtbksl} {\symbol{"5C}}% \
\newcommand*{\txtcaret}{\symbol{"5E}}% ^
\newcommand*{\txtunder}{\symbol{"5F}}% _
\newcommand*{\txtlcurl}{\symbol{"7B}}% {
\newcommand*{\txtrcurl}{\symbol{"7D}}% }
\newcommand*{\txttilde}{\symbol{"7E}}% ~
\newcommand*{\N}{\ensuremath{\mathbb{N}}}  % requires amssymb
\newcommand*{\Z}{\ensuremath{\mathbb{Z}}}  % requires amssymb
\newcommand*{\Q}{\ensuremath{\mathbb{Q}}}  % requires amssymb
\newcommand*{\R}{\ensuremath{\mathbb{R}}}  % requires amssymb
\newcommand*{\bigOh}{\mathcal{O}}
\newcommand*{\onehalf}{\ensuremath{{}^1\!\!/\!_2}}

% Abbreviations of latin phrases.
\newcommand*{\ie}{\latinabb{i.e.}}
\newcommand*{\eg}{\latinabb{e.g.}}
\newcommand*{\etc}{\latinabb{etc}}
\newcommand*{\vs}{\latinabb{vs}}

% General math macros.
\newcommand*{\comp}[1]{\overline{#1}}  % set complement
\newcommand*{\emptystr}{\varepsilon}  % empty string
\newcommand*{\lequiv}{\mathrel{\ \Longleftrightarrow\ }}  % equivalence
\newcommand*{\lxor}{\oplus}  % exclusive or
\newcommand*{\cat}{\cdot}  % string concatenation
\newcommand*{\invisible}[1]{\mathrel{\hphantom{#1}}}
% floors and ceilings, with optional size-changing command,
% e.g., \floor[\Big]{x/2} generates '\Big\lfloor{x/2}\Big\rfloor'
\newcommand*{\floor}[2][]{{#1\lfloor}{#2}{#1\rfloor}}
\newcommand*{\ceil}[2][]{{#1\lceil}{#2}{#1\rceil}}
\newcommand*{\lcm}{\operatorname{lcm}}  % requires amsmath
\newcommand*{\size}{\operatorname{size}}  % requires amsmath

% Redefined symbols from amssymb.
\renewcommand*{\emptyset}{\varnothing}  % rounder than default
\let\bigiff\iff
\renewcommand*{\iff}{\mathrel{\Leftrightarrow}}  % smaller than default
\let\bigimplies\implies
\renewcommand*{\implies}{\mathrel{\Rightarrow}}  % smaller than default
\renewcommand*{\ge}{\geqslant}  % with slanted line under the > sign
\renewcommand*{\le}{\leqslant}  % with slanted line under the < sign

% For algorithms, in Python.
\let\kw\textbf  % keywords
\let\proc\textsc  % function names
\newcommand*{\opgets}[1]{\mathrel{#1=}}
\newcommand*{\eq}{\mathrel{==}}
\newcommand*{\True}{\const{True}}
\newcommand*{\False}{\const{False}}
\newcommand*{\None}{\const{None}}
\newcommand*{\cmod}{\mathbin{\%}}
\newcommand*{\len}{\operatorname{len}}  % requires amsmath

% Like {itemize} but using less vertical space.
\newenvironment*{points}
 {\ifvmode\else\unskip\par\fi\begin{list}{$\bullet$}
   {\setlength{\topsep}{.25ex plus .125ex minus .1825ex}
    \setlength{\itemsep}{\topsep}\setlength{\parsep}{0ex}
    \setlength{\leftmargin}{1.75em}\setlength{\labelsep}{.5em}
    \setlength{\labelwidth}{1.75em}}\ignorespaces}
 {\ifvmode\else\unskip\fi\end{list}\ignorespaces}

% Checkboxes and checklists.
\newcommand*{\cbox}[1]{{\fboxrule.125ex\fboxsep0ex
    \framebox[2.75ex]{\rule[-.75ex]{0ex}{2.75ex}\smash{#1}}}}
\newcommand*{\cmark}{\raisebox{.0625ex}{$\surd$\kern.125ex}}
\newcommand*{\xmark}{\raisebox{-.1875ex}{\kern.0625ex{X}}}
\newcommand*{\checkbox}{{\sf\cbox{}}}
\newcommand*{\checkedbox}{{\sf\cbox{\cmark}}}
\newcommand*{\markedbox}{{\sf\cbox{\xmark}}}
\newenvironment{checklist}{\begin{list}{\checkbox}{}}{\end{list}}
\newcommand*{\checkeditem}{\item[\checkedbox]}
\newcommand*{\markeditem}{\item[\markedbox]}

% Proof-related environments and macros.
\newcommand*{\just}{{\quad\#\ }}  % justification for a proof step
\newenvironment*{pindent}
   {\begin{list}{}
       {\topsep 0pt
        \partopsep 0pt
        \itemsep 0pt
        \parsep 0pt
        \parskip 0pt}\item\relax}
   {\unskip\end{list}\ignorespaces}
% Usage: \begin{assumption}[<pre-text>]{<assumption>}
%          ...body...
%        \end{assumption}{<conclusion>}
% is formatted as
%    <pre-text> assume <assumption>
%        ...body...
%    <conclusion>
% or if <pre-text> is empty,
%    Assume <assumption>
%        ...body...
%    <conclusion>
\newenvironment*{assumption}[2][]
   {\unskip\ifvmode\else\par\fi
    {#1} \ifx\empty#1\empty\expandafter\uppercase\fi{a}ssume {#2}
    \begin{pindent}}
   {\end{pindent}}
% Usage: \begin{pickavalue}[<pre-text>]{<names>}
%          ...body...
%        \end{pickavalue}{<conclusion>}
% is formatted as
%    <pre-text> let <names>
%    ...body...
%    <conclusion>
% or if <pre-text> is empty,
%    Let <names>
%    ...body...
%    <conclusion>
\newenvironment*{pickavalue}[2][]
   {\unskip\ifvmode\else\par\fi
    {#1} \ifx\empty#1\empty\expandafter\uppercase\fi{l}et {#2}
    \par\ignorespaces}
   {\unskip\par\ignorespaces}



\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

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}



\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]$$
{\bf Solution:} 
The statement is \textbf{false}.

Proof:
\begin{pindent}
Let $x_0 = -1$, $y_0 = 0$\\
Then $x_0 \in \mathbb{Z}$, $y_0 \in \mathbb{Z}$\\
Then $x_0(x_0 + 1) = 0$ \just{$x_0+1=0$}\\
Then $y_0(y_0 + 1) = 0$ \just{$y_0 = 0$}\\
Then $x_0 (x_0 + 1) = y_0 (y_0 + 1)$\just{both equal 0}\\
Then also $\lnot[x_0  = y_0]$\just{$-1 \neq 0$}\\
Then $ [x(x+1) = y(y+1)] \land \lnot[x = y]$\just{conjunction of two true statements}\\
Then $\exists x \in \mathbb{Z}, \exists y \in \mathbb{Z}, [x(x+1) = y(y+1)] \land \lnot[x = y]$ \just{$x_0, y_0$ are such $x, y$}\\
Then $\exists x\in \mathbb{Z}, \exists y \in \mathbb{Z}, \lnot([x(x+1) = y(y+1)] \Rightarrow [x = y])$ \just{implication negation}\\
Then $\exists x\in \mathbb{Z}, \exists y\in \mathbb{Z}, [\lnot([x(x+1) = y(y+1)] \Rightarrow [x = y])] \lor [\lnot([x(x+1) = y(y+1)] \Leftarrow [x = y])]$ \just{True $\lor$ R is True for any R}\\
Then $\exists x\in \mathbb{Z}, \exists y\in \mathbb{Z}, \lnot([x(x+1) = y(y+1)] \Leftrightarrow [x = y])$\just{equivalence negation}\\
Then $\exists x\in \mathbb{Z}, \lnot [\forall y\in \mathbb{Z}, [x(x+1) = y(y+1)] \Leftrightarrow [x = y]]$\just{quantifier negation}\\
Then $\lnot [\forall x\in \mathbb{Z},  \forall y\in \mathbb{Z}, [x(x+1) = y(y+1)] \Leftrightarrow [x = y]]$\just{quantifier negation}\\
%   \hspace*{13cm}\includegraphics[height=0.5cm]{soccer2}
\end{pindent}

Note: less detailed arguments that still end with the same conclusion may be fine.

\newpage

	\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]$$
{\bf Solution:}
The statement is \textbf{true}.

Proof:
\begin{pindent}
	\begin{assumption}{$x \in \mathbb{R}, y \in \mathbb{R}$}
		Then $x^{49} \in \mathbb{R}$ \just{the reals are closed under multiplication and $x^{49} = x*x*x*...*x$}   \\
		Also $x^{49} \neq 0$ \just{$\forall x \in \mathbb{R}, x = 0 \iff x^n = 0$ } \\
		Then $(x^{49})^2 > 0$ \just{$\forall a \in \mathbb{R}, a \neq 0 \implies a^2 > 0$ }\\
		Then $x^{98} > 0$ \just{algebra}\\
		\begin{assumption}{$(x^2 y  < 0) \land (x \neq 0)$}
			    Then $x^{98} (x^2 y < 0)$ \just{$\forall a \in \mathbb{R}, \forall b \in \mathbb{R}, [a>0, b < 0] \implies ab < 0$}\\
			    Then $x^{100} y < 0$ \just{algebra/associativity of multiplication}\\
		\end{assumption}{Then $[(x^2 y  < 0) \land (x \neq 0)]  \implies [x^{100} y < 0]$}\just{assuming the antecedent leads to the consequent}\\
	
		\begin{assumption}{$x^{100} y < 0$}
			Then $x^{98} (x^2 y) < 0$ \just{algebra/associativity of multiplication}\\
			Also $1/x^{98}>0$ \just{$\forall a \in \mathbb{R}, a>0 \implies 1/a>0$}
			Then $(1/x^{98}) x^{98} (x^2 y) < (1/x^{98}) 0$ \just{multiply both sides by the same value}\\
			Then $x^{2} y < 0$ \just{algebra}\\
		\end{assumption}{Then $[x^{100} y < 0] \implies [(x^2 y  < 0) \land (x \neq 0)] $}\just{assuming the antecedent leads to the consequent}
		Then $[(x^2 y  < 0) \land (x \neq 0)]  \Leftrightarrow [x^{100} y < 0]$ \just{equivalence}\\
  \end{assumption}{Then $\forall x \in \mathbb{R}, \forall y \in \mathbb{R}, [(x^2 y  < 0) \land (x \neq 0)]  \Leftrightarrow [x^{100} y < 0]$}\just{introduce universal}\\
%   \hspace*{13cm}\includegraphics[height=0.5cm]{soccer2}\\
\end{pindent}

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

{\bf Solution:}
The statement is \textbf{true}.

Proof:
\begin{pindent}
  Let $N_c$ be the number of footballers in the group who come from country c $\in$ \{Brazil, Italy, Argentina, Germany\}\\
  Let $N$ be the total number of footballers in the group
  \begin{assumption}{there is no group of 6 footballers who come from the same country and $N = 25$} 
	Then $\forall c \in$ {Brazil, Italy, Argentina, Germany}, $N_c \le 5$\just{By assumption, the natural number $N_c$ is smaller than 6}\\
	Then $N = N_{Brazil}+N_{Italy}+N_{Argentina}+N_{Germany} \le 5+5+5+5=20$ \just{Only footballers from the 4 countries are in the group + substitution}\\
	But it is not the case that $25\le 20$\just{arithmetic, we assumed that $N=25$}\\
          Contradiction!	
  \end{assumption}{Then there is a group of at least 6 footballers who come from the same country} \just{assuming otherwise leads to a contradiction}\\
%   \hspace*{13cm}\includegraphics[height=0.5cm]{soccer2}
\end{pindent}


\newpage

	\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)]$$
{\bf Solution:}
The statement is \textbf{true}.

\begin{pindent}
  Proof:
  \begin{align*}
  (\lnot Q \land P) \lor \lnot Q & \Leftrightarrow  (\lnot Q \land P) \lor (\lnot Q \land (P \lor \lnot P)) \just{identity \text{ } laws}\\
  & \Leftrightarrow  (\lnot Q \land P) \lor (\lnot Q \land P) \lor (\lnot Q \land \lnot P) \just{distributive \text{ } laws}\\
  & \Leftrightarrow (\lnot Q \land P) \lor (\lnot Q \land \lnot P) \just{idempotency \text{ } laws}\\
  & \Leftrightarrow (\lnot Q \land (P \lor \lnot P)) \just{distributive \text{ } laws}\\
  & \Leftrightarrow \lnot Q \just{identity \text{ } laws}\\
  & \Leftrightarrow \lnot Q \land (\lnot R \lor R) \just{identiy \text{ } laws}\\
  & \Leftrightarrow (\lnot Q \land \lnot R) \lor (\lnot Q \land R) \just{distributive \text{ } laws}
  \end{align*}
   \hspace*{13cm}\includegraphics[height=0.5cm]{soccer2}
\end{pindent}
  

	\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]$$
{\bf Solution:}
The statement is \textbf{true}.\\
Proof:
\begin{pindent}
  Let $\epsilon_0 = 16$\\
  \begin{assumption}{$B \in \mathbb{N}, n \in \mathbb{N}$}
	\begin{assumption}{$n > B$} 
		  Then $B \geq 0$ \just{The smallest natural number is zero}\\		
		  Then $n \geq 1$ \just{$n>B\ge 0$}\\		
		  Then $\abs{\frac{2n^2+15n}{n^2}-2} = \abs{\frac{15}{n}} = \frac{15}{n} \leq 15$ \just{algebra, 		$\forall n_1 \in \mathbb{N}, \forall n_2 \in \mathbb{N}, n_2 > n_1 \implies 1/n_2 < 1/n_1$ applied to $n_1 = 1$}\\
		Then $\abs{\frac{2n^2+15n}{n^2}-2} < \epsilon_0$ \just{$16>15$}
	\end{assumption}{Then $[n > B] \implies  \abs{\frac{2n^2+15n}{n^2}-2} < \epsilon_0$ \just{assuming the antecedent implies the consequent} }
  \end{assumption}
  Then $\forall B \in \mathbb{N}, \forall n \in \mathbb{N}, [n > B] \implies \left[\abs*{\frac{2n^2+15n}{n^2}-2} < \epsilon\right]$\just{introduce universal}\\
  Then $\exists \epsilon \in 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]$\just{$\epsilon_0 = 16$ is such an $\epsilon$}\\ 	
%   \hspace*{13cm}\includegraphics[height=0.5cm]{soccer2}\\
\end{pindent}

\newpage

	\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]$$
{\bf Solution:}
The statement is \textbf{true}.

Proof:

\begin{pindent}
  \begin{assumption}{$0 \in D$}
    Let $x_0 = 0$\\
    Then $x_0 \in D$\\
    Then $\forall y \in \mathbb{N}, y\geq x_0$  \just{$0$ is the smallest  natural number}\\
    Then $\exists x\in D, \forall y \in \mathbb{N}, y\geq x$ \just{$x_0$ is such an x}\\
    Then $\lnot (\forall x\in D, \exists y \in \mathbb{N}, y<x$) \just{quantifier negation}
  \end{assumption}{Then $0 \in D \Rightarrow \lnot (\forall x\in D, \exists y \in \mathbb{N}, y<x$} \just{assuming the antecedent leads to the consequent}
  Then $\forall x\in D, \exists y \in \mathbb{N}, y<x \Rightarrow 0 \not \in D$ \just{contrapositive} \\

  \begin{assumption}{$0 \not \in D$}
	\begin{assumption}{$x \in D$}	
		Then $x \neq 0$\just{$0 \not in D$ but $x \in D$}
  		Let $y_0 = 0$\\
	  	Then $y_0 \in \mathbb{N}$ \just{definition of naturals}\\
	  	Then $\forall x\in D, y_0 < x$ \just{the minimum natural number is $0$ and $0 \not \in D$ so $x \neq 0$}\\ 
		Then $\exists y\in \mathbb{N}, y < x$ \just{$y_0$ is such a $y$}
	\end{assumption}{Then  $\forall x\in D, \exists y\in \mathbb{N}, y < x$}\just{introduce universal}
  \end{assumption}{Then $[0 \not \in D] \implies [\forall x\in D, \exists y\in \mathbb{N}, y < x]$} \just{assuming the antecedent implies the consequent}\\


Then $\forall x\in D, \exists y \in \mathbb{N}, y<x \Leftrightarrow 0 \not \in D$ \just{equivalence}\\
%   \hspace*{13cm}\includegraphics[height=0.5cm]{soccer2}\\
\end{pindent}

	


	


\end{enumerate}


\end{document}
