%
% LaTeX Problem Set Template by Sachin Padmanabhan
% I created this when I was a freshman in CS 103,
% and I continue to use it to this day.
%
% Hope you enjoy!
%
% There may be problems with this template.
% If so, feel free to contact me.
%

% Updated for Fall 2018 by Michael Zhu
% Updated for Fall 2019 by Joshua Spayd

\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage[margin=1in]{geometry}
\usepackage{multicol}
\usepackage{bm}
\usepackage{listings}
\PassOptionsToPackage{usenames,dvipsnames}{color}  %% Allow color names
\usepackage{pdfpages}
\usepackage{algpseudocode}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage[T1]{fontenc}
\usepackage{inconsolata}
\usepackage{framed}
\usepackage{wasysym}
\usepackage[thinlines]{easytable}
\usepackage{hyperref}
\usepackage{wrapfig}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,
    urlcolor=blue,
}

\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#1}
\author{[TODO: Replace this with your name(s)]}
\date{\today}

% Running author based on https://tex.stackexchange.com/questions/68308/how-to-add-running-title-and-author#answer-68310
\makeatletter
\let\runauthor\@author
\makeatother

\lhead{\runauthor}
\chead{Problem Set 1}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Autumn 2019}
\rfoot{\thepage}

\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\absfit}[1]{\left\lvert #1 \right\rvert}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\eval}[3]{\left[#1\right]_{#2}^{#3}}
\renewcommand{\(}{\left(}
\renewcommand{\)}{\right)}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\pd}[1]{\frac{\partial}{\partial #1}}
\newcommand{\inner}[1]{\langle#1\rangle}
\newcommand{\cond}{\bigg|}
\newcommand{\rank}[1]{\mathbf{rank}(#1)}
\newcommand{\range}[1]{\mathbf{range}(#1)}
\newcommand{\nullsp}[1]{\mathbf{null}(#1)}
\newcommand{\repr}[1]{\left\langle#1\right\rangle}

\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Tr}{\mathbf{Tr}}
\DeclareMathOperator{\diag}{\mathbf{diag}}
\DeclareMathOperator{\dist}{\mathbf{dist}}
\DeclareMathOperator{\prob}{\mathbf{prob}}
\DeclareMathOperator{\dom}{\mathbf{dom}}
\DeclareMathOperator{\E}{\mathbf{E}}
\DeclareMathOperator{\R}{\mathbb{R}}
\DeclareMathOperator{\var}{\mathbf{var}}
\DeclareMathOperator{\quartile}{\mathbf{quartile}}
\DeclareMathOperator{\conv}{\mathbf{conv}}
\DeclareMathOperator{\VC}{VC}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator{\Ber}{Bernoulli}
\DeclareMathOperator{\NP}{\mathbf{NP}}
\DeclareMathOperator{\coNP}{\mathbf{coNP}}
\DeclareMathOperator{\TIME}{\mathsf{TIME}}
\DeclareMathOperator{\polytime}{\mathbf{P}}
\DeclareMathOperator{\PH}{\mathbf{PH}}
\DeclareMathOperator{\SIZE}{\mathbf{SIZE}}
\DeclareMathOperator{\ATIME}{\mathbf{ATIME}}
\DeclareMathOperator{\SPACE}{\mathbf{SPACE}}
\DeclareMathOperator{\ASPACE}{\mathbf{ASPACE}}
\DeclareMathOperator{\NSPACE}{\mathbf{NSPACE}}
\DeclareMathOperator{\Z}{\mathbb{Z}}
\DeclareMathOperator{\N}{\mathbb{N}}
\DeclareMathOperator{\EXP}{\mathbf{EXP}}
\DeclareMathOperator{\NEXP}{\mathbf{NEXP}}
\DeclareMathOperator{\NTIME}{\mathbf{NTIME}}
\DeclareMathOperator{\DTIME}{\mathbf{DTIME}}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\BPP}{\mathbf{BPP}}
\DeclareMathOperator{\ZPP}{\mathbf{ZPP}}
\DeclareMathOperator{\RP}{\mathbf{RP}}
\DeclareMathOperator{\coRP}{\mathbf{coRP}}
\DeclareMathOperator{\BPL}{\mathbf{BPL}}
\DeclareMathOperator{\IP}{\mathbf{IP}}
\DeclareMathOperator{\PSPACE}{\mathbf{PSPACE}}
\DeclareMathOperator{\NPSPACE}{\mathbf{NPSPACE}}
\DeclareMathOperator{\SAT}{\mathsf{SAT}}
\DeclareMathOperator{\NL}{\mathbf{NL}}
\DeclareMathOperator{\PCP}{\mathbf{PCP}}
\DeclareMathOperator{\PP}{\mathbf{PP}}
\DeclareMathOperator{\cost}{cost}
\let\Pr\relax
\DeclareMathOperator*{\Pr}{\mathbf{Pr}}

% start MZ
\let\oldemptyset\emptyset
\renewcommand{\emptyset}{\text{\O}}
\renewcommand{\labelitemii}{$\bullet$}
\renewcommand\qedsymbol{$\blacksquare$}
\newenvironment{prf}{{\bfseries Proof.}}{\qedsymbol}
\renewcommand{\emph}[1]{\textit{\textbf{#1}}}
\newcommand{\annotate}[1]{\textit{\textcolor{blue}{#1}}}
\usepackage{mdframed}
\usepackage{float}

\makeatother
% end MZ

\definecolor{shadecolor}{gray}{0.95}

\theoremstyle{plain}
\newtheorem*{lem}{Lemma}

\theoremstyle{plain}
\newtheorem*{claim}{Claim}

\theoremstyle{definition}
\newtheorem*{answer}{Answer}

\newtheorem{theorem}{Theorem}[section]
\newtheorem*{thm}{Theorem}
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\setlength{\parindent}{0pt}

\pagestyle{fancy}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

\begin{document}

\maketitle

\section*{Checkpoint Problem One: Finding Negations}

In order to write a proof by contradiction or contrapositive, you'll need to determine the negation of one or more
statements. In Friday's lecture, we talked about a few common classes of statements and how to form their negations.
Using what you've learned, answer the following multiple-choice questions and \emph{briefly explain how you arrived at
your answer}. \\

Which of the following is the negation of ``everything that has a beginning has an end?''

\begin{enumerate}[label=\Alph*)]
  \item Everything that does not have a beginning has an end.
  \item Everything that has a beginning has no end.
  \item There is something that has no beginning and has an end.
  \item There is something that has a beginning and has no end.
\end{enumerate}

\begin{shaded}
  Write your answer here.
\end{shaded}

Which of the following is the negation of ``there is a successful person who is grateful?''

\begin{enumerate}[label=\Alph*)]
  \item There is an unsuccessful person who is grateful.
  \item There is a successful person who is ungrateful.
  \item Every successful person is grateful.
  \item Every successful person is ungrateful.
  \item Every unsuccessful person is grateful.
  \item Every unsuccessful person is ungrateful.
\end{enumerate}

\begin{shaded}
  Write your answer here.
\end{shaded}

Which of the following is the negation of ``if $A \subseteq B$, then $A - B = \emptyset$?''

\begin{enumerate}[label=\Alph*)]
  \item If $A \subseteq B$, then $A - B = \emptyset$.
  \item If $A \subseteq B$, then $A - B \neq \emptyset$.
  \item If $A \not\subseteq B$, then $A - B = \emptyset$.
  \item If $A \not\subseteq B$, then $A - B \neq \emptyset$.
  \item There are sets $A$ and $B$ where $A \subseteq B$ and $A - B = \emptyset$.
  \item There are sets $A$ and $B$ where $A \subseteq B$ and $A - B \neq \emptyset$.
  \item There are sets $A$ and $B$ where $A \not\subseteq B$ and $A - B = \emptyset$.
  \item There are sets $A$ and $B$ where $A \not\subseteq B$ and $A - B \neq \emptyset$.
\end{enumerate}

\begin{shaded}
  Write your answer here.
\end{shaded}

\annotate{Remember that you need to provide a justification for your answers. While it's not required, ideally you
  should be able to explain both why your answer is correct \emph{and} why all the other answers are incorrect.}

\section*{Checkpoint Problem Two: Set Theory Warmup}

This question is designed to help you get used to the notation and mathematical
conventions surrounding sets.
Consider the following sets:
\begin{align*}
  A & = \{0, 1, 2, 3, 4\}          \\
  B & = \{2, 2, 2, 1, 4, 0, 3\}    \\
  C & = \{1, \{2\}, \{\{3, 4\}\}\} \\
  D & = \{1, 3\}                   \\
  E & = \N                         \\
  F & = \{\N\}
\end{align*}
Answer each of the following questions and briefly justify your answers.
No proofs are necessary.

\begin{enumerate}[label*=\roman*.,ref=\roman*]

  \item Which pairs of the above sets, if any, are equal to one another?

        \begin{shaded}
          Write your answer here.
        \end{shaded}

  \item Is $D \in A$? Is $D \subseteq A$?

        \begin{shaded}
          Write your answer here.
        \end{shaded}

  \item What is $A \cap C$? How about $A \cup C$? How about $A \Delta C$?

        \begin{shaded}
          Write your answer here.
        \end{shaded}

  \item What is $A - C$? How about $\{A - C\}$? Are those sets equal?

        \begin{shaded}
          Write your answer here.
        \end{shaded}

  \item What is $|B|$? What is $|E|$? What is $|F|$?

        \begin{shaded}
          Write your answer here.
        \end{shaded}

  \item What is $E - A$? Express your answer in set-builder notation.

        \begin{shaded}
          Write your answer here.
        \end{shaded}

  \item Is $0 \in E$? Is $0 \in F$?

        \begin{shaded}
          Write your answer here.
        \end{shaded}

\end{enumerate}

\section*{Checkpoint Problem Three: Modular Arithmetic}

Different numbers can yield the same remainder when divided by some number. For example, the numbers 1, 12, 23, and 34
all leave a remainder of one when divided by eleven. To formalize this relationship between numbers, we'll introduce a
relation $\equiv_k$ that, intuitively, indicates that two numbers leave the same remainder when divided by $k$. For
example, we'd say that $1 \equiv_{11} 12$, since both 1 and 12 leave a remainder of 1 when divided by 11, and that $8
\equiv_3 14$, since both 8 and 14 leave a remainder of 2 when divided by 3.

To be more rigorous, we'll formally define $\equiv_k$. For any integer $k$, define $a \equiv_k b$ as follows:
\begin{center}
  We say that $a \equiv_k b$ if there exists an integer $q$ such that $a = b + kq$
\end{center}

We'd read the statement ``$x \equiv_k y$'' aloud as ``\textit{$x$ is congruent to $y$ modulo $k$}.'' For example, $7
  \equiv_3 4$, because $7 = 4 + 3 \cdot 1$, and $5 \equiv_4 13$ because $5 = 13 + 4 \cdot (-2)$.

In this problem, you will prove several properties of modular congruence.

\begin{enumerate}[label*=\roman*.,ref=\roman*]
  \item Prove that for any integer $x$ and any integer $k$ that $x \equiv_k x$.
\end{enumerate}
\annotate{Be careful not to assume what you need to prove. Don't start your proof by assuming there's a choice of $q$
  where $x = x + kq$ and then solving for $q$. If you assume there's an integer $q$ where $x = x + kq$, you're already
  assuming that $x \equiv_k x$! Look at the proofs we did in lecture with odd and even numbers as an example of how to
  prove that there is a number with a specific property without making any unfounded assumptions.}
\begin{shaded}
  Write your answer here.
\end{shaded}

\begin{enumerate}[resume*]
  \item Prove that for any integers $x$ and $y$ and any integer $k$ that if $x \equiv_k y$, then $y \equiv_k x$.
\end{enumerate}
\annotate{Keep an eye out for your variable scoping in the above proof. Make sure you introduce the variables $x$, $y$,
  and $k$ before you use them. Are they chosen arbitrarily? Do they represent specific values?}
\begin{shaded}
  Write your answer here.
\end{shaded}

\begin{enumerate}[resume*]
  \item Prove that for any integers $x$, $y$, and $z$ and any integer $k$ that if $x \equiv_k y$ and $y \equiv_k z$,
        then $x \equiv_k z$.
\end{enumerate}
\begin{shaded}
  Write your answer here.
\end{shaded}

Modular congruence arises in some pretty unexpected places. Stay tuned -- you'll see this
idea explored in more detail later in the quarter.

\pagebreak

\begin{center}
  \emph{The rest of these problems are due on Friday at 2:30PM. \\ Please type your solutions and submit them on
    GradeScope.}
\end{center}

\section{Much Ado About Nothing}

\begin{shaded}
  Submit your edited $\mathsf{MuchAdoAboutNothing.sets}$ file through GradeScope under ``Programming Assignment 1''.
\end{shaded}

\section{Set Theory in C++}

\begin{shaded}
  Submit your edited $\mathsf{SetTheory.cpp}$ file through GradeScope under ``Programming Assignment 1''.
\end{shaded}

\section{Describing the World in Set Theory}

The notation of set theory (e.g. $\cup, \cap, \wp, \subseteq, \in$, etc.) is a great tool for describing the real world.
Answer each of the following questions by writing an expression using set theory notation, but \emph{without} using
plain English, \emph{without} using set-builder notation, \emph{without} introducing any new variables, and
\emph{without} using propositional or first-order logic (which we'll cover next week). No justification is required.

\begin{enumerate}[label*=\roman*.,ref=\roman*]
  \item In the Talking Heads song \textit{Crosseyed and Painless}, David Byrne speaks the following lines:
        \begin{center}
          ``Facts are simple and facts are straight. \\
          Facts are lazy and facts are late.''
        \end{center}
        Let $F$ be the set of all facts. Let $A, B, C,\text{ and }D$ represent the set of all things that are simple,
        straight, lazy, and late, respectively. Write an expression that conveys David Byrne's lyrics in the language of
        set theory.
\end{enumerate}
\annotate{Once you've written up your answer to this problem, take a minute to \emph{type-check} it. As an example, 
  suppose that you have the following answer:
  \begin{equation*}
    (A \in B) \cap (A \in C)
  \end{equation*}
  This expression can't possibly be correct, and here's one way to see this. The expression $A \in B$ is of type Boolean
  -- either $A \in B$ is true or it isn't -- and the same is true of $A \in C$. However, the intersection operator
  $\cap$ can only be applied to sets. The expression therefore contains a type error: it tries to apply an operator that
  only works on sets to boolean values.}
\annotate{You can type-check this answer in a different way. For example, suppose you came up with this expression:
  \begin{equation*}
    A \cup F
  \end{equation*}
  Here, $A$ and $F$ are sets, so it's perfectly fine to write $A \cup F$, which evaluates to an object of type set. But
  notice that the statement here asks you to write an expression that says ``facts are simple and facts are straight /
  facts are lazy and facts are late,'' and that statement is of type Boolean (facts either have these properties or they
  don't). Therefore, $A \cup F$ can't possibly be an expression with the right meaning, since the type of the expression
  (set) doesn't match the type of the statement (Boolean).}
\annotate{If you're having trouble with this problem, consider working backwards. You know that you need an expression
  that evaluates to type Boolean. What operations on sets do you have that produce Booleans?}
\begin{shaded}
  Write your answer here.
\end{shaded}

\begin{enumerate}[resume*]
  \item Suppose you're on an exciting first date. Let $Y$ represent your hobbies and $D$ represent your
        date's hobbies. Write an expression that says that you have a hobby that your date doesn't have.
        \begin{shaded}
          Write your answer here.
        \end{shaded}

  \item The song ``I am Moana'' from the movie \textit{Moana} starts off with the following lyrics:
        \begin{center}
          ``I know a girl from an island / She stands apart from the crowd.''
        \end{center}
        Let $K$ be the set of all people I know, $G$ be the set of all girls, $L$ be the set of all people from an
        island, and $C$ be the set of all people who stand apart from the crowd. Write an expression that expresses the
        above lyric using the notation of set theory.
\end{enumerate}
\annotate{Notice that you don't have a name for the person described in this statement.}
\begin{shaded}
  Write your answer here.
\end{shaded}

\begin{enumerate}[resume*]
  \item Let's say that a \emph{committee} is a group of people, which we can think of as being represented by the set of
        people that comprise it. Let's have $S$ represent the set of all students at Stanford and let $F$ represent the
        set of all faculty at Stanford. Write an expression representing the set of all committees you can make from
        Stanford students and faculty that contain at least one student and at least one faculty member. You can assume
        no one is both a student and a faculty member.
\end{enumerate}
\annotate{Something to think about: how would you say ``all committees made purely of students?'' Something else
  to think about: what is the type of the statement to translate? Is it a Boolean? A set? Neither?}
\begin{shaded}
  Write your answer here.
\end{shaded}


\section{Proof Critiques, Part One}

One of the best ways to improve your proof \textit{writing} is to do some proof \textit{reading}. In doing so, you'll
get a much better perspective on why certain stylistic conventions matter, both in the positive sense, (``wow, that's so
easy to read!'') and in the negative sense (``I can't make heads or tails of this!''). You'll also get practice tracing
through mathematical arguments, which will help expand your repertoire of techniques and give you a better sense of what
details to focus on in your own reasoning.

We've curated three proofs for you to review. Read these proofs, and for each one, do the following:
\begin{itemize}
  \item \emph{Critique its style.} Our Proofwriting Checklist contains specific details to review in any proof. Go
        through the checklist one item at a time, identifying any style errors and explaining each.  \item
        \emph{Critique its reasoning.} Are the arguments given by these proofs correct? If there are logic errors, point
        them out and demonstrate why they're incorrect. Then, determine whether the theorem being proved is even true in
        the first place.  After all, you can prove anything using faulty logic!
  \item \emph{If possible, rewrite the proof.} You now have a list of issues. Based on what you've found, do one of
        the following:
        \begin{itemize}
          \item If the reasoning is correct but the proof has poor style, simply rewrite the proof to improve its style,
                keeping the core argument intact.
          \item If the reasoning is \textit{incorrect} but the statement being proved is still true, write a new proof
                of the overall theorem. Try to modify the original argument as little as possible.
          \item If the reasoning is \textit{incorrect} and the statement being proved isn't even true to begin with,
                briefly explain why the statement isn't true, though no formal disproof is required.
        \end{itemize}
\end{itemize}

You should submit both your notes from the initial critique and your newly-revised proofs.

\begin{enumerate}[label*=\roman*.,ref=\roman*]

  \item Critique this proof about parities (the \emph{parity} of a number is whether it's even or odd.)
        \begin{thm}
          The sum of an even integer and an odd integer is odd.
        \end{thm}
        \begin{prf}
          This proof will talk about adding together different kinds of numbers. An even integer is an integer that can
          be written as $2k$ for some integer $k$. Therefore, $m = 2k$. Similarly, an odd integer is one that can be
          written as $2k+1$ for some integer $k$. So $n = 2k+1$. $m + n = 2k + 2k + 1 = 4k + 1$. Therefore $m + n$ is
          odd.
        \end{prf}

        \begin{shaded}
          Write your critique and newly-revised proof here.
        \end{shaded}

  \item Critique this proof about natural numbers.
        \begin{thm}
          Every natural number is odd.
        \end{thm}
        \begin{prf}
          Assume for the sake of contradiction that every natural number is even. In particular, that would mean that
          137 is even. Since $137 = 2 \cdot 68 + 1$ and 68 is a natural number, we see that 137 is odd. We know that
          there is no integer $n$ where $n$ is both odd and even. However, $n = 137$ is both even and odd. This is
          impossible.  We've reached a contradiction, so our assumption must have been wrong. Therefore, every natural
          number is odd.
        \end{prf}

        \begin{shaded}
          Write your critique and newly-revised proof here.
        \end{shaded}

  \item Critique this proof about modular arithmetic.
        \begin{thm}
          If $n$ is an integer and $n \equiv_2 0$, then $n \equiv_4 0$.
        \end{thm}
        \begin{prf}
          We will prove the contrapositive of this statement and show that if $n$ is an integer where $n \equiv_4 0$,
          then $n \equiv_2 0$. Since $n \equiv_4 0$, we know $n = 0 + 4q$. This in turn tells us that $n = 2(2q)$, so
          there is an integer $m$ such that $n = 2m$. Consequently, we see that $n = 0 + 2m$, and so $n \equiv_2 0$, as
          required.
        \end{prf}

        \begin{shaded}
          Write your critique and newly-revised proof here.
        \end{shaded}

\end{enumerate}

\section{Modular Arithmetic, Part Two}

The modular congruence relation you saw in the checkpoint problem has a lot of nice properties. As you saw, in many
ways, it acts like regular old equality. How far does that connection extend?

Consider the following statement:
\begin{center}
  For any integers $x, y, z$, and $k$, if $x \equiv_k y$ then $xz \equiv_k yz$.
\end{center}
Determine whether this statement is true. If it's true, write a proof of the statement. If it's false, write a
\emph{disproof} of that statement (take a look at the Proofwriting Checklist for information about how to write a
disproof). You can use any proof techniques you'd like.

\annotate{This is your first example of a ``prove or disprove'' problem. Your first task is to figure out whether it's
  true or false, since if it's true you'll want to prove it and if it's false you'll want to disprove it.}

\annotate{Here are two strategies for approaching problems like these. First, try out a lot of examples! You'll want to
  get a feel for what the symbolic expression above ``feels'' like in practice. Second, get a sheet of scratch paper and
  write out both the statement and its negation. One of those statements is true, and your task is to figure out which
  one it is. Once you have those two statements, think about what you would need to do to prove each of them. In each
  case, what would you be assuming? What would you need to prove? If you can answer those questions, you can explore
  both options and seeing which one ends up panning out.}

\annotate{Finally, remember to call back to definitions! Regardless of whether you're proving or disproving this, you'll
  want to refer to the formal definition of modular congruence from the checkpoint problem.}

\begin{shaded}
  Provide a proof or disproof here.
\end{shaded}

\section{Proof Critiques, Part Two}

Proofs on set theory follow the same general rules as proofs on any other structure, though they tend to be a little
more nuanced. Critique the following two proofs on set theory by following the same instructions as in Problem Four
(apply the Proofwriting Checklist, flag any logic errors, determine whether the theorems are true, and then either
rewrite the proof or briefly explain why the statement in question isn't true to begin with.)

We \emph{strongly} recommend reading the Guide to Set Theory Proofs before starting this problem.

\begin{enumerate}[label*=\roman*.,ref=\roman*]
  \item Critique this proof about sets.
        \begin{thm}
          If $A \subseteq B$ and $A \subseteq C$, then $A \subseteq B \cap C$.
        \end{thm}
        \begin{prf}
          Since $A \subseteq B$, it means that some group of the elements of $B$ is the set $A$. Since $A \subseteq C$,
          it means that some group of the elements of $C$ is the set $A$. Therefore, some group of the elements of $B
          \cap C$ is the set $A$, so $A \subseteq B \cap C$.
        \end{prf}

        \begin{shaded}
          Write your critique and newly-revised proof here.
        \end{shaded}

  \item Critique this proof about sets. Here, the notation $S \subsetneq T$ is read as ``$S$ is a \emph{strict subset}
        of $T$'' and means that $S \subseteq T$ and $S \neq T$.
        \begin{thm}
          If $A \subsetneq B$ and $A \subsetneq C$, then $A \subsetneq B \cap C$.
        \end{thm}
        \begin{prf}
          Since $A \subsetneq B$, it means that some group of the elements of $B$ is the set $A$, and there are some
          other elements of $B$. Since $A \subsetneq C$, it means that some group of the elements of $C$ is the set $A$,
          and there are some other elements of $C$. Therefore, some group of the elements of $B \cap C$ is the set $A$,
          and there are some other elements of $B \cap C$, so $A \subsetneq B \cap C$.
        \end{prf}

        \begin{shaded}
          Write your critique and newly-revised proof here.
        \end{shaded}

\end{enumerate}


\section{Properties of Sets}

For each of these statements about sets, decide whether that statement is true or false. Prove each true statement, and
disprove each false statement.

\begin{enumerate}[label*=\roman*.,ref=\roman*]
  \item Prove or disprove: for all sets $A$, $B$, and $C$, if $A \in B$ and $B \in C$, then $A \in C$.
\end{enumerate}
\annotate{As a note, it is true that if $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$. But $\subseteq$ and
$\in$ are different concepts.}
\begin{shaded}
  Provide a proof or disproof here.
\end{shaded}

\begin{enumerate}[resume*]
  \item Prove or disprove: if $A$, $B$, and $C$ are sets where $A - C = B - C$, then $A = B$.
\end{enumerate}
\annotate{A question you should be able to answer before starting this problem: how do you prove that two sets are equal
  to one another? Based on that, how do you prove that two sets are \emph{not} equal to one another?  Check the Guide to
  Proofs on Sets for details.}
\begin{shaded}
  Provide a proof or disproof here.
\end{shaded}

\begin{enumerate}[resume*]
  \item Prove or disprove: if $A$ and $B$ are sets and $A \in B$, then $\wp(A) \in \wp(B)$.
\end{enumerate}
\begin{shaded}
  Provide a proof or disproof here.
\end{shaded}

\begin{enumerate}[resume*]
  \item Prove or disprove: if $A$ and $B$ are sets and $\wp(A) \in \wp(B)$, then $A \in B$.
\end{enumerate}
\annotate{Notice that this implication essentially is the statement from part (iii) with the antecedent and consequent
  swapped. We sometimes call this the \emph{converse} of the implication. Every implication is equivalent to its
  contrapositive, but not all implications are equivalent to their converses.}
\begin{shaded}
  Provide a proof or disproof here.
\end{shaded}

\begin{enumerate}[resume*]
  \item Prove or disprove: if $A$, $B$, and $C$ are sets where $A \Delta C = B \Delta C$, then $A = B$.
\end{enumerate}
\annotate{Again, you're asked to determine whether two sets are equal. If you want to disprove this statement, write
  out, specifically, what it is that you need to show. If you want to prove this, write out, explicitly, what you need
  to prove.}
\begin{shaded}
  Provide a proof or disproof here.
\end{shaded}

\annotate{Before you turn in these proofs, read over the Proofwriting Checklist and the Guide to Proofs on Sets and
  confirm that your proof meets our style criteria. Here are a few specific things to look for:
  \begin{itemize}
    \item Make sure that your proofs match the definitions of the relevant terms. To prove $S \subseteq T$, pick an
          arbitrary $x \in S$, then prove $x \in T$ by making claims about $x$. To prove $S = T$, prove $S \subseteq T$
          and $T \subseteq S$.
    \item However, avoid restating definitions in the abstract. For example, rather than writing
          \begin{center}
            ``We know that $S \subseteq T$ if every element of $S$ is an element of $T$. \\
            Therefore, since we know that $A \subseteq B$ and $x \in A$, we see that $x \in B$.''
          \end{center}
          instead remove that first sentence and just write something like this:
          \begin{center}
            ``Since $x \in A$ and $A \subseteq B$, we see that $x \in B$.''
          \end{center}
          Whoever is reading your proof knows all the relevant definitions. They're more interested in seeing
          \emph{how those definitions interact with one another} than \emph{what those definitions are}.
    \item Make sure you clearly indicate what each variable means and whether it's chosen arbitrarily or chosen to have
          a specific value. For example, if you refer to variables like A, B, or C, you should clearly indicate whether
          they're chosen arbitrarily or refer to specific values.
    \item When talking about an arbitrary set A, it's tempting to list off the elements of A by writing something like
          $A = \{ x_1, x_2, \ldots, x_n \}$. The problem is that writing $A = \{ x_1, x_2, \ldots, x_n \}$ implicitly
          says that the set $A$ is finite, since you're saying it only has $n$ elements in it. This is a problem if $A$
          is infinite. In fact, if $A$ is infinite, because of Cantor's theorem, you can't necessarily even write $A =
          \{ x_1, x_2, x_3, \ldots \}$, since you might run out of natural numbers with which to name the elements of
          $A$!
  \end{itemize}
}

\section{Tournament Champions}
\begin{wrapfigure}{r}{3.75cm}
  \begin{tikzpicture}[x=1.5cm, y=1.5cm]
    \node[draw, circle] (C) at (1, 0) {$C$};
    \node[draw, circle] (B) at
    (0.30901699437494745, 0.9510565162951535) {$B$};
    \node[draw, circle] (A) at
    (-0.8090169943749473, 0.5877852522924732) {$A$};
    \node[draw, circle] (E) at
    (-0.8090169943749475, -0.587785252292473) {$E$};
    \node[draw, circle] (D) at
    (0.30901699437494723, -0.9510565162951536) {$D$};
    \path[->] (B) edge (A);
    \path[->] (C) edge (A);
    \path[->] (D) edge (A);
    \path[->] (A) edge (E);
    \path[->] (B) edge (C);
    \path[->] (B) edge (D);
    \path[->] (E) edge (B);
    \path[->] (C) edge (D);
    \path[->] (C) edge (E);
    \path[->] (D) edge (E);
  \end{tikzpicture}
\end{wrapfigure}
A \emph{tournament} is a contest among $n$ players. Each player plays a game against each other player, and either wins
or loses the game (let's assume that there are no draws). We can visually represent a tournament by drawing a circle for
each player and adding arrows between pairs of players to indicate who won each game. For example, in the tournament to
the right, player $A$ beat player $E$, but lost to players $B$, $C$, and $D$. \\

A \emph{tournament champion} is a player $c$ where, for each other player $p$ in the tournament, either
\begin{itemize}
  \item $c$ won her game against $p$, or
  \item there's a player $q$ where $c$ won her game against $q$ and $q$ won his game against $p$.
\end{itemize}
In the tournament shown here, player $B$ is a champion: she won against $A$, $C$, and $D$, and although she lost to $E$,
she won against $D$, who in turn won against $E$. Player $C$ is also a champion: she won against $A$, $D$, and $E$, and
the one player she lost to ($B$) is covered because $C$ won against $E$, who in turn won against $B$. Player $A$,
however, is not a tournament champion. To see this, $A$ didn't win against $C$, nor is there any player who $A$ won
against who in turn won against $C$.

\begin{enumerate}[label*=\roman*.,ref=\roman*]
  \item Is player $D$ a tournament champion? How about player $E$? No justification required.
\end{enumerate}
\annotate{This is all about applying the definition. You might have an intuition for what a tournament champion is, but
  to determine the answers to these questions, you'll have to look back at the definition.}
\begin{shaded}
  Write your answer here.
\end{shaded}

Here's an amazing fact about tournaments.
\begin{enumerate}[resume*]
  \item Let $T$ be an arbitrary tournament and $p$ be any player in that tournament. Prove the following statement: if
        $p$ won more games than anyone else in $T$ or is tied for winning the greatest number of games, then $p$ is a
        tournament champion in $T$.
\end{enumerate}
\annotate{Remember that proofwriting heavily involves leveraging definitions. Intuitively it makes sense that someone
  who won the most games did the best in a tournament, but that's not what's being asked here. Instead, you're asked to
  show that if someone won the most games (or tied for winning the most games), then they specifically meet the criteria
  described above that characterize what a tournament champion is.}
\annotate{A great question to ponder -- what has to happen for someone to not be a tournament champion? Don't guess
  based on your intuition; negate the definition of a tournament champion and see what happens. You might want to draw a
  picture of what happens in this case.}
\begin{shaded}
  Provide a proof here.
\end{shaded}
A corollary of the result you proved from (ii) is that every tournament with at least one player has at least one
tournament champion -- pick someone who won the most games or is tied for winning the most games. \\

\begin{enumerate}[resume*]
  \item Prove or disprove: if $T$ is a tournament and $c$ is a champion in $T$, then either $c$ won the most games or is
        tied for winning the most games.
\end{enumerate}
\annotate{This is the converse of the result from part (ii). Remember -- the converse of an implication is not
  necessarily equivalent to the original implication.}
\begin{shaded}
  Provide a proof or disproof here.
\end{shaded}

The result you proved in part (ii) of this problem is noteworthy for several reasons. First, this is a fundamental
result about tournaments -- many aspects of tournaments can be better understood by looking at its champions. Second,
it's an example of a style of proof called a proof by extreme case. In a proof of that sort, you pick some "extreme"
object, usually the biggest or smallest object of some type, then prove that it has some property. Here, you proved that
the "winningest" player must be a tournament champion. Keep this idea in mind for the future -- you'll likely get some
more mileage out of it!

\section*{Optional Fun Problems}

\annotate{On each problem set, we'll provide some optional fun problems for extra credit. These are problems that can be
  solved purely using the techniques you've learned so far, but which will require more thought than the other problems
  on the problem set. Each problem, in our opinion, has a beautiful solution that will give you a much deeper
  understanding of core concepts, so we strongly encourage you to play around with them if you get the chance. Please
  feel free to work on as many of these problem as you'd like, though please only submit a solution to at most one of
  the optional fun problems on each problem set. If you submit submissions to both problems, we will pick one to grade
  Arbitrarily and Capriciously. \smiley} \\

\annotate{When we compute final grades at the end of the quarter, we compute the grading curve without any extra credit
  factored in, then recompute grades a second time to factor in extra credit. This way, you're not at any disadvantage
  if you decide not to work through these problems. If you do complete the extra credit problems, you may get a slight
  boost to your overall grade.} \\

\annotate{As a matter of course policy, we don't provide any hints on the extra credit problems -- after all, they're
  supposed to be challenge problems! However, we're happy to chat about them after the problem sets come due.}

\section*{Optional Fun Problem One: Hat Colors}

You and nine of your friends are brought into a room together. The CS103 TAs go around and place a hat on everyone's
head. There are ten different colors of hats -- red, orange, yellow, green, blue, magenta, black, white, gray, and gold.
It's possible that everyone gets a hat of a different color. It's possible that everyone gets a hat of the same color.
In fact, aside from the restriction that each hat is one of the ten colors mentioned earlier, there are no restrictions
about how many hats there are of each color. \\

You and your friends can all look around to see what color hats everyone else is wearing, but no one can see their own
hat color. The staff will then go around and ask everyone to write down a guess of what color their hat is. We'll then
collect those guesses and reveal them all at once. You and your friends succeed if at least one of you is able to
correctly guess their own hat color. You and your friends all lose if no one correctly guesses their own hat color. \\

Before we place hats on everyone, we'll allow you and your friends to work out a strategy about how you're going to
guess, but once the hats are on no communication of any kind -- whether explicit or implicit -- is permitted between the
group. Devise a strategy that \textit{guarantees} at least one person will correctly guess their own hat color, even if
we know what strategy you'll be using. Then, using the mathematical notation and tools you've learned so far in this
course, formally prove that your strategy works. For example, here are a few strategies you could choose from that
\textit{don't} work:
\begin{itemize}
  \item Everyone could pick which color they're going to guess before going into the room, and then write down that
        guess regardless of what color hats they see on everyone else. If we assign hats randomly, then the probability
        that this works is approximately $1 - e^{-1}$ (take CS109 if you're curious why this is!) However, if we
        overhear your discussion, we could be mean and deliberately give everyone the wrong hat color, making your
        probability of success exactly 0.

  \item Everyone could arrange themselves in a circle, then guess the color of the hat of the person immediately to
        their left. If we choose hat colors randomly, then there's a decent probability that someone will correctly
        guess their own hat color. But if we know that this is what you're going to do, we can just give everyone a
        different hat color and you're guaranteed to lose
\end{itemize}

\annotate{I first heard this problem from Michelle McGhee, CS major (theory track), storyteller, and Ultimate Frisbee
  player. Her senior project was a program that generated freestyle rap lyrics.}

\begin{shaded}
  Provide a description of your strategy and a proof that it works here.
\end{shaded}

\section*{Optional Fun Problem Two: Infinite Deviation}

In our first class meeting, we sketched out a proof of Cantor's theorem. This proof assumed there was a pairing between
the elements of a set $S$ and the subsets of $S$, then constructed a set that was different in at least one position
from each of the paired sets. \\

Show that, no matter how you pair the elements of $\mathbb{N}$ with the subsets of $\mathbb{N}$, there's always at least
one set $X \subseteq \mathbb{N}$ that differs in \textit{infinitely many} positions from each of the paired sets.
Justify your answer, but no formal proof is necessary.

\begin{shaded}
  Write your answer here.
\end{shaded}

\end{document}
