% % 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. % \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} \lhead{Your Name(s) Here} \chead{Problem Set \#2} \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{\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}}} % end MZ \begin{document} \maketitle No checkpoint problems! Enjoy your Martin Luther King Jr Day holiday. \pagebreak \section{Propositional Completeness} In lecture, we covered the seven propositional connectives, which for convenience we've listed below: $$ \neg \hphantom{--} \land \hphantom{--} \neg \hphantom{--} \rightarrow \hphantom{--} \leftrightarrow \hphantom{--} \top \hphantom{--} \perp $$ We settled on this set of connectives because they're convenient and expressive. However, it turns out that we could get away with fewer connectives than this. \begin{enumerate}[label*=\roman*.,ref=\roman*] \item Show how to rewrite the expressions $\perp$, $p \rightarrow q$, and $p \leftrightarrow q$ purely using the remaining four connectives ($\land$, $\lor$, $\neg$, and $\top$), along with the variables $p$ and $q$. This means that those four propositional connectives are \emph{sufficient} -- the other three connectives can be rewritten purely in terms of them. \begin{shaded} Write your answer here. \end{shaded} \item There's even some redundancy in the four connectives you've used so far! Show how to rewrite the expression $p \lor q$ without using any connectives besides $\land$, $\neg$, and $\top$. This shows that those three connectives are actually all you need to cover all possible formulas. \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} We can push this further. You can rewrite any propositional formula using just the $\rightarrow$ and $\perp$ connectives. \begin{enumerate}[resume*] \item Find a formula that's equivalent to $\top$ that doesn`t use any connectives besides $\rightarrow$ and $\perp$. \begin{shaded} Write your answer here. \end{shaded} \item Find a formula that's equivalent to $\neg p $ and uses only the variable $p$ and doesn`t use any connectives besides $\rightarrow$ and $\perp$. \begin{shaded} Write your answer here. \end{shaded} \item Find a formula that's equivalent to $p \land q$ that uses only the variables $p$ and $q$ and doesn’t use any connectives besides $\rightarrow$ and $\perp$. \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} \annotate{As a hint, what happens if you negate an implication?} \\ To recap: given the $\rightarrow$ and $\perp$ connectives, you can express $\land$, $\neg$, and $\top$. From $\land$, $\neg$, and $\top$ you can get $\land$, $\lor$, $\neg$, and $\top$. And from those four connectives, you can get back the original seven. Overall, any propositional formula can be expressed purely in terms of $\rightarrow$ and $\perp$. Nifty! \pagebreak \section{Designing Propositional Formulas} Federal appeals courts in the United States typically assign three judges to hear each case. Each judge decides whether to \textit{affirm} the decision (uphold the lower court's ruling) or \textit{reverse} the decision (invalidate the lower court's ruling). The court as a whole then decides whether to affirm or reverse by going with the majority of the judges, so if two vote to affirm and one votes to reverse, the court decides to affirm. \\ Let $a$, $b$, and $c$ be propositional logic variables representing the votes of each of the judges in a particular case. Each variable is true if the judge voted to affirm, and is false if the judge voted to reverse. \begin{enumerate}[label*=\roman*.,ref=\roman*] \item Write a truth table that shows the court's overall decision as a function of $a$, $b$, and $c$. The output should be ``true'' if a majority of the judges vote to affirm, and should be ``false'' if a majority of the judges vote to reverse. \begin{shaded} Write your truth table here. % Tip: Use http://www.tablesgenerator.com/ \end{shaded} \item Design a propositional logic formula that has the above truth table. For full credit, your formula should use a total of four connectives. ("total of four" means that, for example, if you use 6 copies of $\land$ and one $\lor$ that would count as 7 total connectives, which would be too many for this problem) \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} Imagine a room with three light switches that all control the same light. If the light is on and any switch is flipped, the light turns off, and if the light is off and any switch is flipped, the light turns on. Additionally, the light is on when all three switches are in the ``on'' position. Let $a$, $b$, and $c$ be propositional variables that represent whether the first, second, and third light switches are in the ``on'' position, respectively. \begin{enumerate}[resume*] \item Write a truth table that shows whether the light should be turned on as a function of $a$, $b$, and $c$. An output of ``true'' means that the light should be turned on, and an output of ``false'' means that the light should be turned off. \begin{shaded} Write your truth table here. % Tip: Use http://www.tablesgenerator.com/ \end{shaded} \item Design a propositional logic formula that has the above truth table. For full credit, your formula should use a total of two connectives (same definition of ``total'' as above). \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} \annotate{Which connectives have truth values that flip when one of their inputs change?} \\ \pagebreak \section{Symmetric Differences} The set symmetric difference operator $\Delta$ is perhaps the most unusual set combination operator. It's not as commonly used as the others, and its behavior can be a bit surprising. Fortunately, now that we have propositional logic at our disposal, we can get a slightly better handle on how it works. \begin{enumerate}[label*=\roman*.,ref=\roman*] \item Imagine you have two sets $A$ and $B$. Fill in the last column of the following truth table. \begin{table}[h] \centering \begin{shaded} \begin{tabular}{c|c|c} $x \in A$ & $x \in B$ & $x \in A \Delta B$ \\ \hline F & F & \\ F & T & \\ T & F & \\ T & T & \end{tabular} \end{shaded} \end{table} \end{enumerate} \annotate{Don't be weirded out by the fact that the inputs to the truth table have the form $x \in A$ and $x \in B$ rather than single letters like $p$ and $q$. Remember -- the statement ``$x \in A$'' is a proposition: it's either true or false!} \begin{enumerate}[resume*] \item Based on your answer to part (i) of this problem, fill in the following blank with a \textbf{logic formula} (reminder: a logic formula can not include set operations like $\cap$ unless otherwise specified, so here you only have $\in$). Aim to get the simplest formula you can. \begin{shaded} $$ x \in A \Delta B \text{ happens precisely when } \rule{5cm}{0.15mm} % Replace with your answer $$ \end{shaded} \end{enumerate} \annotate{That truth table should look really familiar. Use that to guide your search.} \begin{enumerate}[resume*] \item Generalize your answer to part (ii) by filling in the following blank. For full credit, see if you can find a \textbf{logic formula} that uses exactly \textit{two} connectives. \begin{shaded} $$ x \in (A \Delta B) \Delta C \text{ happens precisely when } \rule{5cm}{0.15mm} % Replace with your answer $$ \end{shaded} \end{enumerate} \annotate{If you've done this correctly, you should have a slight sense of d\'ej\`a vu.} \begin{enumerate}[resume*] \item Using your answer to part (iii) as a starting point, simplify the expression $(A \Delta B) \Delta B$. Briefly justify your answer. No formal proof is necessary. \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} 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 (iv) is an interesting one. You may want to keep it in mind for later in the quarter. \smiley \pagebreak \section{First-Order Negations} For each of the first-order logic formulas below, find a first-order logic formula that is the negation of the original statement. Your final formula must not have any negations in it except for direct negations of predicates. For example, the negation of the formula $\forall x.\ (P(x) \rightarrow \exists y.\ (Q(x) \land R(y)))$ could be found by pushing the negation in from the outside inward as follows: \begin{align*} &\neg (\forall x.\ (P(x) \rightarrow \exists y.\ (Q(x) \land R(y)))) \\ &\exists x.\ \neg(P(x) \rightarrow \exists y.\ (Q(x) \land R(y))) \\ &\exists x.\ (P(x) \land \neg\exists y.\ (Q(x) \land R(y))) \\ &\exists x.\ (P(x) \land \forall y.\ \neg(Q(x) \land R(y))) \\ &\exists x.\ (P(x) \land \forall y.\ (Q(x) \rightarrow \neg R(y))) \end{align*} Show every step of the process of pushing the negation into the formula (along the lines of what is done above), and \textit{please preserve the indentation from the original formula} as you go. You don't need to formally prove that your negations are correct. \\ We \emph{strongly} recommend reading over the Guide to Negations before starting this problem. \begin{enumerate}[label*=\roman*.,ref=\roman*] \item $\begin{aligned}[t] &\exists p.\ (\textit{Problem}(p) \land \\ &\qquad \forall g.\ (\textit{Program}(g) \rightarrow \neg \textit{Solves}(g, p)) \\ &) \end{aligned}$ \begin{shaded} Write your answer here. \end{shaded} \item $\begin{aligned}[t] &\forall x \in \R.\ \forall y \in \R.\ (x < y \rightarrow \\ &\qquad \exists q \in \Q.\ (x < q \land q < y) \\ &) \end{aligned}$ \begin{shaded} Write your answer here. \end{shaded} \item $(\forall x.\ \forall y.\ \forall z.\ (R(x, y) \land R(y, z) \rightarrow R(x, z))) \rightarrow (\forall x.\ \forall y.\ \forall z.\ (R(y, x) \land R(z, y) \rightarrow R(z, x)))$ \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} \annotate{Be careful -- make sure you understand how that formula is parenthesized before you try negating it.} \begin{enumerate}[resume*] \item $\begin{aligned}[t] &\forall x.\ \exists S.\ (\textit{Set}(S) \land \\ &\qquad \forall z.\ (z \in S \leftrightarrow z = x) \\ &) \end{aligned}$ \begin{shaded} Write your answer here. \end{shaded} \item $\begin{aligned}[t] &\forall k.\ (\textit{SixClique}(k) \rightarrow \\ &\qquad \exists t.\ (\textit{Triangle}(t, k)\ \land \\ &\qquad\qquad (\forall e.\ (\textit{Edge}(e, t) \rightarrow \textit{Red}(e)) \lor \forall e.\ (\textit{Edge}(e, t) \rightarrow Blue(e))) \\ &\qquad) \\ &) \end{aligned}$ \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} \pagebreak \section{Vacuous Truths} A statement is called \textbf{\textit{vacuously true}} if either \begin{itemize} \item it's an implication of the form $P \rightarrow Q$ where $P$ is false, \item it's a universally-quantifed implication $\forall x.\ (P(x) \rightarrow Q(x))$ where $P(x)$ is never true, or \item it's a universally-quantifed implication $\forall x \in S.\ Q(x)$ where $S$ is the empty set. \end{itemize} These statements are true \textit{by definition}. In the first case, the truth table for the $\rightarrow$ connective says the implication is true when the antecedent is false, and in the second and third cases we just define these sorts of statements to be true. \\ You might be wondering why exactly this is the case. \begin{enumerate}[label*=\roman*.,ref=\roman*] \item Negate the propositional formula $P \rightarrow Q$ and push the negations as deep as possible. Now, look at the resulting formula. Explain why when $P \rightarrow Q$ is vacuously true, its negation is false. \begin{shaded} Write your answer here. \end{shaded} \item Negate the first-order formula $\forall x.\ (P(x) \rightarrow Q(x))$ and push the negations as deep as possible. Now, look at the resulting formula. Explain why if the original formula is vacuously true, then its negation is false. \begin{shaded} Write your answer here. \end{shaded} \item Negate the first-order formula $\forall x \in S.\ Q(x)$ and push the negations as deep as possible. Now, look at the resulting formula. Explain why if the original formula is vacuously true, then its negation is false. \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} Your answers to parts (i), (ii), and (iii) of this problem give another justification for vacuous truths. The three classes of statements given above have false negations in the indicated cases, and therefore to keep everything consistent we choose to define them as (vacuously) true. (Generally speaking, consistency is considered a virtue in mathematics. We're making up the rules, after all, and it's a lot easier when we pick them to be as simple as possible!) \pagebreak \section{Translating into Logic} In each of the following, write a statement in first-order logic that expresses the indicated sentence. Your statement may use any first-order construct (equality, connectives, quantifiers, etc.), but you \textbf{\textit{must}} only use the predicates, functions, and constants provided. You do not need to provide the simplest formula possible, though we'd appreciate it if you made an effort to do so. \smiley \\ We \emph{highly} recommend reading the Guide to First-Order Logic Translations before starting this problem. \begin{enumerate}[label*=\roman*.,ref=\roman*] \item Given the predicate \qquad $\textit{Natural}(x)$, which states that $x$ is an natural number and the functions \qquad $x + y$, which represents the sum of $x$ and $y$, and \qquad $x \cdot y$, which represents the product of $x$ and $y$ write a statement in first-order logic that says ``for any $n \in \N$, $n$ is even if and only if $n^2$ is even.'' \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} \annotate{Try translating this statement assuming you have a predicate Even(x). Then, rewrite your solution without using Even(x). Numbers aren't a part of first-order logic, so you can't use the number 2 in your solution.} \begin{enumerate}[resume*] \item Given the predicates \qquad $\textit{Person}(p)$, which states that $p$ is a person; \qquad $\textit{Kitten}(k)$, which states that $k$ is a kitten; and \qquad $\textit{HasPet}(o, p)$, which states that $o$ has $p$ as a pet, write a statement in first-order logic that says ``someone has exactly two pet kittens and no other pets.'' \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} \annotate{Make sure your formula requires that the person have \emph{exactly} two pet kittens; look at the lecture example of uniqueness as a starting point. Good questions to ask -- is your formula false if everyone has exactly one pet kitten? Is it false if everyone has exactly three pet kittens?} \begin{enumerate}[resume*] \item The \emph{axiom of pairing} is the following statement: given any two distinct objects $x$ and $y$, there's a set containing $x$ and $y$ and nothing else. Given the predicates \qquad $x \in y$, which states that $x$ is an element of $y$, and \qquad $\textit{Set}(S)$, which states that $S$ is a set, write a statement in first-order logic that expresses the axiom of pairing. \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} \annotate{What does the Guide to Logic Translations say about translating statements about sets?} \begin{enumerate}[resume*] \item Given the predicates \qquad $x \in y$, which states that $x$ is an element of $y$, and \qquad $\textit{Set}(S)$, which states that $S$ is a set, write a statement in first-order logic that says ``every set has a power set.'' \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} \annotate{As a warm-up, solve this problem assuming you have a predicate $X \subseteq Y$ that says that $X$ is a subset of $Y$. Once you have that working, see if you can solve the full version of this problem.} \begin{enumerate}[resume] \item Given the predicates \qquad $\textit{Lady}(x)$, which states that $x$ is a lady; \qquad $\textit{Glitters}(x)$, which states that $x$ glitters; \qquad $\textit{SureIsGold}(x, y)$, which states that $x$ is sure that $y$ is gold; \qquad $\textit{Buying}(x, y)$, which states that $x$ buys $y$; and \qquad $\textit{StairwayToHeaven}(x)$, which states that $x$ is a Stairway to Heaven; write a statement in first-order logic that says ``there's a lady who's sure all that glitters is gold, and she's buying a Stairway to Heaven.'' \begin{shaded} Write your answer here. \end{shaded} \end{enumerate} \pagebreak \section{Hereditary Sets} Let's begin with a fun little definition: \begin{center} A set $S$ is called a \emph{hereditary set} if all its elements are hereditary sets. \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 these types of 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{Try writing out some sample sets and see what you find. You'll quickly get a better handle on how the definition behaves, which will help guide your search.} \begin{enumerate}[resume*] \item Prove that if $S$ is a hereditary set, then $\wp(S)$ is also a hereditary set. \begin{shaded} Provide a proof here. \end{shaded} \end{enumerate} \annotate{ 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 If you want to prove in part (ii) that a set T is a hereditary set, you need to prove the statement ``every element of T is a hereditary set.'' That's a universally-quantifed statement. If you're proving it via a direct proof, you'll probably need to pick some arbitrary element $x \in T$, then prove that x is a hereditary set by making specific claims about the variable x. Read over your proof and make sure that (1) you've introduced a new variable to refer to some arbitrarily-chosen element of T and that (2) you're making specific claims about the variable x, rather than talking in general about how elements of T behave. You may need to introduce multiple variables in the course of your proofs. \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. \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. \end{itemize} } Hereditary sets are used in \textit{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{The Star-Drawing Saga, Part Three} On Problem Set One, you saw the Simple Star Criterion, which pins down what has to happen in order for a $p$-point star with a step size of $s$ to be a simple star: \begin{center} \emph{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 an integer $t$ such that $n \equiv_p s \cdot t$. \end{center} This criterion is a little bit tricky to work with because of the universal quantifier at the front (``for every natural number $n$.'') It turns out that there's an easier way to characterize simple stars. \\ Take a minute and try drawing out the \textit{non}-simple stars \{6 / 2\}, \{8 / 2\}, \{10 / 4\}, and \{12 / 3\}. Because those aren't simple stars, the star you draw doesn't end up passing through all of the points on the perimeter. Notice that, specifically, \textit{none} of those stars end up passing through point 1. Formally speaking, if we have the star \{$p$ / $s$\}, then the star passes through point 1 on the perimeter precisely if there's an integer $t$ such that $1 \equiv_p s \cdot t$. \begin{enumerate}[resume*] \item Let $p$ and $s$ be natural numbers where $p > 0$. Using the simple star criterion, prove that the star \{$p$ / $s$\} is simple if and only if there is an integer $t$ where $1 \equiv_p s \cdot t$. \begin{shaded} Provide a proof here. \end{shaded} \end{enumerate} \annotate{Reminder: Q: how do you set up a proof of a biconditional statement? A: write two proofs, one ``forwards'' and one ``backwards''). And a reminder from the previous problem -- \emph{don't use quantifiers or connectives in proofs}. The rules for writing proofs are the same now as they were last week.} \\ \pagebreak \section{Tournament Champions} Here's one more problem to help you practice your proofwriting. It's a classic CS103 problem, and we hope that you enjoy it! \\ \begin{wrapfigure}{l}{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 drawing arrows between pairs of players to indicate who won each game. For example, in the tournament to the left, player $A$ beat player $E$, but lost to players $B$, $C$, and $D$. \\ A \emph{tournament champion} is a player in a tournament who, for each other player, either won her game against that player, or won a game against a player who in turn won his game against that player (or both). For example, in the graph on the left, players $B$, $C$, and $E$ are tournament champions. However, player $D$ is \emph{not} a tournament champion, because he neither beat player $C$, nor beat anyone who in turn beat player $C$. Although player $D$ won against player $E$, who in turn won against player $B$, who then won against player $C$, under our definition player $D$ is \emph{not} a tournament champion. \textit{(Make sure you understand why!)} \\ \begin{enumerate}[label*=\roman*.,ref=\roman*] \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$. \begin{shaded} Provide a proof here. \end{shaded} \end{enumerate} \annotate{This problem is a lot easier to solve if you draw the right picture. Something to think about: what happens if a player $p$ \emph{isn't} a champion in a tournament? What would that mean about player $p$? And finally, be careful not to make broad claims about tournaments or tournament structures without first proving them!} \\ \annotate{Once you've figured out the key insight and are writing up your answer, \emph{be precise with your terminology}. For example, be careful about saying something like ``player X beat player Y indirectly,'' because reasonable people can disagree about what ``indirectly'' means. For example, in the above tournament, player D beats player E, who beats player B, who beats player C, who beats player A. In one sense, that means that player D beat player A indirectly. But D isn't a tournament champion because that ``indirectly'' involves going through too many other players. If you want to talk about direct versus indirect wins, that's fine, but be sure to precisely define what you mean! Similarly, be careful about talking about different sets of players that might have some overlap. For example, ``the set of people that player C won a game against'' and ``the set of players that those people won games against'' aren't disjoint: player C beat player E, so E is in the first set, and player C also beat player A, who in turn beat player E, so player E is also in the second set.} \\ A corollary of the result you proved in part (i) is that every tournament with at least one player must have at least one tournament champion -- you can always pick someone who won the most games or is tied for winning the most games. However, note that you can be a champion without necessarily winning the most games -- for example, player $E$ in the above example tournament is a champion, though player $E$ only won a single game! \\ \begin{enumerate}[resume*] \item Prove that for any $n \geq 3$, there's a tournament with exactly $n$ players and exactly three champions. \begin{shaded} Provide a proof here. \end{shaded} \end{enumerate} \annotate{There's a universal and an existential component to this theorem. How do you prove existential statements?} \section*{Optional Fun Problem: Insufficient Connectives (Extra Credit)} Every propositional logic formula could be written in terms of just $\rightarrow$ and $\perp$. However, you 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}