\documentclass[12pt]{amsart} % Document type

% There is a lengthy top section...
% Copy and paste this into a new .tex file.
% Begin typing at the bottom of this document.

%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%
%
% Various add-ons that allow for greater customization of the document. Not all are necessary.

%\usepackage[T1]{fontenc} % Output encoding (suggested when text contains accented letters)
%\usepackage[utf8]{inputenc} % Input encoding (important when writing in foreign languages)
\usepackage[margin =.5in]{geometry} % Set page dimensions
\usepackage{parskip} % Custom paragraph spacing
\usepackage{setspace} % Allow for double-spacing using \doublespace
\usepackage{multicol} % Allows multiple columns on a page
\usepackage{mathtools,amssymb,amsfonts,amsthm} % Variety of useful things for math
\usepackage{euscript,mathrsfs,bbm} % Some additional fonts
\usepackage{color} % Color
\usepackage[usenames,dvipsnames,svgnames,table]{xcolor} % Extra colors

\usepackage{comment} % Customizable comment environments
\usepackage{newverbs} % Customizable verbatim environments
\usepackage{enumitem} % Customizable enumerate environments
\usepackage{tabularx} % Greater flexibility with tables
\usepackage{multirow} % Table elements span multiple rows

\usepackage{graphicx} % For inserting images
\usepackage{wrapfig} % Wrap text around figures
\usepackage{url} % For inserting urls
\usepackage[linktoc=all,colorlinks=true,linkcolor=blue,urlcolor=Purple,citecolor=cyan]{hyperref} % Internal and external links
\usepackage[all]{hypcap} % Image captions (requires hyperref)
\usepackage{pdfpages} % Insert pdfs
\usepackage{tikz} % For drawing pictures
    \usetikzlibrary{patterns}
    \usetikzlibrary{trees}
%\usepackage[all]{xy} % Matrix-like diagrams
\usepackage{wasysym}
\raggedbottom
\allowdisplaybreaks

%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%
%
% Custom comment environments and various editing macros
% Comments can be turned off using \excludecomment{ }

