\documentclass[UTF8, 11pt]{amsart}
\usepackage{hyperref}
\usepackage{amsthm}

\title{MATH 3040: Homework 5}
\author{}
\date{September 20, 2017}

%----------Theorems----------

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{nondefinition}[theorem]{Non-Definition}
\newtheorem{exercise}[theorem]{Exercise}

\renewcommand{\P}{\mathcal{P}}
\newcommand{\N}{\textbf{N}}
\newcommand{\Z}{\textbf{Z}}

%Redefine the first level
\renewcommand{\theenumi}{(\alph{enumi})}
\renewcommand{\labelenumi}{\theenumi}

\begin{document}

\maketitle

All answers must be in complete sentences. All assertions must be proven, per the student contract. Remember that this is a writing class, so while correctness and thoroughness are most important, \textit{style} matters as well. 


\bigskip
\noindent
\textbf{1. (Practice in Posing Questions)} What is an interesting open-ended question you could ask, which is related to the material that we covered in class? What is a concrete mathematical question that could be used to approach an answer to the question? 


\bigskip
\noindent
\textbf{2. (Wrap-up from class)} 
\begin{enumerate}
  % a
  \item{(Induction, Exer. 7) How many ways are there to cover a $2 \times n$ chessboard with $n$ dominos of size $2 \times 1$, without overlaps?}
  
  % b
  \item{Show that the well-ordering principle implies the principle of mathematical induction.}	

  
  % c
  \item{(Induction, Exer. 10) Show that the principle of mathematical induction implies the well-ordering principle.}
  
\end{enumerate}

\bigskip
\noindent
\textbf{3. (Practice proofs with sets)} Suppose that $A$, $B$, and $C$ are arbitrary sets.
\begin{enumerate}
  % a
  \item{(``Distributivity") Prove that $A \times (B \cap C) = (A \times B) \cap (A \times C)$.}
  
  % b
  \item{Is there an analogous expression for $A \times (B \cup C)$? If so, state it and prove it. If not, explain why such a statement cannot hold.}
  
  % c
  \item{Assume that $C \neq \emptyset$. If $A \times C = B \times C$, then $A = B$.}	
\end{enumerate}


\bigskip
\noindent
\textbf{4. (Sizes of sets)} Suppose that $A$ is a set of three elements, $B$ is a set of five elements, and $C$ is a set of eight elements. What can you say about the number of elements in the following sets? If there are several possibilities, find all of them. (It might be convenient to use the notation $|X|$ for the size of the set $X$.)
\begin{enumerate}
  % a
  \item{$A \cup B$, $A \cap B$ and $A \times B$}	
  
  % b
  \item{$A \cup B \cup C$, $A \cap B \cap C$, $(A \cup B) \cap C$, and $A \cup (B \cap C)$}
  
  % c
  \item{$\P(A \cup B)$, $\P(A \cap B)$, and $\P(A \times B)$ (Recall that $\P(S)$ denotes the powerset of the set $S$, i.e. the set of all its subsets)}
  
  % d
  \item{$\P(A) \cup \P(B)$, $\P(A) \cap \P(B)$, and $\P(A) \times \P(B)$}
\end{enumerate}



\bigskip
\noindent
\textbf{5. (Prove or disprove and salvage)} Let $A$ and $B$ be arbitrary sets.
\begin{enumerate}
  % a
  \item{$\P(A \cup B) = \P(A) \cup \P(B)$}	
  
  % b
  \item{$\P(A \cap B) = \P(A) \cap \P(B)$}
  
  % c
  \item{$|\P(A \times B)| = |\P(A) \times \P(B)|$}
\end{enumerate}
 

\bigskip
\noindent
\textbf{6. (Subtleties of Sets)} Let $S$ be the set of all sets $A$ that satisfy the property ``$A$ does not belong to itself," that is,
\[
S = \{A \mid A \not \in A\}.
\] 
\begin{enumerate}
  % a
  \item{Show that the assumption that $S$ is a member of $S$ leads to a contradiction.}
  
  % b
  \item{Show that the assumption that $S$ is not a member of $S$ also leads to a contradiction.}	
\end{enumerate}

\medskip
\noindent
\textit{Remark.} Here's one way to try and think about the above exercise. Suppose we are in a world of robots. Wally is a robot that cleans all the robots, and only those robots, that don't clean themselves. Does Wally clean himself? The above shows some of the limitations of using words or properties to define sets, and highlights some of the issues that may arise if you start thinking carefully about these kinds of questions.

\bigskip
\bigskip
The following problem should be submitted as a group. Modify the groupwork template tex file accordingly. You can look at the .tex file for this homework assignment if you don't want to retype it in.

\bigskip
\noindent
\textbf{7. (Groupwork) [Patterns in Numbers]}
\begin{enumerate}
  % a
  \item{Prove that the product of any two consecutive integers is even.}
  
  % b
  \item{Prove that the product of any three consecutive integers is divisible by 6.}
  
  % c
  \item{Prove that the product of any four consecutive integers is divisible by 24.}
  
  % d
  \item{Prove that the product of any five consecutive integers is divisible by 120.}
  
  % e
  \item{How can you generalize the above results to a product of $k$ consecutive integers for any $k \in \N$? State your claim and prove it.}	
\end{enumerate}
 
\bigskip
\noindent
\textbf{8. (Lewis Carroll's logical arguments)} The following examples are by Charles Lutwidge Dodgson (better known as Lewis Carroll), an English writer and mathematician, best known as the author of \textit{Alice's Adventures in Wonderland}. Are the arguments justified? In other words, do the hypotheses imply the conclusion?
\begin{enumerate}
  % a
  \item{\begin{itemize}
  \item{Babies are illogical.}
  \item{Nobody is despised who can manage a crocodile.}
  \item{Illogical persons are despised.}	
\end{itemize}
Therefore, babies cannot manage crocodiles.
}	
  % b
  \item{\begin{itemize}
  \item{No ducks waltz.}
  \item{No officers ever decline to waltz.}
  \item{All my poultry are ducks.}	
\end{itemize}
Therefore, my poultry are not officers.
}

  % c
  \item{
  \begin{itemize}
    \item{All, who neither dance on tight ropes nor eat penny buns, are old.}
    \item{Pigs that are liable to giddiness are treated with respect.}
    \item{A wise balloonist takes an umbrella with him.}
    \item{No one ought to lunch in public who looks ridiculous and eats penny buns.}
    \item{Young creatures who go up in balloons are liable to giddiness.}
    \item{Fat creatures who look ridiculous may lunch in public if they do not dance on tight ropes.}
    \item{No wise creatures dance on tight ropes if they are liable to giddiness.}
    \item{A pig looks ridiculous carrying an umbrella.}
    \item{All, who do not dance on tight ropes and who are treated with respect, are fat.}	
  \end{itemize}
  Therefore, a wise young pig will not become a balloonist. (Hint: Argue indirectly. Assume, as Carroll apparently did, that an old creature is not young.)
}
\end{enumerate}

 

\end{document}
