\documentclass[11pt]{amsart}
\usepackage{geometry}                % See geometry.pdf to learn the layout options. There are lots.
\geometry{letterpaper}                   % ... or a4paper or a5paper or ... 
%\geometry{landscape}                % Activate for for rotated page geometry
%\usepackage[parfill]{parskip}    % Activate to begin paragraphs with an empty line rather than an indent
\usepackage{amsfonts, amscd, amssymb, amsthm, amsmath}
\usepackage{pdfsync}%leaves makers for tex searching
\usepackage{enumerate}

%%%%% Margins %%%%% 
\setlength{\topmargin}{1in} %top/bot margins
\setlength{\oddsidemargin}{\topmargin} %sidemargins

\setlength{\textheight}{11in} \setlength{\textwidth}{8.5in}
\setlength{\hoffset}{-1in} \setlength{\voffset}{-1in} \setlength{\evensidemargin}{\oddsidemargin} \addtolength{\textheight}{-2 \topmargin}\addtolength{\textwidth}{-2\oddsidemargin}
\setlength{\headheight}{0pt} \setlength{\headsep}{20pt} \setlength{\footskip}{20pt}
\addtolength{\textheight}{-\footskip} \addtolength{\textheight}{-\headheight} \addtolength{\textheight}{-\headsep}



%%%%% Theorems %%%%% 
\theoremstyle{plain}
	\newtheorem{thm}{Theorem}
	\newtheorem*{thm*}{Theorem}
	\newtheorem{lemma}[thm]{Lemma}
	\newtheorem{prop}[thm]{Proposition}
	\newtheorem{cor}[thm]{Corollary}
\theoremstyle{definition}
	\newtheorem*{defn}{Definition}
	\newtheorem{remark}[thm]{Remark}
\theoremstyle{example}
	\newtheorem*{example}{Example}


%%%%% Pictures %%%%% 
%\usepackage{etex} %fixes the fight that pictex has with every other drawing package
%\usepackage{pictexwd}
\usepackage{tikz}
%\usepackage{graphicx}
\usepackage{epstopdf}
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `dirname #1`/`basename #1 .tif`.png}
\usepackage[pdftex,bookmarks]{hyperref}

\usepgflibrary{shapes.geometric}
\tikzstyle{V}=[draw, fill =black, circle, inner sep=0pt, minimum size=1.5pt]
\tikzstyle{over}=[draw=white,double=black,line width=2pt, double distance=.5pt]


