% Homework 3, CSCE 235, spring 2007
% Assigned 7 February 2007; due 12 February 2007

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=8.5truein
\pdfhorigin=1.5truein \pdfvorigin=1.25truein

\headline={\hfil}
\footline={\hfil Page~\folio\hfil}

\newcount\pno
\pno=0
\def\problem{\advance\pno by1 \noindent{\bf Problem~\the\pno.} }
\def\problemno#1. {\noindent{\bf Problem~\hbox{#1}.} }
\def\solution{\nobreak\medskip\noindent{\bf Solution.} }
\def\part#1{\medskip\indent\llap{#1\enspace}\ignorespaces}
\def\mathpart#1#2\par{{%
	\abovedisplayskip=-\ht\strutbox \advance\abovedisplayskip by-\dp\strutbox %
	\abovedisplayshortskip=-\ht\strutbox \advance\abovedisplayshortskip by-\dp\strutbox %
	\part{#1}#2\par}}

\def\implies{\;\Longrightarrow\;}
\def\Z{\mathord{\bf Z}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}

\centerline{CSCE~235: Introduction to Discrete Structures}
\centerline{{\bf Homework assignment~3} (87~points)}
\centerline{Assigned Wednesday, February~7, 2007}
\centerline{Due Monday, February~12, 2007}

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (15~points) Prove that for any integer~$n$ there does not exist an
integer~$k$ such that $n^2=3k+2$.

{\it Hint\/}: Use a proof by cases. If any integer is divided by~3, the
remainder is either 0,~1, or~2. Therefore every integer can be written as
$3k$,~$3k+1$, or~$3k+2$ for some integer~$k$. Consider these three cases
separately. For example, if $n$ leaves a remainder of~1 when divided by~3, so
that $n=3k+1$ for some~$k$, then what is the remainder when $n^2$ is divided
by~3?

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (6~points) Let $A=\{1,2\}$, $B=\{1,3\}$, $C=\{3\}$, and $D=\{1,2,3\}$.

\smallskip

\item{(a)} (2~points) Use set builder notation to describe~$D$.
\item{(b)} (4~points) Which of these sets are subsets of which other of these
sets? In other words, list all true statements of the form~$X\subseteq Y$,
where $X$~and~$Y$ are to be replaced with $A$,~$B$, $C$, or~$D$.

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (9~points) Determine whether each of these statements is true or
false.

\smallskip

\item{(a)} $0\in\emptyset$
\item{(b)} $\emptyset\in\{0\}$
\item{(c)} $\{0\}\subseteq\emptyset$
\item{(d)} $\emptyset\subseteq\{0\}$
\item{(e)} $\{0\}\in\{0\}$
\item{(f)} $\{0\}\subseteq\{0\}$
\item{(g)} $\{\emptyset\}\subseteq\{\emptyset\}$
\item{(h)} $\emptyset\in\{\emptyset\}$
\item{(i)} $\emptyset\subseteq\{\emptyset\}$

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (5~points) Let $A$ and~$B$ be finite sets. Let $m$ be the cardinality
of~$A$ and let $n$ be the cardinality of~$B$. Find the cardinality of the
following sets.

\smallskip

\item{(a)} $P(A)$
\item{(b)} $P(B)$
\item{(c)} $A\times B$
\item{(d)} $P(A\times B)$
\item{(e)} $P(A)\times P(B)$

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (8~points) Let
$$\eqalign{
	A&=\{1,2,3,4,5\},\cr
	B&=\{\,x\mid\hbox{$x$ is even}\,\},\cr
	C&=\{\,x\mid\hbox{$x$ is a multiple of~3}\,\},\hbox{ and}\cr
	D&=\{\,x\mid\hbox{$x$ is prime}\,\},\cr
}$$
where the universal set is the set of all positive integers less than~20.
[{\it Note\/}: The number~1 is not prime.]

\smallskip

\item{(a)} What is $A\cup C$?
\item{(b)} What is $B\cap C$?
\item{(c)} What is $A-D$?
\item{(d)} What is $D-A$?
\item{(e)} What is $\overline A$?
\item{(f)} What is $B\cap D$?
\item{(g)} What is $(B\cap C)\cap D$?
\item{(h)} What is $(B\cup D)\cap\overline A$?

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (8~points) List the ordered pairs in the relation~$R$ from
$A=\{0,1,2,3,4\}$ to $B=\{0,1,2,3\}$ where $(a,b)\in R$ if and only~if

\smallskip

\item{(a)} $a=b$.
\item{(b)} $a+b=4$.
\item{(c)} $a>b$.
\item{(d)} $a$ divides $b$.

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (16~points) For each of these relations on the set~$\{1,2,3,4\}$,
decide whether it is reflexive, whether it is symmetric, whether it is
transitive, and whether it is an equivalence relation.

\smallskip

\item{(a)} $\bigl\{\,(2,2),\,(2,3),\,(2,4),\,(3,2),\,(3,3),\,(3,4)\,\bigr\}$
\vskip2pt
\item{(b)} $\bigl\{\,(1,1),\,(1,2),\,(2,1),\,(2,2),\,(3,3),\,(4,4)\,\bigr\}$
\vskip2pt
\item{(c)} $\bigl\{\,(1,2),\,(2,3),\,(3,4)\,\bigr\}$
\vskip2pt
\item{(d)} $\bigl\{\,(1,1),\,(1,3),\,(2,2),\,(2,3),\,(3,1),\,(3,2),\,(3,3),\,(4,4)\,\bigr\}$

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) Which of these relations on~$\Z$ are equivalence
relations? Determine the properties of an equivalence relation that the others
lack.

\smallskip

\item{(a)} $\bigl\{\,(x,y)\bigm|x>y\,\bigr\}$
\vskip2pt
\item{(b)} $\bigl\{\,(x,y)\bigm|x=y\,\bigr\}$
\vskip2pt
\item{(c)} $\bigl\{\,(x,y)\bigm|\labs x-y\rabs\le1\,\bigr\}$
\vskip2pt
\item{(d)} $\bigl\{\,(x,y)\bigm|\hbox{$x$ divides $y$}\,\bigr\}$
\vskip2pt
\item{(e)} $\bigl\{\,(x,y)\bigm|\labs x\rabs=\labs y\rabs\,\bigr\}$

\bigskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (10~points) Find a partition of the positive integers such that no two
prime numbers are in the same subset and every subset contains a prime number.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye