\documentclass[letterpaper,11pt]{article} % Tweaked 3/30/22 to fit page

\usepackage{amsfonts,amssymb,amsmath,amsthm,txfonts,pxfonts,mathrsfs,fullpage,enumitem}
\usepackage{xcolor}

\pagestyle{empty}
\begin{document} 

\begin{center}\textbf{Problem Set 8 \hspace{.7in} Foundations \hspace{.7in} Due 4/4/22} \end{center}

\noindent Four of these problems will be graded (my choice, not yours!), with each problem worth 5 points.  Clear and complete justification is required for full credit.  You are welcome to discuss these problems with anyone and everyone, but must write up your own final submission without reference to any sources other than the textbook and instructor.

\begin{enumerate}
\item (From Devlin, $Sets, Functions, and \ Logic$) The Hilbert Hotel, named after the famous German mathematician (and set theory pioneer) David Hilbert, has an inifinte number of rooms.  The rooms are numbered 1, 2, 3, etc.  One evening --- it was a Super Bowl weekend --- all the rooms were booked.  But late that night, an unexpected VIP turned up and asked for a room.  Fortunately, the desk clerk had been reading Keith Devlin's book $Sets, Functions, and \ Logic$.  With a bit of rearranging, the clerk was able to arrange matters so that the VIP got a room and so did everyone else.  How did he do it?

\item (From Devlin, $Sets, Functions, and \ Logic$) The following evening the rooms were all still booked, but an infinite number of new guests arrived, all without reservations.  The clever desk clerk was again able to arrange matters so that all the new arrivals got rooms and so too did the guests who had advance reservations.  What did the clerk do this second night?

\item Consider the relation $\sim$ on $\mathbb{Z}$ given by $x$ $\sim$ $y$ iff 5 divides $x-y$.  Determine whether this relation is reflexive, symmetric, and transitive.

\item Consider the relation $\sim$ on $\mathbb{Z}$ given by $x$ $\sim$ $y$ iff 5 divides $x+y$.  Determine whether this relation is reflexive, symmetric, and transitive.

\item Let $S = \{1, 2, 3, 4, 5\}$.  Then $R =\{(1,1), (1,3), (2,2), (2,5), (3,1), (3,3), (4,4), (5,2), (5,5)\}$ is an equivalence relation on $S$.  Write the equivalence classes of $S$ associated with $R$.

\item Let $S = \{1, 2, 3, 4\}$.  Suppose that $\sim$ is an equivalence relation with $1 \sim 4$.  What are the possible partitions associated with $\sim$?

\item Do the BinaryGateway on WeBWorK, available via
\begin{center} http:webwork.coe.edu/webwork2/MTH-215/BinaryGateway/ . \end{center}

\item Let $S = \{a,b,c,d,e\}$ and $\Pi = \{\{a\},\{b,d\},\{c,e\}\}$.  Write the relation $R$ corresponding to the partition $\Pi$.

\item Let $S$ be a set and $\Pi$ a partition of $S$ defined by $a \sim b \Leftrightarrow \exists P \in \Pi$ for which $a, b \in P$.  Then $\Pi$ is a reflexive relation.

\item Let $S$ be a set and $\Pi$ a partition of $S$ defined by $a \sim b \Leftrightarrow \exists P \in \Pi$ for which $a, b \in P$.  Then $\Pi$ is a symmetric relation.

\item Let $S$ be a set and $\Pi$ a partition of $S$ defined by $a \sim b \Leftrightarrow \exists P \in \Pi$ for which $a, b \in P$.  Then $\Pi$ is a transitive relation.
\end{enumerate}

\end{document}