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

\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}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=blue,
}

\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#1}
\author{YOUR NAME, PARTNERS NAME}
\date{\today}

\lhead{YOUR NAME, PARTNERS NAME}
\chead{Problem Set 1}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Winter 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}

% For Polyominoes
% Source: https://tex.stackexchange.com/a/110669
\usepackage{color}

\definecolor{lightgray}{rgb}{0.75, 0.75, 0.75}

\newdimen\omsq  \omsq=16pt
\newdimen\omrule    \omrule=1pt
\newdimen\omint

\newif\ifvth    \newif\ifhth    \newif\ifomblank
\def\OMINO#1{%
    \vthtrue \hthtrue
    \vbox{ \offinterlineskip\parindent=0pt \OM#1\relax\vskip1pt}}
\definecolor{gray}{rgb}{0.5, 0.5, 0.5}

\def\OM#1{%
    \omint=\omsq    \advance\omint-\omrule
    \ifx\relax#1%
    \else
      \ifx\\#1 \newline\null \hthtrue \ifvth\vthfalse\else\vskip-\omrule\vthtrue\fi
      \else%
        \ifx .#1\hskip\ifhth \omrule\else \omint\fi
        \else%
          \ifx +#1\def\colour{black}\fi%
          \ifx -#1\def\colour{black}\fi%
          \ifx |#1\def\colour{black}\fi%
          \ifx @#1\def\colour{black}\fi%
          \ifx r#1\def\colour{red}\fi%
          \ifx g#1\def\colour{green}\fi%
          \ifx b#1\def\colour{blue}\fi%
          \ifx y#1\def\colour{yellow}\fi%
          \ifx m#1\def\colour{magenta}\fi%
          \ifx c#1\def\colour{cyan}\fi%
          \ifx x#1\def\colour{lightgray}\fi%
          \textcolor{\colour}{\rule{\ifhth\omrule\else\omsq\fi}{\ifvth\omrule\else\omsq\fi}}%
          \ifhth\else\hskip -\omrule\fi%
        \fi%
        \ifhth\hthfalse\else\hthtrue\fi%
      \fi%
    \expandafter\OM%
    \fi}

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

