\documentclass{2800hw}
\usepackage{amsmath,amssymb,latexsym}
\usepackage{utf8}
\usepackage{url}
\usepackage{enumitem}
\newcommand{\TODO}[1][fix]{\textbf{[TODO: #1]}}
\topic{Logic and Probability}
\homework{2}
\begin{document}
\maketitle
\begin{exercises}
\item
Let $F(x, y)$ be the statement ``$x$ can fool $y$,'' where the domain consists of all people in the world. Use quantifiers to express each of these statements. For once, use {\em only} symbolic (i.e. non-English) notation in your answers. You may use connectives such as $\vee$, $\wedge$ etc as required. Do not create new predicates (i.e. don't write something like: {\em Define $G(x, y) =$ ``$x$ cannot fool $y$''}). You do not need to specify the overall domain ($x \in People$) anywhere.
\begin{enumerate}
\item Everybody can fool Fred.
\item Evelyn can fool everybody.
\item Everybody can fool somebody.
\item There is no one who can fool everybody.
\item Everyone can be fooled by somebody.
\item No one can fool both Fred and Jerry.
\item Nancy can fool exactly two people.
\end{enumerate}
\item
Negate each of the expressions you constructed in the previous exercise, distributing the negation as far inwards as possible. You don't need to show the steps of the derivation. Translate your negated expressions to simple English (do not simply prefix ``It is not the case that \dots''). You may use De Morgan's Laws without proof:
\[
\neg (P \wedge Q \wedge \dots) \iff (\neg P) \vee (\neg Q) \vee \dots
\]
\[
\neg (P \vee Q \vee \dots) \iff (\neg P) \wedge (\neg Q) \wedge \dots
\]
{\bf {\em Note:}} {\em You will get full credit for doing the negation correctly, even if your original expression is slightly incorrect. Translating the negated expression to English and comparing with the original is a good sanity check, which is why we ask you to do it.}
\item Prove from first principles (i.e. Kolmogorov's axioms) or give a counterexample for each of the following. You may use any results from set theory without proof, as long as they are true.
\begin{enumerate}[label=\alph*)]
\item $P(A \cup B) \leq P(A) + P(B)$, where $A$ and $B$ are any two events in a probability space.
\item If $A \subseteq B$ but $A \neq B$ then $P(A) < P(B)$.
\item If $A_1, A_2, \dots, A_n$ are mutually exclusive events and $\bigcup_i A_i = S$ (the entire sample space), then for some $i$, $P(A_i) \geq 1/n$.
\item If $A \neq \emptyset$, then $P(A) \neq 0$.
\item For any $x \in S$, $P(\{x\}) = 1/|S|$.
\end{enumerate}
\end{exercises}
\end{document}