%
% LaTeX Problem Set Template originally designed
% by former CS103 TA Sachin Padmanabhan, with updates,
% edits, and simplifications by the lovely folks below.
%
% Updated for Fall 2018 by Michael Zhu
% Updated for Fall 2019 by Joshua Spayd
% Updated for Fall 2020 by Lucy Lu
% Updated for Winter/Spring 2021 by Cynthia Bailey Lee
% Updated for Fall 2021 by Grant McClearn
% Commands slimmed down and simplified in Fall 2022 by Keith Schwarz

\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathdots}
\usepackage{braket}
\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 \#2}
\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 2}
\rhead{\today}
\lfoot{}
\cfoot{CS 103: Mathematical Foundations of Computing --- Winter 2024}
\rfoot{\thepage}

\newcommand{\abs}[1]{\lvert #1 \rvert}
\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{\powerset}[1]{\wp\left(#1\right)}
\newcommand{\suchthat}{\ \vert \ }
\newcommand{\naturals}{\mathbb{N}}
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\reals}{\mathbb{R}}
\renewcommand{\qed}{\blacksquare}
\newcommand{\accepts}{\text{ accepts }}
\newcommand{\rejects}{\text{ rejects }}
\newcommand{\loopson}{\text{ loops on }}
\newcommand{\haltson}{\text{ halts on }}
\newcommand{\encoded}[1]{\left\langle#1\right\rangle}
\newcommand{\rlangs}{\mathbf{R}}
\newcommand{\relangs}{\mathbf{RE}}
\newcommand{\corelangs}{\text{co-}\mathbf{RE}}
\newcommand{\plangs}{\mathbf{P}}
\newcommand{\nplangs}{\mathbf{NP}}

\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

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

\usepackage{boxedminipage}
\newenvironment{blank}{\colorbox{shadecolor}{\strut \underline{\ \ \ \ \ }}}

\begin{document}

\maketitle

\begin{center}
  \emph{Due Friday, January 26 at 4:00 pm Pacific}
\end{center}

\vspace{1cm}

Problems One through Six are to be answered by editing the appropriate files (see the Problem Set \#2 instructions). You won't include your answers to those problems here.

\section*{Symbols Reference}
Here are some symbols that may be useful for this PSet. If you are using \LaTeX, view this section in the template file (the code in \texttt{cs103-ps2-template.tex}, not the PDF) and copy-paste math code snippets from the list below into your responses, as needed. If you are typing your Pset in another program such as Microsoft Word, you should be able to copy some of the symbols below from this PDF and paste them into your program. Unfortunately the symbols with a slash through them (for ``not'') and font formats such as exponents don't usually copy well from PDF, but you may be able to type them in your editor using its built-in tools.
\begin{itemize}
    \item Logical AND: $\land$
    \item Logical OR: $\lor$
    \item Logical NOT: $\lnot$
    \item Logical implies: $\to$
    \item Logical biconditional: $\leftrightarrow$
    \item Logical TRUE: $\top$
    \item Logical FALSE: $\bot$
    \item Universal quantifier: $\forall$
    \item Existential quantifier: $\exists$
\end{itemize}

\LaTeX typing tips:
\begin{itemize}
    \item Set (curly braces need an escape character backslash): ${1, 2, 3}$ (incorrect), $\{1, 2, 3\}$ (correct)
    \item Exponents (use curly braces if exponent is more than 1 character): $x^2$, $2^{3x}$
    \item Subscripts (use curly braces if subscript is more than 1 character): $x_0$, $x_{10}$
\end{itemize}
    
\newpage

\section*{Problem Seven: Yablo's Paradox}
    i.
    \begin{shaded}
    Write your answer to Problem Seven, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Seven, part ii. here.
    \end{shaded}
    
    iii.
    \begin{shaded}
    Write your answer to Problem Seven, part iii. here.
    \end{shaded}

\newpage

\section*{Problem Eight: Hereditary Sets}
    i.
    \begin{shaded}
    Write your answer to Problem Eight, part i. here.
    \end{shaded}
        
    ii.
    \begin{shaded}
    Write your answer to Problem Eight, part ii. here.
    \end{shaded}
    
\newpage

\section*{Problem Nine: Tournament Champions}
    i.
    \begin{shaded}
    Write your answer to Problem Nine, part i. here.
    \end{shaded}
    
    ii.
    \begin{shaded}
    Write your answer to Problem Nine, part ii. here.
    \end{shaded}
    
\newpage

\section*{Optional Fun Problem: Insufficient Connectives}

\begin{shaded}
Write your answer to the Optional Fun Problem here.
\end{shaded}
    
\end{document}