%
% 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 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{minted}
\usepackage{wrapfig}
\usepackage{hyperref}

\title{CS 103: Mathematical Foundations of Computing\\Problem Set \#2}
\author{Your Name(s) Here}
\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 --- 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{\Q}{\mathbb{Q}}
\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}}

\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}
\RecustomVerbatimEnvironment{Verbatim}{BVerbatim}{}

\hypersetup{urlcolor=blue}

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

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

\begin{document}

\maketitle

\section*{Checkpoint Problem One: Interpersonal Dynamics}

\begin{wrapfigure}{r}{3.75cm}
  \begin{tikzpicture}[shorten >=1pt,node distance=2cm,on
      grid,auto,baseline={(current bounding box.north)}]
    \node[state] (A)   {$A$};
    \node[state] (C) [below=of A] {$C$};
    \node[state] (B) [left=of C] {$B$};
    \node[state] (D) [right=of C] {$D$};
    \node[state] (E) [below=of C] {$E$};
    \node[state] (F) [right=of E] {$F$};
    \path[->]
    (A) edge [bend left=30] node {} (C)
        edge [loop right] node {} ()
    (B) edge [loop above] node {} ()
    (C) edge [bend left=30] node {} (A)
        edge node {} (B)
        edge node {} (D)
        edge [bend left = 30] node {} (E)
    (D) edge [loop above] node {} ()
    (E) edge [bend left=30] node {} (C)
        edge [loop right] node {} ()
    (F) edge [loop above] node {} ();
  \end{tikzpicture}
\end{wrapfigure}

The diagram to the right represents a set of people named $A, B, C, D, E,$ and
$F$. If there's an arrow from a person $x$ to a person $y$, then person $x$
loves person $y$. We'll denote this by writing $\textit{Loves}(x, y)$. For
example, in this picture, we have $\textit{Loves}(C, D)$ and $\textit{Loves}(E,
E)$, but not $\textit{Loves}(D, A)$. \\

There are no ``implied'' arrows anywhere in this diagram. For example, even
though $A$ loves $C$ and $C$ loves $E$, the statement $\textit{Loves}(A, E)$ is
false because there's no direct arrow from $A$ to $E$. Similarly, even though
$C$ loves $D$, the statement $\textit{Loves}(D, C)$ is false because there's no
arrow from $D$ to $C$. \\

Below is a series of ten first-order logic statements. For each of those
statements, tell us the minimum number of additional arrows that must be added
to the diagram to the right to make that formula true. You’re only allowed to
add arrows; you can’t remove existing ones. If a formula is already true, the
answer will be ``zero'' because no edges need to be added. Then, tell us what
those arrows are, and briefly explain why that’s the smallest number of arrows
that need to be added.

\begin{enumerate}[label=\roman*.,ref=\roman*]
  \item $Loves(A, A) \rightarrow Loves(E, E)$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $Loves(A, B) \rightarrow Loves(C, D)$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $Loves(A, C) \rightarrow Loves(C, F)$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $Loves(A, D) \rightarrow Loves(D, E)$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $Loves(A, D) \leftrightarrow Loves(B, C)$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $Loves(A, C) \leftrightarrow Loves(E, C)$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $\forall x.~\exists y.\ Loves(x, y)$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $\forall x.~\exists y.\ (x \ne y \land Loves(x, y))$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $\exists x.~\forall y.\ Loves(x, y)$
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item $\exists x.~\forall y.\ (x \ne y \rightarrow Loves(x, y))$
    \begin{shaded}
      Write your answer here.
    \end{shaded}
\end{enumerate}

\pagebreak

\section*{Checkpoint Problem Two: First-Order Fundamentals}

Consider the following first-order logic statement:
\begin{flalign*}
  &\exists p.\ (Problem(p) \land \\
  &\qquad \forall g.~(Program(g) \rightarrow \lnot Solves(g, p)) \\
  &)
\end{flalign*}
Here, the predicate $Problem(x)$ states that $x$ is a problem, the predicate
$Program(y)$ states that $y$ is a program, and the predicate $Solves(a, b)$
states that $a$ solves $b$.

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

  \item Translate this formula into plain English. No justification is required.
    \begin{shaded}
      Write your answer here.
    \end{shaded}

  \item Write a first-order logic formula that is the negation of the above
    formula. Your formula should not include any negations, except possibly
    for direct negations of predicates.

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

\end{enumerate}

\annotate{We \emph{strongly} recommend reading over the Guide to Negations
  before attempting the above problem.}

\begin{enumerate}[resume*]

  \item Using only the predicates given above, write a statement in first-order
    logic that says ``there is a program that solves every problem.'' (Alas,
    this isn’t true, but wouldn’t it be nice?)

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