\specialcomment{lecturenotes}{}{}\excludecomment{lecturenotes}
\specialcomment{answers}{ \textsc{Answer: }}{}
\specialcomment{remarks}{

\setlength{\leftskip}{5mm}
\begingroup\color{blue}}
{\endgroup

\setlength{\leftskip}{0mm}
}
\specialcomment{inremarks}{\begingroup\color{blue}}{\endgroup}
\newcommand{\ctypo}[1]{\colorbox{yellow}{#1}\hspace{-1mm}}
\newcommand{\ctex}[1]{\colorbox{Gold}{#1}}
\newcommand{\period}{\colorbox{cyan!50}{.}}
\newcommand{\comma}{\colorbox{cyan!50}{,}}

\newverbcommand{\cverb}{\small\color{purple}}{}
\newverbcommand{\everb}{\small\color{blue}}{}

%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%
%
% Custom column types for tabularx

\newcolumntype{L}[1]{>{\hsize=#1\hsize\raggedright\arraybackslash}X}
\newcolumntype{R}[1]{>{\hsize=#1\hsize\raggedleft\arraybackslash}X}
\newcolumntype{C}[1]{>{\hsize=#1\hsize\centering\arraybackslash}X}

%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%
%
% Custom spacing commands

\begingroup
    \makeatletter
    \@for\theoremstyle:=definition,remark,plain\do{%
        \expandafter\g@addto@macro\csname th@\theoremstyle\endcsname{%
            \addtolength\thm@preskip\parskip
            }%
        }
\endgroup

\newcommand{\sss}{\vspace{2 mm}\noindent}
\newcommand{\lss}{\vspace{5 mm}\noindent}
\newcommand{\lls}{\vspace{7 mm}\noindent}
\newcommand{\ds}{\displaystyle}
\newcommand{\HR}{\vspace{5pt}\hrule height 1pt \vspace{5pt}}
\newcommand{\atext}[1]{\text{\quad #1 \quad }}
%\newcommand\Tstrut{\rule{0pt}{2.6ex}}         % = `top' strut
%\newcommand\Bstrut{\rule[-1ex]{0pt}{0pt}}   % = `bottom' strut

%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%
%
% Shortcuts for commonly used symbols

\newcommand{\ca}{\mathcal}
\newcommand{\fr}{\mathfrak}
\newcommand{\eucal}{\EuScript}
\newcommand{\scr}{\mathscr}
\newcommand{\bbf}{\mathbb{F}}
\newcommand{\bbn}{\mathbb{N}}
\newcommand{\bbr}{\mathbb{R}}
\newcommand{\bbq}{\mathbb{Q}}
\newcommand{\bbc}{\mathbb{C}}
\newcommand{\bbz}{\mathbb{Z}}
\newcommand{\bbp}{\mathbb{P}}
\newcommand{\bfa}{\mathbf{a}}
\newcommand{\bfb}{\mathbf{b}}
\newcommand{\bfc}{\mathbf{c}}
\newcommand{\bfu}{\mathbf{u}}
\newcommand{\bfv}{\mathbf{v}}
\newcommand{\bfx}{\mathbf{x}}
\newcommand{\ring}{\ca O}

\newcommand{\inv}{^{-1}}
\newcommand{\into}{\hookrightarrow}
\newcommand{\onto}{\twoheadrightarrow}
\newcommand{\isom}{\overset{\sim}{\to}}
\renewcommand{\iff}{\Leftrightarrow}
\renewcommand{\implies}{\Rightarrow}
\renewcommand{\impliedby}{\Leftarrow}
\newcommand{\contradiction}{\Rightarrow\Leftarrow}

%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%
%
% Shortcuts for matrices and vectors

\newcommand{\bmat}[1]{\begin{bmatrix}#1\end{bmatrix}}
\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}
\newcommand{\vmat}[1]{\begin{vmatrix}#1\end{vmatrix}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\Floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\vect}[1]{\langle #1 \rangle}

%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%
%
% Custom function names

\newcommand{\Ad}{\operatorname{Ad}}
\newcommand{\ad}{\operatorname{ad}}
\newcommand{\disc}{\operatorname{disc}}
\newcommand{\domain}{\operatorname{domain}}
\newcommand{\Id}{\operatorname{Id}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\ind}{\operatorname{ind}}
\newcommand{\nul}{\operatorname{Nul}}
\newcommand{\nullity}{\operatorname{nullity}}
\newcommand{\ord}{\operatorname{ord}}
\newcommand{\proj}{\operatorname{proj}}
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\red}{\operatorname{Red}}
\newcommand{\bbref}{\operatorname{rref}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\trunc}{\operatorname{Trunc}}
\newcommand{\vspan}{\operatorname{span}}

%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%
%
% Environment styles

\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem*{prop*}{Proposition}
\newtheorem*{cor*}{Corollary}
\newtheorem*{lem*}{Lemma}
\newtheorem*{thm*}{Theorem}

\theoremstyle{definition}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{defn}[thm]{Definition}
\newtheorem*{defn*}{Definition}
\newtheorem{claim}[thm]{Claim}
\newtheorem{example}[thm]{Example}
\newtheorem*{conj*}{Conjecture}
\newtheorem*{rd}{Read from the text}
\newenvironment{answer}{\noindent\textsc{Answer:}}{\hfill $\square$}

\newcounter{homework}
\newtheorem{hw}[homework]{Homework}
\newtheorem*{hw*}{Homework}
\newcounter{exercise}[homework]
\newtheorem{exer}[exercise]{Exercise}
\renewcommand{\theexercise}{\arabic{exercise}}

\theoremstyle{remark}
\newtheorem{remark}[thm]{Remark}
\newtheorem*{remark*}{Remark}
\newtheorem{notation}[thm]{Notation}
\newtheorem*{notation*}{Notation}

\newcommand{\truefalse}{\qquad\textbf{T}\qquad \textbf{F}\quad :\quad}
\renewcommand{\thethm}{\textbf{\arabic{thm}}}

\title{Math 2001 \\ Conditionals, Quantifiers, and negation}

\begin{document}
\maketitle

As stated previously, if-then statements are very common. Due to the nuance and variation of the English language, there are many ways to restate an if-then statement. Depending on the context, some phrasings may be more appropriate than others. We have already seen one example: the statement ``if $P$, then $Q$" is equivalent to the statement ``$P \implies Q$". Here are a few more equivalent forms.

\begin{exer}
Consider the following ``if $P$, then $Q$" statement.
\begin{quote}
If $\underbrace{x = 1}_P$, then $\underbrace{x^2 = 1}_Q$.
\end{quote}
Complete each of the following statements so that they are equivalent to the if-then statement above. 

\begin{enumerate}[label={\alph*.}]
\item \underline{\hspace{2.25in}} if \underline{\hspace{2.25in}}.
\item \underline{\hspace{2.25in}} only if \underline{\hspace{2.25in}}.
\item \underline{\hspace{2.25in}} implies \underline{\hspace{2.25in}}.
\item \underline{\hspace{2.25in}} is implied by \underline{\hspace{2.25in}}.
\item \underline{\hspace{2.25in}} whenever \underline{\hspace{2.25in}}.
\item \underline{\hspace{2.25in}} is necessary when \underline{\hspace{2.25in}}.
\item \underline{\hspace{2.25in}} is sufficient for \underline{\hspace{2.25in}}.
\end{enumerate}
\end{exer}

As long as we can identify the $P$ and $Q$ parts in statements like the ones above, we can follow the rules to form the negations, contrapositives, and converses of the statements as necessary.

\begin{exer}
For the statement ``$P \implies Q$", the contrapositive, negation, and converse are
\begin{itemize}
\item Contrapositive:
\item Negation:
\item Converse: 
\end{itemize}
\end{exer}

\subsection*{For each/all/every: ``For all $P$, we have $Q$" or ``$Q$ for all $P$"} 
Another common phrase is the ``for all" statement. For example: ``$x^2 < 0$ for all $x \in \bbr$." (Equivalently, ``for all $x \in \bbr$, we have $x^2 < 0$.") 

\subsection*{There exists: ``There exists $P$ such that $Q$"} The ``for all'' statement implies that the statement is always true. On the other end of the spectrum, the ``there exists" statement implies that the statement is true in at least one case (but may be false otherwise). For example: ``there exists $c \in \bbz$ such that $3c = 7$."

Of course, both my examples are false statements. So by negating these statements, we will have true statements. How do we negate ``for all" and ``there exists"? 

\begin{itemize}
\item $\neg$(``for all $P$, we have $Q$") = ``there exists $P$ such that $\neg Q$"
\item $\neg$(``there exists $P$ such that $Q$") = ``for all $P$, we have $\neg Q$"
\end{itemize}

E.g. $\neg$(``for all $x \in \bbr$, we have $x^2 < 0$") = ``there exists $x \in \bbr$ such that $x^2 \ge 0$."

\qquad $\neg$(``there exists $c \in \bbz$ such that $3c=7$") = ``for all $c \in \bbz$, we have $3c \neq 7$."

\pagebreak

\begin{multicols}{2}
\begin{enumerate}[label={\bf \Roman*.}]
\item\

\begin{tikzpicture}[scale=1.2]
\foreach \x/\y in {1/dots,2/dots,3/bricks,4/fivepointed stars} {
	\draw (1.3*\x,1.2) node[draw,pattern=\y,inner sep = 6mm] {};
	\draw (1.3*\x,1.2) node[circle,fill=white,inner sep=.5mm,draw] {$s_\x$};
}
\foreach \x/\y in {1/dots,2/dots,3/bricks,4/fivepointed stars,5/fivepointed stars} {
	\draw (1.3*\x,0) node[draw,pattern=\y,inner sep = 5mm,circle] {};
	\draw (1.3*\x,0) node[circle,fill=white,inner sep=.5mm,draw] {$c_\x$};
}
\end{tikzpicture}

\item 

\

\begin{tikzpicture}[scale=1.2]
\foreach \x/\y in {1/dots,2/dots,3/fivepointed stars,4/bricks,5/north west lines} {
	\draw (1.3*\x,1.2) node[draw,pattern=\y,inner sep = 6mm] {};
	\draw (1.3*\x,1.2) node[circle,fill=white,inner sep=.5mm,draw] {$s_\x$};
}
\foreach \x/\y in {1/bricks,2/fivepointed stars,3/north west lines,4/bricks,5/dots} {
	\draw (1.3*\x,0) node[draw,pattern=\y,inner sep = 5mm,circle] {};
	\draw (1.3*\x,0) node[circle,fill=white,inner sep=.5mm,draw] {$c_\x$};
}
\end{tikzpicture}

\item
\

\begin{tikzpicture}[scale=1.2]
\foreach \x/\y in {1/north west lines,2/north west lines,3/north west lines,4/north west lines} {
	\draw (1.3*\x,1.2) node[draw,pattern=\y,inner sep = 6mm] {};
	\draw (1.3*\x,1.2) node[circle,fill=white,inner sep=.5mm,draw] {$s_\x$};
}
\foreach \x/\y in {1/north west lines,2/north west lines,3/north west lines} {
	\draw (1.3*\x,0) node[draw,pattern=\y,inner sep = 5mm,circle] {};
	\draw (1.3*\x,0) node[circle,fill=white,inner sep=.5mm,draw] {$c_\x$};
}
\end{tikzpicture}

\item
\

\begin{tikzpicture}[scale=1.2]
\foreach \x/\y in {1/north west lines,2/fivepointed stars,3/north west lines,4/dots,5/fivepointed stars} {
	\draw (1.3*\x,1.2) node[draw,pattern=\y,inner sep = 6mm] {};
	\draw (1.3*\x,1.2) node[circle,fill=white,inner sep=.5mm,draw] {$s_\x$};
}
\foreach \x/\y in {1/bricks,2/fivepointed stars,3/fivepointed stars,4/bricks,5/dots} {
	\draw (1.3*\x,0) node[draw,pattern=\y,inner sep = 5mm,circle] {};
	\draw (1.3*\x,0) node[circle,fill=white,inner sep=.5mm,draw] {$c_\x$};
}
\end{tikzpicture}
\end{enumerate}
\end{multicols}

Let $P(s_i)$ and $P(c_i)$ denote the pattern on the $i$-th square or circle, respectively. 
\begin{itemize}
\item For each of the following statements, write its contrapositive, negation, and converse where requested. 

\item In the neighboring boxes, identify the diagrams ({\bf I, II, III, IV}) that satisfy each statement.
\end{itemize}

\begin{enumerate}[label={\arabic*.}]
%\setlength{\itemsep}{5mm}
\item 
\begin{tikzpicture}
\draw (0,0) rectangle (3,1.5);
\node at (1.5,1.2) {Satisfied by};
\end{tikzpicture}
If $i=j$, then $P(s_i) = P(c_j)$.

\item[] 
\begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Contrapositive:}

\item[] \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Negation:}

\item[] \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Converse:}

\item \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
The pattern $P(c_i)$ is ``lines'' whenever $P(s_i)$ is ``lines''.

\item[] \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Contrapositive:}

\item[] \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Negation:}

\item[] \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Converse:}

\item \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
For each $i$, there exists a $j$ for which $P(c_i) = P(s_j)$.

\item[] \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Negation:}

\item \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
For each $i$, there exists a $j$ for which $P(s_i) = P(c_j)$.

\item[] \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Negation:}

\item \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
There exists an $i$ such that $P(s_j) = P(c_i)$ for all $j$.

\item[] \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Negation:}

\item \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
For all $i$ and all $j$, we have $P(c_i) = P(s_j)$.

\item[] \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Negation:}

\item \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
There exists an $i$ and there exists a $j$ such that $P(c_i) = P(s_j)$.

\item[] \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Negation:}

\item \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
If there exists an $i$ for which $P(c_i) = P(s_i)$, then there exists a $j \neq i$ such that $P(c_i) = P(c_j)$.

\item[] \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Contrapositive:}

\item[] \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Negation:}

\item[] \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Converse:}

\item \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
There exists an $i$ for which $P(c_i)$ is ``dots'' only if there exists a $j$ for which $P(s_j)$ is ``dots''.

\item[] \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Contrapositive:}

\item[] \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Negation:}

\item[] \begin{tikzpicture}
\draw (0,0) rectangle (3,1);
\end{tikzpicture}
{Converse:}
\end{enumerate}

{Upcoming deadlines:}
\begin{itemize}
\setlength{\itemsep}{-2mm}
\item Due Friday, Mar 4: final draft of proof 4, first draft of proof 7.
\item Due Monday Mar 7: final draft of proof 5, final draft of proof 6.
\item Due Wednesday Mar 9: final draft of proof 7, first draft of proof 8.
\end{itemize}


\begin{exer}
Complete each of the following statements using the following clauses.
\begin{quote}
$P$: It rains heavily. \qquad $Q$: The streams flood their banks.
\end{quote}
(You may need to alter how the clauses are phrased.)

\begin{enumerate}[label={\alph*.}]
\item If \underline{\hspace{3in}}, then \underline{\hspace{3in}}.
\item \underline{\hspace{3in}} if \underline{\hspace{3in}}.
\item \underline{\hspace{3in}} only if \underline{\hspace{3in}}.
\item \underline{\hspace{3in}} implies \underline{\hspace{3in}}.
\item \underline{\hspace{3in}} implied by \underline{\hspace{3in}}.
\item \underline{\hspace{3in}} whenever \underline{\hspace{3in}}.
\item \underline{\hspace{3in}} necessary \underline{\hspace{3in}}.
\item \underline{\hspace{3in}} sufficient \underline{\hspace{3in}}.
\end{enumerate}
\end{exer}
\end{document}