\textit{\textcolor{blue}{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 \textbf{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$.

\textit{\textcolor{blue}{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}

\item Prove that for any integers $x$ and $y$ and any integer $k$ that if $x \equiv_k y$, then $y \equiv_k x$.

\textit{\textcolor{blue}{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}

\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$.

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

\end{enumerate}

Modular congruence is a powerful mathematical tool. You'll use it later in this problem set to build a better
understanding of star-drawing!

\pagebreak

\begin{center}
\textit{\textbf{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 six $\mathsf{.object}$ files through GradeScope under ``Coding Problems for Problem Set One'' by uploading your edited starter files. 
\end{shaded}

\section{Set Theory in C++}

\begin{shaded}
Submit your edited $\mathsf{SetTheory.cpp}$ file through GradeScope under ``Coding Problems for Problem Set One''.
\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 \textit{\textbf{without}} using
plain English, \textit{\textbf{without}} using set-builder notation, \textit{\textbf{without}} introducing any new variables, and \textit{\textbf{without}} using propositional or first-order logic (which we'll cover next week).

\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.

\textit{\textcolor{blue}{Once you've written up your answer to this problem, take a minute to \textbf{type-check} it. As an example, suppose
that you have the following answer: 
\begin{equation*}
(C \in M) \cap (V \in M)
\end{equation*}
This expression can't possibly be right, and here's one way to see this. The expression $C \in M$ is of type
boolean -- either $C \in M$ is true or it isn't -- and the same is true of $V \in M$. 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. }}

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

\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.

\textit{\textcolor{blue}{You can type-check this answer in a different way. For example, suppose you came up with this expression:
\begin{equation*}
Y \cup D
\end{equation*}
Here, $Y$ and $D$ are sets, so it's perfectly fine to write $Y \cup D$, which evaluates to an object of type set. But
notice that the statement here asks you to write an expression that says ``you have a hobby that your date
doesn't have,'' and that statement is essentially of type boolean (you either do or do not have a hobby your
date doesn't have). Therefore. $Y \cup D$ 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). }}

\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, $I$ 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. 

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

\item Let's say that a \textit{\textbf{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.

\textit{\textcolor{blue}{Something to think about: how would you say ``all committees made purely of students?'' }}

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

\end{enumerate}

\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 \textit{\textbf{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 \textit{\textbf{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 \textit{\textbf{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 \textit{\textbf{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 II}

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?

Below are two statements. For each true statement, write a proof that the statement is true. For each false statement, write a disproof of the 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. 

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

\item Prove or disprove: for any integers $x, y, z$, and $k$, if $x \equiv_k y$ then $xz \equiv_k yz$.

\textit{\textcolor{blue}{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.}}

\textit{\textcolor{blue}{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.}}

\textit{\textcolor{blue}{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}

\item Prove or disprove: for any integers $x, y, z$ and $k$, if $z \neq 0$ and $xz \equiv_k yz$, then $x \equiv_k y$.


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

\end{enumerate}

\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$.

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

\item Prove or disprove: if $A$, $B$, and $C$ are sets where $A - C = B - C$, then $A = B$.

\textit{\textcolor{blue}{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 not equal to one another? Check the Guide to Proofs on Sets for details.}}

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

\item Prove or disprove: if $A$ and $B$ are sets where $\wp(A) = \wp(B)$, then $A = B$.

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

\item Prove or disprove: if $A$, $B$, and $C$ are sets where $A \Delta C = B \Delta C$, then $A = B$.

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

\end{enumerate}

\textit{\textcolor{blue}{ 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 the structures of 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
\textbf{how those definitions interact with one another} than \textbf{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{Yablo's Paradox}

A \emph{logical paradox} is a statement that results in a contradiction
regardless of whether it's true or false.
One of the simplest paradoxes is the \emph{Liar's paradox},
which is the following:
\begin{center}
\emph{This statement is false.}
\end{center}
If this statement is true,
then by its own admission, it must be false -- a contradiction!
On the other hand, if the above statement is false, then the statement ``This statement is false'' is false, and therefore the
statement ``This statement is false'' is true -- a contradiction!
Since this statement results in a contradiction regardless of whether
it's true or false, it's a paradox. \\

Paradoxes often arise as a result of self-reference.
In the Liar's Paradox,
the paradox arises because the statement itself directly refers to itself.
However, it's not the only paradox that can arise from self-reference.
This problem explores a paradox called \emph{Yablo's paradox}. \\

Consider the following collection of infinitely many statements numbered
$S_0, S_1, S_2,\dots,$ where there is a statement $S_n$ for each
natural number $n$.
These statements are ordered in a list as follows:
\begin{figure}[H]
\begin{mdframed}[backgroundcolor=yellow!20] 
\begin{center}
$(S_0)$: All statements in this list after this one are false. \\
$(S_1)$: All statements in this list after this one are false. \\
$(S_2)$: All statements in this list after this one are false. \\
$\cdots$
\end{center}
\end{mdframed}
\end{figure}

More generally, for each $n \in \N$,
the statement $(S_n)$ is
\begin{center}
$(S_n)$: All statements in this list after this one are false.
\end{center}
Surprisingly,
the interplay between these statements makes every statement in the list
a paradox.

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

\item Prove that if any statement in this list is true, it results in a contradiction.

\end{enumerate}

\textit{\textcolor{blue}{Your result needs to work for any choice of statement in the list, not just one of them. Follow the template for proving a universally-quantified statement}}

\begin{enumerate}[resume*]

\item Prove that every statement in this list is a paradox. 

\end{enumerate}

\textit{\textcolor{blue}{Something to ponder: how do you negate a universally-quantified statement?}}

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

Now, consider the following modification to this list.
Instead of infinitely many statements,
suppose that there are ``only'' $10,000,000,000$ statements.
Specifically, suppose we have these statements:
\begin{mdframed}[backgroundcolor=yellow!20] 
\begin{center}
$(T_0)$: All statements in this list after this one are false. \\
$(T_1)$: All statements in this list after this one are false. \\
$(T_2)$: All statements in this list after this one are false. \\
$\cdots$ \\
$(T_{9,999,999,999})$: All statements in this list after this one are false.
\end{center}
\end{mdframed}
There's still a lot of statements here,
but not infinitely many of them.
Interestingly,
these statements are all perfectly consistent with one another and do not
result in any paradoxes.

\begin{enumerate}[resume*]

\item For each statement in the above list,
determine whether it's true or false and explain why
your choices are consistent with one another.

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

\end{enumerate}

Going forward, don't worry about paradoxical statements in CS103.
We won't talk about any more statements like these.
\smiley

\section{The Star-Drawing Saga, Part II}

On Problem Set 0, you got to play around with star drawing and discovered that certain combinations of a number of points p and a step size s led to simple stars (for example, the \{7 / 2\} and \{8 / 3\} stars), while other combinations did not (for example, the \{8 / 2\} or \{12 / 3\} stars). Why exactly is this? Over the course of the next several problem sets, you'll discover exactly why! \\

The main insight that we'll use in analyzing stars is to recognize a connection between star-drawing, which you saw on Problem Set Zero, and modular congruence, which you explored in this problem set. Imagine that you set out to draw a p-pointed star by drawing p points around a circle. Let's number those points $0, 1, 2, \dots, p - 1$, going clockwise around the circle. (Of course we're using zero-indexing - we're computer scientists!) We'll then draw the star by starting at position 0, then drawing a line to the point $s$ positions clockwise from us, then drawing a line from there to the point $s$ positions clockwise from that, etc. until we end back up at position 0. 

\begin{enumerate}[label*=\roman*.,ref=\roman*]
    \item Let's suppose we're following the above procedure and stop after drawing $t$ total lines and end up on point $n$ on the star. Explain, intuitively, why $n \equiv_p s \cdot t$.
    
    \begin{shaded}
    Write your answer here.
    \end{shaded}
    
\end{enumerate}

\annotate{Mathematicians conventionally use single-letter variable names for everything, which can lead to really dense formulas. Computer scientists love to use longer variable names to improve readability. If you're having trouble interpreting that above formula, consider writing a ``cheat sheet'' that lists each variable along with a more verbose description of what it represents.} \\

If we pick a number of points $p$ and a step size $s$, we end up with a simple star if we end up passing through each of the $p$ points before ending back at our starting point. The modular equation you just saw in part (i) of this problem tells us where on the star we'll be at each point in time. Putting these two ideas together gives us this fundamental fact about stars:
\begin{center}
    Simple Star Criterion: A $p$-point star with a step size of $s$ is a simple star if and only if for every natural number $n$, there is a natural number $t$ such that $n \equiv_p s \cdot t$.
\end{center}
This statement is slightly dense, and like all mathematically dense statements, one of the best ways to get a handle on what it says is to try it out in some specific cases.

\begin{enumerate}[resume*]
    \item Consider a star polygon with nine points and a step size of two (the \{9 / 2\} star). This is a simple star. Show that it meets the star polygon criterion by filling in the table below, listing off values of $t$ such that $n \equiv_p s \cdot t$.

\begin{shaded}
\begin{table}[H]
\begin{tabular}{rlllllllll}
\emph{n} & \emph{0} & \emph{1} & \emph{2} & \emph{3} & \emph{4} & \emph{5} & \emph{6} & \emph{7} & \emph{8} \\ \cline{2-10} 
\multicolumn{1}{l|}{\emph{Value of $t$ where $n \equiv_p s \cdot t$}} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} \\ \cline{2-10} 
\end{tabular}
\end{table}
\end{shaded}

\end{enumerate}

\annotate{It's somewhat tricky to fill this table in purely by eyeballing the mathematical formula and trying to guess numbers. Instead, think back to the intuition behind this formula. You might want to try drawing the star and seeing whether that gives you any new insights.} \\

On Problem Set 0, you explored several different cases that led to simple stars and several that didn't. One observation you might have made is that if you have an odd number of points, you can always form a simple star by taking steps of size two.

\begin{enumerate}[resume*]
    \item Using the simple star criterion, prove that \{$p$ / 2\} is a simple star for any odd natural number $p$.
    
    \begin{shaded}
    Provide a proof here.
    \end{shaded}
\end{enumerate}

\annotate{This problem has a lot of moving parts, so proceed slowly and methodically. } \\ 

\annotate{Before you spend time trying to solve this problem, answer the following questions. What, specifically, will you be assuming? What, specifically, do you need to prove? To check that you've done this properly, you should ultimately find yourself assuming that you have a bunch of arbitrarily-chosen values and trying to prove an existential statement. That's going to require you to find an integer with certain properties, and that's the creative step of the proof. } \\

\annotate{Look back at the table you wrote in part (ii) of this problem. Do you see a pattern in the numbers you used to fill in the table? Try writing out corresponding tables for other values of p, like 5, 7, 11, or 13. Can you generalize the pattern you came up with to work for any odd number p, not just 9? Ideally, you should be able to answer the questions "what entry goes in the column if n is 42 and if p is 137?" or "what entry goes in the column for n is 103 if p is 271?" If you're able to answer those questions, you've had the insights that you need, and you should try writing up your answer as a formal proof. } \\

\annotate{In the course of solving this problem you are going to be working with a bunch of variables - p for starters, plus some more that will present themselves as you work through the rest of the logic. Keep track of what those variables represent, which variables have values you are allowed to pick, and which ones have values that are out of your control. A useful tip, make a little cheat sheet describing what each variable represents.} 

\pagebreak

\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 some thought. 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.} \\

\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, when she was helping staff Girl Code @Stanford in 2018. 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. If you'll recall, this proof worked by assuming there was a pairing between the elements of a set $S$ and the subsets of that set $S$, then constructing a set that was different in at least one position from each of the paired sets. \\

Suppose you try to pair off the elements of $\mathbb{N}$ with the subsets of $\mathbb{N}$. Show that, no matter how you do this, there's always at least one set $X \subseteq \mathbb{N}$ that differs in 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}