\documentclass[12pt,letterpaper]{article}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amscd}
\usepackage{enumerate}
\usepackage{fancyhdr}
\usepackage{mathrsfs}
\usepackage{bbm}
\usepackage{framed}
\usepackage{mdframed}
\usepackage{cancel}
\usepackage{mathtools}
\usepackage{verbatim}
\usepackage[letterpaper,voffset=-.5in,bmargin=3cm,footskip=1cm]{geometry}
\setlength{\parindent}{0.0in}
\setlength{\parskip}{0.1in}
\allowdisplaybreaks
\headheight 15pt
\headsep 10pt
\newcommand\N{\mathbb N}
\newcommand\Z{\mathbb Z}
\newcommand\R{\mathbb R}
\newcommand\Q{\mathbb Q}
\newcommand\lcm{\operatorname{lcm}}
\newcommand\setbuilder[2]{\ensuremath{\left\{#1\;\middle|\;#2\right\}}}
\newcommand\E{\operatorname{E}}
\newcommand\V{\operatorname{V}}
\newcommand\Pow{\ensuremath{\operatorname{\mathcal{P}}}}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand\hint[1]{\textbf{Hint}: #1}
\newcommand\note[1]{\textbf{Note}: #1}
\newcounter{enum22i}
\newenvironment{22enumerate}{\begin{enumerate}[a.]\itemsep0em\setcounter{enumi}{\value{enum22i}}}{\setcounter{enum22i}{\value{enumi}}\end{enumerate}}
\newenvironment{22itemize}{\begin{itemize}\itemsep0em}{\end{itemize}}
\fancypagestyle{firstpagestyle} {
\renewcommand{\headrulewidth}{0pt}
\lhead{\textbf{CSCI 0220}}
\chead{\textbf{Discrete Structures and Probability}}
\rhead{M. Littman}
}
\fancypagestyle{fancyplain} {
\renewcommand{\headrulewidth}{0pt}
\lhead{\textbf{CSCI 0220}}
\chead{Homework 2}
\rhead{\textit{Wednesday, February 12}}
}
\pagestyle{fancyplain}
\begin{document}
\thispagestyle{firstpagestyle}
\begin{center}
{\huge \textbf{Homework 2}}
{\large \textit{Due: Wednesday, February 12}}
\end{center}
All homeworks are due at 12:55 PM on Gradescope.
Please do not include any identifying information about yourself in the handin, including your Banner ID.
Be sure to fully explain your reasoning and show all work for full credit.
\subsection*{Problem 1}
{
\nopagebreak
{\setcounter{enum22i}{0}
\begin{22enumerate}
\item
Prove or disprove that a relation that is reflexive and symmetric is necessarily
transitive.
\item
Prove or disprove that a relation that is reflexive and transitive is necessarily
symmetric.
\item
Prove or disprove that a relation that is symmetric and transitive is necessarily
reflexive.
\end{22enumerate}
}
}
\subsection*{Problem 2}
{
\nopagebreak
{\setcounter{enum22i}{0}
Determine whether or not each of the following relations is an equivalence
relation. Be sure to justify your answers.
\begin{22enumerate}
\item The relation $R$ on $\Z$ defined by the set of ordered pairs:
\[\setbuilder{(a,b)}{\quad |a-b| \leq 2 }.\]
\item The relation on $\R^2$ defined by the set of ordered pairs:
\[\setbuilder{(a,b)}{
||a|| = ||b|| },\] where $||a||$ is the distance from $a$ to the origin in $\R^2$
($\R^2$ is the set of ordered pairs $(x, y)$ where $x, y \in \R$, also known as the set of points in the plane, and the distance from a point $(x, y)$ to the origin is defined as $\sqrt{x^2 + y^2}$.)
In addition to your proof, answer the following:
given a fixed point $p\ \in \R^2$, the
collection of all points related to $p$ gives what
familiar geometric object?
That is, what is $\{x | x\; R\; p\}$?
\item
Let $S = \{a, b, c, d\}.$
Let $R$ be the relation on $S$ with the graph:
\[\{(a, a), (b, b), (c, c), (a, b), (b, c), (a, c), (b, a), (c, b), (c, a)\}\].
\end{22enumerate}
}
}
\subsection*{Problem 3}
{
\nopagebreak
{\setcounter{enum22i}{0}
Determine whether each of the following statements is true or false, and explain why.
\begin{22enumerate}
\item The powerset of the empty set has the empty set as a member.
\item The empty set is an element of every set.
\item The empty set is a subset of any set that does not have the empty set as a member.
\item Any set that has the empty set as a member must be the empty set.
\item The set containing the set containing the set containing the empty set has a cardinality of zero (here, $A$ contains $B$ means $B \in A$).
\item The set of all empty sets is the same as the powerset of the empty set.
\end{22enumerate}
}
}
\subsection*{Problem 4}
{
\nopagebreak
{\setcounter{enum22i}{0}
\begin{22enumerate}
\item \begin{enumerate}[i.]
\item
Find all relations from $\{0,1\}$ to $\{1\}$.
\item
Find all relations from $\{1\}$ to $\{0,1\}$.
\end{enumerate}
\item \begin{enumerate}[i.]
\item
Find all functions from $\{0,1\}$ to $\{1\}$.
\item
Find all functions from $\{1\}$ to $\{0,1\}$.
\end{enumerate}
\item
Let $S=\{0,1\}, \; T = \{t | t \subseteq S \times S\}$, and $R$ be the set of all possible functions from $S$ to $S$.
\begin{enumerate}[i.]
\item Can an injection from $T$ to $R$ exist?
If so, give one such injection and prove that this mapping is indeed
injective. If not, prove why such a mapping cannot exist.
\item Can a surjection from $T$ to $R$ exist?
If so, give one such surjection and prove that this mapping is indeed
surjective. If not, prove why such a mapping cannot exist.
\item Can a bijection from $T$ to $R$ exist? If so, why?
If not, why not?
\end{enumerate}
\end{22enumerate}
}
}
\subsection*{Problem 5}
{
\nopagebreak
{\setcounter{enum22i}{0}
Drayton Martin is the Vice President of Brand Stewardship at Dunkin' Donuts
\footnote{https://www.linkedin.com/in/drayton-martin-a616413}.
She is responsible for deciding which stores carry which flavors.
Consider the nonempty set of flavors $F = \{f_1,f_2, \ldots, f_n\}$
that a store can carry.
Drayton can tell a store to carry any subset of these flavors (even the empty set).
She decides to assign each of these subsets to exactly one store.
Prove that the number of stores that sell an even number of flavors is equal to
the number of stores that sell an odd number of flavors. Prove this by constructing
a bijection between the two set of stores.
Be sure to prove that your function is in fact bijective.
}
}
\end{document}