\newcommand\TikZ[1]{\begin{matrix}\begin{tikzpicture}#1\end{tikzpicture}\end{matrix}}


%PARTITIONS
\newcounter{r}
\newcommand\Part[1]{
        \setcounter{r}{1}
	 \foreach \x in {#1}{
 	{\ifnum\value{r}=1
		\draw (0,\value{r}-1)--(\x,\value{r}-1); 
		\fi}
	\draw (0,\value{r}) to (\x,\value{r});
   	\foreach \y in {0, ..., \x} {\draw (\y,\value{r})--(\y,\value{r}-1);}
	\addtocounter{r}{1}
 }}
 \def\PartUNIT{.175}
%Self-contained tikz images for \Part above. 
\newcommand{\PART}[1]{
\begin{matrix}
\begin{tikzpicture}[xscale=\PartUNIT, yscale=-\PartUNIT] 
	\Part{#1}
\end{tikzpicture}
\end{matrix}
}


%BRAIDS:
\def\Over[#1,#2][#3,#4]{ %1,2=start position; 3,4=end position
	\draw[style=over]   (#1,#2) .. controls ++(0,#4*.5-#2*.5) and ++(0,-#4*.5+#2*.5) .. (#3,#4);}
\def\Under[#1,#2][#3,#4]{ %1,2=start position; 3,4=end position
	\draw  (#1,#2) .. controls ++(0,#4*.5-#2*.5) and ++(0,-#4*.5+#2*.5) .. (#3,#4);}
\def\Cross[#1,#2][#3,#4]{%Mimic over, under follows
	\Under[#3,#2][#1,#4]\Over[#1,#2][#3,#4]}
\def\Tops[#1][#2][#3]{%1=pole locations, 2=top, 3=k 
	\foreach\x in {#1}{
		\draw (\x+.1,#2) -- (\x+.1,#2+.15) (\x-.1,#2) -- (\x-.1,#2+.15) ;
		\draw (\x+.1,#2+.15) arc (0:360:1mm and .5mm);}
	%Nodes 
	\foreach \x in {1,...,#3} {\draw (\x,#2)  to (\x,#2+.05) node[V]{};}
	}
\def\Bottoms[#1][#2][#3]{%1=pole locations, 2 = bottom, 3=top 
	\foreach\x in {#1}{
		\draw (\x+.1,#2) -- (\x+.1,#2-.1) (\x-.1,#2) -- (\x-.1,#2-.1) ;
		\draw (\x+.1,#2-.1) arc (0:-180:1mm and .5mm);}
	%Nodes 
	\foreach \x in {1,...,#3} {\draw (\x,#2)  to (\x,#2-.05) node[V]{};}
	}
\def\Caps[#1][#2,#3][#4]{%1=pole locations, 2 = bottom, 3=top, 4=k 
	\Tops[#1][#3][#4]
	\Bottoms[#1][#2][#4]
	}
\def\Pole[#1][#2,#3]{%1=horizontal location, 2 = bottom, 3=top
	\shade[left color=white,right color=white] (#1+.1,#2) rectangle (#1-.1,#3);
	\draw[over] (#1+.1,#2) to (#1+.1,#3) (#1-.1,#2) to (#1-.1,#3) ;}
\def\Label[#1,#2][#3][#4]{%1,2 = top/bot position, 3=i, 4=label
	\node[above] at (#3,#2+.1) {#4};
	\node[below] at (#3,#1-.1) {#4};		}
	
	
%%%%% Color  %%%%% 
\usepackage{color}
\definecolor{dred}{rgb}{.65, 0, 0.15}
\newcommand{\NOTE}[1]{{\color{blue}#1}}
\newcommand{\MOVED}[1]{{\color{gray}#1}}
\newcommand{\blue}[1]{{\color{blue} #1 }}


%%%%% Alphabets %%%%% 
\def\cA{\mathcal{A}}\def\cB{\mathcal{B}}\def\cC{\mathcal{C}}\def\cD{\mathcal{D}}\def\cE{\mathcal{E}}\def\cF{\mathcal{F}}\def\cG{\mathcal{G}}\def\cH{\mathcal{H}}\def\cI{\mathcal{I}}\def\cJ{\mathcal{J}}\def\cK{\mathcal{K}}\def\cL{\mathcal{L}}\def\cM{\mathcal{M}}\def\cN{\mathcal{N}}\def\cO{\mathcal{O}}\def\cP{\mathcal{P}}\def\cQ{\mathcal{Q}}\def\cR{\mathcal{R}}\def\cS{\mathcal{S}}\def\cT{\mathcal{T}}\def\cU{\mathcal{U}}\def\cV{\mathcal{V}}\def\cW{\mathcal{W}}\def\cX{\mathcal{X}}\def\cY{\mathcal{Y}}\def\cZ{\mathcal{Z}}

\def\AA{\mathbb{A}} \def\BB{\mathbb{B}} \def\CC{\mathbb{C}} \def\DD{\mathbb{D}} \def\EE{\mathbb{E}} \def\FF{\mathbb{F}} \def\GG{\mathbb{G}} \def\HH{\mathbb{H}} \def\II{\mathbb{I}} \def\JJ{\mathbb{J}} \def\KK{\mathbb{K}} \def\LL{\mathbb{L}} \def\MM{\mathbb{M}} \def\NN{\mathbb{N}} \def\OO{\mathbb{O}} \def\PP{\mathbb{P}} \def\QQ{\mathbb{Q}} \def\RR{\mathbb{R}} \def\SS{\mathbb{S}} \def\TT{\mathbb{T}} \def\UU{\mathbb{U}} \def\VV{\mathbb{V}} \def\WW{\mathbb{W}} \def\XX{\mathbb{X}} \def\YY{\mathbb{Y}} \def\ZZ{\mathbb{Z}}  

\def\fa{\mathfrak{a}} \def\fb{\mathfrak{b}} \def\fc{\mathfrak{c}} \def\fd{\mathfrak{d}} \def\fe{\mathfrak{e}} \def\ff{\mathfrak{f}} \def\fg{\mathfrak{g}} \def\fh{\mathfrak{h}} \def\fj{\mathfrak{j}} \def\fk{\mathfrak{k}} \def\fl{\mathfrak{l}} \def\fm{\mathfrak{m}} \def\fn{\mathfrak{n}} \def\fo{\mathfrak{o}} \def\fp{\mathfrak{p}} \def\fq{\mathfrak{q}} \def\fr{\mathfrak{r}} \def\fs{\mathfrak{s}} \def\ft{\mathfrak{t}} \def\fu{\mathfrak{u}} \def\fv{\mathfrak{v}} \def\fw{\mathfrak{w}} \def\fx{\mathfrak{x}} \def\fy{\mathfrak{y}} \def\fz{\mathfrak{z}}
\def\fgl{\mathfrak{gl}}  \def\fsl{\mathfrak{sl}}  \def\fso{\mathfrak{so}}  \def\fsp{\mathfrak{sp}}  
\def\GL{\mathrm{GL}} \def\SL{\mathrm{SL}}  \def\SP{\mathrm{SL}}

\def\<{\langle} \def\>{\rangle}
\def\ad{\mathrm{ad}} 
\def\Alg{\mathrm{Alg}}
\def\Aut{\mathrm{Aut}}
\def\dim{\mathrm{dim}} 
\def\End{\mathrm{End}} 
\def\ev{\mathrm{ev}} 
\def\half{\hbox{$\frac12$}}
\def\Hom{\mathrm{Hom}} 
\def\id{\mathrm{id}}
\def\img{\mathrm{img}}
\def\Ind{\mathrm{Ind}}
\def\Irr{\mathrm{Irr}} 
\def\ker{\mathrm{ker}}
\def\Lie{\mathrm{Lie}}
\def\normeq{\unlhd}
\def\qtr{\mathrm{qtr}} 
\def\rad{\mathrm{rad}} 
\def\Res{\mathrm{Res}} 
\def\tr{\mathrm{tr}} 
\def\Tr{\mathrm{Tr}} 
\def\vep{\varepsilon}
\def\wt{\mathrm{wt}}
\pagestyle{empty}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{Proof Lab I: Direct proof}
\author{}
\begin{document}


\maketitle

\noindent{\textbf{Instructions:}}

\smallskip

\begin{center}
\fbox{
  \begin{minipage}{15cm}

\noindent \textbf{Step 1 (Today).} \\
Work together with your group to finish the full set of exercises.\\

\noindent \textbf{Step 2 (This weekend and next week).} \\
Each person: pick 8 $ \star$'s worth of exercises, and write up careful drafts of the proofs. Include key definitions and thorough reasoning---think about writing to convince a student taking Bridge next semester. Make sure a novice could follow and locate all critical components of the proof. \textbf{See portfolio guidelines for further instruction.}\\

\noindent \textbf{Step 3 (By next Thursday).} \\
Swap drafts with a peer editor. (Consider getting a peer's email address and sending them a pdf before class on Thursday.)\\

\noindent Provide written constructive criticism for your partner: Are key definitions included? Is the reasoning mathematically accurate? Are the key components of the proof easy to recognize? Is the notation clear? Would a few additional comments help a novice reader to follow more easily? Can the explanation be made more clean and concise?\\

\noindent \textbf{Step 4 (Tuesday 10/16).} \\ 
Turn in your proof second drafts, and comments from at least one peer editor on first drafts. (You will provide two versions of each proof--one first draft with comments, and one rewritten draft. Homework without peer editor comments will not be accepted.)
\end{minipage}}
\end{center}

\vfill

\noindent \textbf{Note:} To prove that multiple statements $X_1, X_2, \dots, X_n$ are all \emph{equivalent}, we showed on Homework 6 \#3 that you can either prove \\\smallskip
\centerline{(1) $X_1 \Leftrightarrow X_2$, $X_2 \Leftrightarrow X_3$, \dots, and $X_{n-1} \Leftrightarrow X_n$, \qquad or \qquad (2) $X_1 \Rightarrow X_2 \Rightarrow \cdots \Rightarrow X_n \Rightarrow X_1$.} 

\thispagestyle{empty}

\vfill
\begin{thm*}[Binomial theorem]
For all real numbers $a$ and $b$, and non-negative integers $n$, we have 
$$(a + b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k},$$
where $\binom{n}{k} = \text{``$n$ choose $k$''} = \frac{n!}{k!(n-k)!}$.
\end{thm*}
\noindent Recall that $n! = n(n-1) \cdots 2 \cdot 1$, where $0! = 1$. In particular, $\binom{n}{k}$ is the number of ways to pick a subset of size $k$ from a set of size $n$. 

\medskip

\noindent{\bf Example:} We have 
$$\binom{4}{0} = \frac{4!}{0!4!} = 1, \quad 
	\binom{4}{1} = \frac{4!}{1!3!} = 4, \quad 
	\binom{4}{2} = \frac{4!}{2!2!} = 6, \quad 
	\binom{4}{3} = \frac{4!}{3!1!} = 4, ~\text{ and } ~
	\binom{4}{4} = \frac{4!}{4!0!} = 1.$$
So $(a + b)^4 = a^4 + 4a^3 b + 6 a^2 b^2 + 4 a b^3 + b^4$. 

\vfill
\pagebreak

\noindent{\bf Problems. } Complete each of the following using a direct proof.

\vfill

\begin{enumerate}[I.]
\item ($\star$) Show that for positive real numbers $x$ and $y$, we have $x > y$ if and only if $x^2 > y^2$. 

\vfill

\item ($\star$) Let $x$ be an integer. Prove that $x^n$ is odd if and only if $x$ is odd. \\
(Hint: One direction uses  the ``binomial theorem'', given above.)


\vfill

\item ($\star$ $\star$) Let $f: X \to Y$ be a function between two sets $X$ and $Y$. Suppose $A$ and $B$ are subsets of $X$. Show that $f(A\cup B) = f(A) \cup f(B)$.

\vfill

\item ($\star$ $\star$) Let $X$ be a set, and let $A$ and $B$ be subsets of $X$. Prove $B - A = (A \cup B) - A$. 

\vfill


\item ($\star$ $\star$ $\star$) Suppose $x$ and $y$ are rational numbers such that $x < y$. Prove that there exists $z \in \QQ$ such that $x < z < y$. That is, between every two rationals there exists another rational.

\vfill

\item ($\star$ $\star$ $\star$) Prove that the following statements are equivalent for $A$ and $B$ subsets of $X$. 
\begin{enumerate}[(i)]
\item  $A\subseteq B$,
\item  $A \cap B^c = \emptyset$,
\item $A^c \cup B=X$.
\end{enumerate}

\vfill

\item ($\star$ $\star$ $\star$)
Prove that the following statements are equivalent.
\begin{enumerate}[(i)]
\item There exists unique $x$ such that $P (x)$ is true.
\item There exists $x$ such that (a) $P(x)$ holds and (b) for all  $y$, we have $P(y) \Rightarrow y = x$.
\item There exists $x$ so that for all $y$, $P(y)$ is true if and only if $y=x$.
\item There exists $x$ such that $P(x)$ holds, and for all $y$ and $z$, we have $(P(y) \land P(z)) \Rightarrow y = z$.
\end{enumerate}

\vfill

\item ($\star$ $\star$ $\star$) Let $x_1$, $x_2$, $x_3$, \dots $x_n$ be an arrangement of the numbers $1, 2, 3, \dots n$. 
(For example if $n = 5$ we could have $x_1=4, x_2 = 3, x_3 = 5, x_4 = 1, x_5 = 2$.) Prove that if $n$ is odd, then $(x_1 - 1) (x_2 - 2)(x_3 - 3)\cdots(x_n - n)$ is even. \\
(Hint: Consider sums rather than products. You may use the fact that if the sum of some integers $n_1, \dots, n_\ell$ is even, and exactly $m$ of those are odd, then $m$ is even.)

\vfill


\end{enumerate}




\end{document}