\end{enumerate}

\annotate{We \emph{strongly} recommend reading over the Guide to Logic
  Translations before attempting the above problem.}

\pagebreak

\section{Propositional Completeness}
\begin{shaded}
  Submit your edited $\mathsf{PropositionalCompleteness.proplogic}$ file through
  Gradescope under ``Programming Assignment 2''.
\end{shaded}

\section{Set Theory and Propositional Logic}

(Parts (i) -- (v) of this question are autograded; please edit the file
$\mathsf{SetTheory.proplogic}$ in the Problem Set Two starter files with your
answers. Part (vi) should be submitted as part of your written answers.)

Imagine we have two sets $A$ and $B$ and some object x. Let’s introduce two
propositional variables:
\begin{itemize}
  \item $a$, which states that $x \in A$, and
  \item $b$, which states that $x \in B$.
\end{itemize}

By combining $a$ and $b$ together in different ways using propositional logic,
we can express different claims about how $x$ relates to $A$ and $B$.
\begin{shaded}
  For parts (i) -- (v), submit your edited $\mathsf{SetTheory.proplogic}$ file
  through Gradescope under ``Programming Assignment 2''.
\end{shaded}

Now, suppose we have some third set $C$. Let’s introduce a third propositional
variable $c$ that means $x \in C$.

\begin{enumerate}[label*=\roman*.,ref=\roman*]
  \setcounter{enumi}{5}
  \item Using your answer to part (v) as a starting point, simplify the
    expression $(A \Delta B) \Delta B$ as much as possible. Briefly justify your
    answer. No formal proof is necessary. \textit{(Please write up your solution
    to this problem in your written assignment submission, since we want to see
    your justification in ad- dition to your answer.)}
\end{enumerate}
\begin{shaded}
  Write your answer here.
\end{shaded}

Generally speaking, if you ever find yourself in possession of a strange
set-theoretic expression involving the set combination operations $\cap$,
$\cup$, $-$, or $\Delta$, you can use the above technique to get a slightly
better handle at what you're looking in fact. In fact, many rules about how
these set-theoretic operators work follow directly from propositional logic! \\

That result in part (vi) is an interesting one. You may want to keep it in mind
for later in the quarter. \smiley{}

\pagebreak

\section{Executable Logic}
\begin{shaded}
  Submit your edited $\mathsf{ExecutableLogic.cpp}$ file through Gradescope.
\end{shaded}

\section{First-Order Negations}
\begin{shaded}
  Submit your edited $\mathsf{FirstOrderNegations.fol}$ file through Gradescope.
\end{shaded}

\section{This, But Not That}
\begin{shaded}
  Submit your five edited $\mathsf{.people}$ files through Gradescope.
\end{shaded}

\section{Translating into Logic}
\begin{shaded}
  Submit your edited $\mathsf{TranslatingIntoLogic.fol}$ file through
  Gradescope.
\end{shaded}

\pagebreak

\section{Hereditary Sets}

Let's begin with a fun little definition:

\begin{center}
  A set $S$ is called a \emph{hereditary set} if every $x \in S$ is also a
  hereditary set.
\end{center}

This definition might seem strange because it's self-referential -- it defines
the hereditary sets in terms of other hereditary sets!  However, it turns out
that this is a perfectly reasonable definition to work with, and in this problem
you'll explore some properties of hereditary sets.

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

  \item Given the self-referential nature of the definition of hereditary sets,
    it's not even clear that hereditary sets even exist at all!  As a starting
    point, prove that there is at least one hereditary set.

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

\end{enumerate}

\annotate{When confronted with a new definition, it never hurts to try out some
  examples. So pick a set, any set, and then apply the above definition to see
  whether it's hereditary. If so, great! You're done. If not, make sure you can
  explain why not. Then, based on what you found, pick another set and repeat
  this process. After a few iterations, you will likely converge on an answer.}
  \\

\annotate{This strategy, by the way, is a \emph{great} way to get a handle on
  any new definition.}

\begin{enumerate}[resume*]

  \item Prove that if $H$ is a hereditary set, then $\wp(H)$ is also a
    hereditary set.

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

\end{enumerate}

