\documentclass{2800hw}
\usepackage{amsmath,amssymb,latexsym}
\usepackage{verbatim}
\usepackage{utf8}

\begin{document}

\topic{Functions}
\homework{4}

\maketitle

\begin{exercises}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item
State the negation of each of these statements in simple English. (Do not
simply prepend a phrase like ``It is not the case that...'').
\begin{enumerate}
\item All dogs have fleas.
\item There is a horse that can add.
\item Every koala can climb.
\item There exists a pig that can swim and catch fish.
\item In every country, there is a city by a river.
\item Old MacDonald had a farm, and on that farm he had a cow.
\item Every person in this class understands discrete mathematics.
\item Some students in this class do not like discrete mathematics.
\item In every mathematics class there is some student who falls asleep during
lectures.
\item There is a student in this class that can beat every other student in the
class at chess.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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.
\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
\begin{enumerate}
\item % 1a
A function $f : A \rightarrow A$ is called involutive if for all $x \in A$, $f(f(x)) = x$.
Prove or disprove: \begin{enumerate}
\item if $f$ is involutive, then it is injective.
\item if $f$ is involutive, then it is surjective.
\end{enumerate}

\item % 1b
A function $f : A \rightarrow A$ is called idempotent if for all $x \in A$, $f(f(x)) =
f(x)$.  Prove or disprove:
\begin{enumerate}
\item if $f$ is idempotent, then it is injective.
\item if $f$ is idempotent, then it is surjective.
\end{enumerate}

\item % 1c
If $f : B \rightarrow C$ and $g : A \rightarrow B$ are functions, then $f \circ g$ is the function
from $A$ to $C$ defined by: $(f \circ g) : x ↦ f(g(x))$.  Prove or disprove:
if $f$ and $f \circ g$ are one-to-one, then $g$ is one-to-one.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item % 2
In the first few homeworks, we asserted various facts about sets.  We will now
prove two of them.  Given two sets $A \subseteq S$ and $B \subseteq S$, show
that
\begin{enumerate}
\item $A \cup B = (A \setminus B) \cup (A \cap B) \cup (B \setminus A)$.
\item $(A \setminus B) \cap (A \cap B) = \emptyset$.
\end{enumerate}

Note that the formal definition of equality for sets is that $A = B$ if $A
\subseteq B$ and $B \subseteq A$, and the formal definition of subset is $A
\subseteq B$ if for all $x \in A$, $x \in B$.  Definitions for $\cup$, $\cap$,
$\setminus$ and $\emptyset$ are on the lecture slides.

\end{exercises}

\end{document}
