\documentclass[12pt,reqno]{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 =.75in]{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{ifthen} % if-then statements

\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{petri}
    \usetikzlibrary{trees}
    \usetikzlibrary{arrows}
    \usetikzlibrary{decorations.markings}
%\usepackage[all]{xy} % Matrix-like diagrams
\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{solutions}{

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

\newboolean{print_solutions}
\setboolean{print_solutions}{true}
\ifthenelse{\boolean{print_solutions}}{}{\excludecomment{solutions}}

%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%
%
% 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}

\title{Math 2001 \\ Quiz 5 instructions}
\date{\today}

\begin{document}
\maketitle

Work in groups of up to three people to give a complete proof for the following theorem.

\begin{thm*}
Let $B$, $C$, and $D$ be sets. If $C \neq \varnothing$ and $B \times C \subseteq C \times D$, then $B \subseteq D$.
\end{thm*}

Points are awarded as follows:
\begin{itemize}
\item (1 pt) Name(s) in the top right corner.
\item (1 pt) Writing is neat and legible.
\item (1 pt) Each relevant and correctly stated definition.
\item (7 pts) Complete sketch of the proof (optional, but recommended).
\item (Remaining points, up to 14) Complete proof: introductory statements, all statements are complete sentences, every statement is justified appropriately, etc.
\end{itemize}
This quiz is out of 16 points. So, for example, if you state two relevant definitions and sketch a complete outline, then I will grade your written proof out of 4. If you just give me a proof (no definitions, no outline), then I will grade the proof out of 14.

You may use the space below for scratch work.

Write your final proof on the other worksheet.

\vfill
\pagebreak

\pagestyle{plain}

\begin{center}
\textbf{MATH 2001 \\ QUIZ 5}
\end{center}

\begin{enumerate}[label={\arabic*.}]
\item Write your name(s) in the top right corner.

\item Write is neatly and legibly.

\item Prove the following theorem.

\begin{thm*}
Let $B$, $C$, and $D$ be sets. If $C \neq \varnothing$ and $B \times C \subseteq C \times D$, then $B \subseteq D$.
\end{thm*}

\begin{solutions}
There are several approaches to proving this statement, so I will give two arguments. 

\begin{proof}
Let $B$, $C$, and $D$ be sets, and suppose that $B \times C \subseteq C \times D$ and $C \neq \varnothing$. We prove that $B \subseteq D$ by showing that if $x \in B$, then $x \in D$.

Suppose $x \in B$, and since $C \neq \varnothing$, let $y \in C$. Then by the definition of Cartesian product, $(x,y) \in B \times C$. Therefore, $(x,y) \in C \times D$ by the definition of subset and since $B \times C \subseteq C \times D$. Thus by the definition of Cartesian product, we conclude that $x \in C$ and $y \in D$. 

In particular, we now have $x \in B$ and $x \in C$, and so $(x,x) \in B \times C$. So by a similar argument, $(x,x) \in C \times D$, and therefore $x \in D$. Thus we have shown that if $x \in B$, then $x \in D$, whence $B \subseteq D$ by the definition of subset.
\end{proof}

I'll now give a second argument, which judging by class today, will likely be a closer match to the proof your group wrote.

\begin{proof}
Let $B$, $C$, and $D$ be sets, and suppose that $B \times C \subseteq C \times D$ and $C \neq \varnothing$. We prove that $B\subseteq D$ in two steps: we prove that $B \subseteq C$ and $C \subseteq D$, and from this we conclude that $x \in B \implies x \in C$.

We will prove that $B \subseteq C$ and $C \subseteq D$ simultaneously by showing that $x \in B\implies x \in C$ and $y \in C \implies y \in D$. 

Suppose that $x \in B$ and $y \in C$. Then $(x,y) \in B \times C$ by the definition of Cartesian product. Since $B \times C \subseteq C \times D$, we have $(x,y) \in C \times D$ by the definition of subset. Therefore $x \in C$ and $y \in D$ by the definition of Cartesian product. Thus we have shows that $x\in B \implies x \in C$ and $x \in C \implies x \in D$. So by the definition of subset, $B \subseteq C$ and $C \subseteq D$.

To finish off the proof that $B \subseteq D$, suppose that $x \in B$. Then $x \in C$ since $B \subseteq C$, and so $x \in D$ since $C \subseteq D$. Thus $B \subseteq D$ by the definition of subset.
\end{proof}

\begin{remark*}
Why is it important that $C \neq \varnothing$? Well, because the theorem is false if $C = \varnothing$, and that is a quiz question. But what about the other sets, $B$ and $D$?

If $B = \varnothing$, then the conclusion of this theorem is automatically satisfied: if $B = \varnothing$, then $B \subseteq D$ since $\varnothing$ is a subset of every set.

What if $D = \varnothing$? The theorem holds, but this is a great question which will take a bit of work to resolve. The argument requires a proof by contradiction (which we will see later this semester), so I won't give it here, but the basic gist is as follows. If $D = \varnothing$, then $B = \varnothing$, and so we are back in the previous case.

Since these cases weren't addressed in the proofs above, are the proofs complete? No. These cases where $B = \varnothing$ and $D = \varnothing$ should be addressed in the proofs as well. In hindsight, I should have stipulated that all of the sets are non-empty to avoid these extraneous cases.

Edit: Actually, $D = \varnothing$ is not a concern. If $C \neq \varnothing$, then $D \neq \varnothing$. 
\end{remark*}
\end{solutions}
\end{enumerate}



\end{document}