\annotate{The hardest part of this problem is determining how to set this proof
  up in a way that's precise and rigorous. Here are some things to think about:
  \begin{itemize}
    \item What is the general procedure for proving an implication? What's the
      antecedent here? What's the consequent?
    \item Consider the statement ``every $x \in S$ is also a hereditary set.''
      Is that an existentially-quantified statement, a universally-quantified
      statement, both, or neither? Based on what you know about how to prove
      existentially-quantified and universally-quantified statements, what
      should you do to prove this statement?
  \end{itemize}
  After you've written up a draft of your proofs, take a minute to read over
  them and apply the criteria from the Proofwriting Checklist. Here are a few
  specific things to watch out for:
  \begin{itemize}
    \item Although we've just introduced first-order logic as a tool for
      formalizing definitions and reasoning about mathematical structures, the
      convention is to \emph{not} use first-order logic notation (connectives,
      quantifiers, etc.) in written proofs. In a sense, you can think of
      first-order logic as the stage crew in the theater piece that is a proof –
      it works behind the scenes to make everything come together, but it's not
      supposed to be in front of the audience. Make sure that you're still
      writing in complete sentences, that you’re not using symbols like
      $\forall$ or $\rightarrow$ in place of words like ``for any'' or
      ``therefore,'' etc.
    \item A common mistake we see people make when they're just getting started
      is to restate definitions in the abstract in the middle of a proof. For
      example, we commonly see people say something like ``since $A \subseteq
      B$, we know that every element of $A$ is an element of $B$.'' When you're
      writing a proof, you can assume that whoever is reading your proof is
      familiar with the definitions of relevant terms, so statements like the
      one here that just restate a definition aren't necessary. Instead of
      restating definitions, try to apply those definitions. A better sentence
      would be something to the effect of ``Since $x \in A$ and $A \subseteq B$,
      we see $that x \in B$,'' which uses the definition to conclude something
      about a specific variable rather than just restating the definition. See
      the Guide to Proofs on Set Theory for more details.
  \end{itemize}}


Hereditary sets are used in \emph{foundational mathematics}, the study of how to
assemble all mathematical structures from simple structures. If you'd like to
learn more about them, take Math 161!

\pagebreak

\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{$(P)$: Statement $(P)$ is false.}
\end{center}
If statement $(P)$ is true, then by its own admission statement $(P)$ must be
false -- a contradiction!  On the other hand, suppose that statement $(P)$ is
false. Then the statement ``statement $(P)$ is false'' is false, meaning that
statement $(P)$ 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}

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

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

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

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

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.

\end{enumerate}

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

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

\pagebreak

\section{Tournament Champions, Part Two}

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

On Problem Set One, you explored \emph{tournaments}, contests between $n \ge 0$
players. You in particular learned about \emph{tournament champions}, players
who satisfy a particular set of criteria. This problem picks up where we left
off.  We recommend that you look back over Problem Set One for the definitions
that you saw there and to review what results about tournaments you've already
proved. \\

Let's begin by introducing the notion of a \emph{loop} in a tournament. A loop
in a tournament $T$ is a series of $n \ge 3$ different players $p_1, p_2, \dots,
p_n$  such that player $p_1$ won against player $p_2$, player $p_2$ won against
player $p_3, \dots$, and, finally, player $p_n$  won against player $p_1$. The
\emph{length} of a loop is the number of players in the loop.

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

  \item Give an example of a loop of length five in the tournament shown above.
    No justification is necessary.

\end{enumerate}

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

\begin{enumerate}[resume*]

  \item Prove that if a tournament has any loops at all, then it must have a
    loop of length three.

\end{enumerate}

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

\annotate{This would be a great spot to draw pictures and try out examples. Try
  drawing tournaments with different numbers of players and loops of different
  sizes and see if you notice anything.} //

\annotate{As a hint, use a \emph{proof by extreme case} like what you did in
  Problem Set One. Focus on the smallest loop in the tournament -- what can you
  say about it?}

Given any tournament $T$, if you select a collection of players from $T$, you
can form a \emph{subtournament} consisting of just those players and the games
they've played against one another.

\begin{enumerate}[resume*]

  \item Let $T$ be an arbitrary tournament. Prove that if $p$ is a player in $T$
    who lost at least one game, then at least one of the players who won against
    $p$ is a tournament champion.

\end{enumerate}

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

\annotate{Before writing this proof, take a minute to articulate what it is that
  you need to do here. This statement has both universal and existential
  components. How do you prove a universally-quantified statement? How do you
  prove an existentially-quantified statement?} \\

\annotate{As a hint, split $T$ into three groups: a subtournament of players who
  won against $p$, a subtournament of players who lost to $p$, and player $p$
  himself. This is sometimes called the \emph{bowtie decomposition} of a
  tournament. (Curious where the name comes from? Draw pictures!)}

\begin{enumerate}[resume*]

  \item Prove that there are no tournaments with exactly two champions.

\end{enumerate}

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

\pagebreak

\section*{Optional Fun Problem: Insufficient Connectives
(Extra Credit)}

Every propositional logic formula could be written in terms of just
$\rightarrow$ and $\perp$. However, you \textit{cannot} express every possible
propositional logic formula using just the $\leftrightarrow$ and $\perp$
connectives. Prove why not.

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

\end{document}
