% Homework 3 solutions, 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|}

% Pilfered from an example on page 106 of the TeXbook
\def\qed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}

\centerline{CSCE~235: Introduction to Discrete Structures}
\centerline{{\bf Homework assignment~3} (solutions)}
\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$.

\solution We are trying to prove that no square leaves a remainder of~2 when
divided by~3. If any integer is divided by~3, the remainder is either 0,~1,
or~2. Therefore every integer~$n$ can be written as $3r$,~$3r+1$, or $3r+2$ for
some integer~$r$; moreover, $n$~can be written in exactly one of these three
forms, depending on what remainder is left when $n$ is divided by~3. We shall
consider these three cases separately.

{\medskip\narrower

\noindent{\bf Case~1:} Suppose $n=3r$ for some integer~$r$. Then
$$n^2=(3r)^2=9r^2=3(3r^2),$$
so $n^2=3s$, where $s=3k^2$. Therefore the remainder when $n^2$ is divided by~3
is~0, so there does not exist an integer~$k$ such that $n^2=3k+2$, because
$n^2$ is of the form~$3k$, not $3k+2$.

\medskip

\noindent{\bf Case~2:} Suppose $n=3r+1$ for some integer~$r$. Then
$$n^2=(3r+1)^2=9r^2+6r+1=3(3r^2+2r)+1,$$
so $n^2=3t+1$, where $t=3r^2+2r$. Therefore the remainder when $n^2$ is divided
by~3 is~1, so there does not exist an integer~$k$ such that $n^2=3k+2$, because
$n^2$ is of the form~$3k+1$, not $3k+2$.

\medskip

\noindent{\bf Case~3:} Suppose $n=3r+2$ for some integer~$r$. Then
$$n^2=(3r+2)^2=9r^2+12r+4=3(3r^2+4r+1)+1,$$
so $n^2=3u+1$, where $u=3r^2+4r+1$. Therefore the remainder when $n^2$ is
divided by~3 is~1, so there does not exist an integer~$k$ such that $n^2=3k+2$,
because $n^2$ is of the form~$3k+1$, not $3k+2$.

\medskip}

\noindent Thus, in all cases there does not exist an integer~$k$ such that
$n^2=3k+2$, and the statement has been proved. \qed

\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$.

\solution

\part{(a)} $D=\{\,x\in\Z^+\mid x<4\,\}$. (Other answers are possible.)
\part{(b)} $A\subseteq A$, $A\subseteq D$, $B\subseteq B$, $B\subseteq D$,
$C\subseteq B$, $C\subseteq C$, $C\subseteq D$, and $D\subseteq D$.

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

\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\}$

\solution

\part{(a)} False. The empty set~$\emptyset$ contains no elements, so 0 cannot
be an element of the empty set.

\part{(b)} False. The set~$\{0\}$ contains only one element, which is the
number~0. It does not contain the empty set as an element. Therefore, the empty
set~$\emptyset$ is not an element of the set~$\{0\}$.

\part{(c)} False. The only subset of the empty set is the empty set, so the
set~$\{0\}$ is not a subset of the empty set. (The set~$\{0\}$ contains an
element, the number~0, which is not an element of the empty set; therefore
$\{0\}$ is not a subset of the empty set.)

\part{(d)} True. The empty set~$\emptyset$ is a subset of every set, so in
particular it is a subset of the set~$\{0\}$.

\part{(e)} False. The set~$\{0\}$ contains exactly one element, which is the
number~0. It does not contain the {\it set\/}~$\{0\}$ as an element. It is
important to see that the number~0 is not the same thing as the set~$\{0\}$.

\part{(f)} True. Every set is a subset of itself, so in particular the
set~$\{0\}$ is a subset of itself.

\part{(g)} True. Again, every set is a subset of itself, so in particular the
set~$\{\emptyset\}$, which is the set containing the empty set~$\emptyset$, is
a subset of itself.

\part{(h)} True. The set~$\{\emptyset\}$ is the set containing the empty
set~$\emptyset$, so the empty set is an element of the set~$\{\emptyset\}$.

\part{(i)} True. The empty set~$\emptyset$ is a subset of every set, so in
particular it is a subset of the set~$\{\emptyset\}$. Note that the reason this
statement is true is {\bf not} that the empty set is an element of the
set~$\{\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)$

\solution

\part{(a)} If a set~$S$ has $n$~elements, then its power set~$P(S)$ has
$2^n$~elements (see page~117 of the textbook). Therefore, since $A$ has
$m$~elements, the power set~$P(A)$ of~$A$ has $2^m$~elements, so the
cardinality of~$P(A)$ is~$2^m$.

\part{(b)} Since $B$ has $n$~elements, the power set~$P(B)$ of~$B$ has
$2^n$~elements, so the cardinality of~$P(B)$ is~$2^n$.

\part{(c)} The set~$A\times B$, called the {\it Cartesian product\/} of $A$
and~$B$, consists of all ordered pairs of the form~$(a,b)$, where $a$ is an
element of~$A$ and $b$~is an element of~$B$. Since there are $m$~elements
in~$A$, we have $m$~different choices for the first element of an ordered pair
of the form~$(a,b)$; and since there are $n$~elements in~$B$, for each of these
$m$~different possibilities for the first element of the ordered pair we have
$n$~different choices for the second element of the ordered pair. Altogether,
then, we have $m\times n$~different ordered pairs of the form~$(a,b)$.
Therefore, the cardinality of~$A\times B$ is~$mn$.

\part{(d)} Since $A\times B$ has $mn$~elements, the power set~$P(A\times B)$
of~$A\times B$ has $2^{mn}$~elements, so the cardinality of~$P(A\times B)$
is~$2^{mn}$.

\part{(e)} The set~$P(A)\times P(B)$ is the set of all ordered pairs of the
form~$(R,S)$, where $R$ is a subset of~$A$ and $S$~is a subset of~$B$. We know
that there are $2^m$~different subsets of~$A$ [from part~(a) of this problem],
and we know that there are $2^n$~different subsets of~$B$ [from part~(b)].
Using similar reasoning to that used in part~(c), we see that there are
$2^m\times2^n$~different ordered pairs of the form~$(R,S)$. Therefore, the
cardinality of~$P(A)\times P(B)$ is~$2^m2^n=2^{m+n}$.

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

\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$?

\solution

\part{(a)} The set~$A\cup C$ consists of all elements that are in~$A$ or
in~$C$, or in both, so
$$A\cup C=\{1,2,3,4,5,6,9,12,15,18\}.$$

\part{(b)} The set~$B\cap C$ consists of all elements that are in both $B$
and~$C$, so it consists of all positive integers less than~20 that are both
even and a multiple of~3. So we have
$$B\cap C=\{6,12,18\}.$$
This can also be written as
$$B\cap C=\{\,x\mid\hbox{$x$~is a multiple of~6}\,\}.$$

\part{(c)} The set~$A-D$ consists of all elements of~$A$ that are not elements
of~$D$, so it contains all integers from 1 to~5 that are not prime, i.e.,
$$A-D=\{1,4\}.$$

\part{(d)} The set~$D-A$ consists of all elements of~$D$ that are not elements
of~$A$, so it contains all prime numbers less than~20 that are not between 1
and~5, i.e.,
$$D-A=\{7,11,13,17,19\}.$$

\part{(e)} The set~$\overline A$ consists of all elements that are not
contained in~$A$. Since our universal set is the set of all positive integers
less than~20, we have
$$\overline A=\{6,7,8,9,10,11,12,13,14,15,16,17,18,19\}=\{6,7,8,\ldots,19\}.$$

\part{(f)} The set~$B\cap D$ consists of all elements that are in both $B$
and~$D$, so it consists of all positive integers less than~20 that are both
even and prime. There is only one such integer, so we have
$$B\cap D=\{2\}.$$

\part{(g)} The set~$(B\cap C)\cap D$ consists of all elements that are in all
three of the sets $B$,~$C$, and~$D$. Thus it contains all positive integers
less than~20 that are even multiples of~3 and prime. Any number that is an
even multiple of~3, however, must be divisible by both 2 and~3, so it cannot
be prime. Therefore, there can be no elements in the set~$(B\cap C)\cap D$, so
we have
$$(B\cap C)\cap D=\emptyset.$$

\part{(h)} The set~$(B\cup D)\cap\overline A$ consists of all elements that are
either in~$B$ or in~$D$ (or both), and that additionally are in the complement
of~$A$. First, we figure out what $B\cup D$ is: this is the set of all positive
integers less than~20 that are either even or prime, so
$$B\cup D=\{2,3,4,5,6,7,8,10,11,12,13,14,16,17,18,19\}.$$
Now, the set~$(B\cup D)\cap\overline A$ consists of all elements that are in
both the set~$B\cup D$ shown above and the set~$\overline A$ shown in the
answer to part~(e). Hence,
$$(B\cup D)\cap\overline A=\{6,7,8,10,11,12,13,14,16,17,18,19\}.$$

\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$.

\solution

\part{(a)} An ordered pair~$(a,b)$ is in~$R$ if and only~if $a=b$. Therefore,
the ordered pairs in~$R$ are $(0,0)$,~$(1,1)$, $(2,2)$, and~$(3,3)$. [Note that
$(4,4)$ is not in~$R$, since $R$ is a relation from~$A$ to~$B$, and so the
second element of the ordered pair must be an element of~$B$; and $4\notin B$.]

\part{(b)} An ordered pair~$(a,b)$ is in~$R$ if and only~if $a+b=4$. Therefore,
the ordered pairs in~$R$ are $(1,3)$,~$(2,2)$, $(3,1)$, and~$(4,0)$. [Note that
$(0,4)$ is not in~$R$, since the second element of the ordered pair must be an
element of~$B$, and $4\notin B$.]

\part{(c)} An ordered pair~$(a,b)$ is in~$R$ if and only~if $a>b$. Therefore,
the ordered pairs in~$R$ are $(1,0)$,~$(2,0)$, $(2,1)$, $(3,0)$, $(3,1)$,
$(3,2)$, $(4,0)$, $(4,1)$, $(4,2)$, and~$(4,3)$.

\part{(d)} An ordered pair~$(a,b)$ is in~$R$ if and only~if $a$ divides~$b$,
that~is, if and only~if $b$ is a multiple of~$a$. Therefore, the ordered pairs
in~$R$ are $(1,0)$,~$(1,1)$, $(1,2)$, $(1,3)$, $(2,0)$, $(2,2)$, $(3,0)$,
$(3,3)$, and~$(4,0)$.

\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\}$

\solution

\part{(a)} This relation is not reflexive, since it does not contain $(1,1)$.
It is not symmetric, since for example it contains $(2,4)$ but not $(4,2)$.
However, it is transitive, because for all $a$,~$b$, and $c$ in the
set~$\{1,2,3,4\}$, if $(a,b)$ and $(b,c)$ are both in the relation, then
$(a,c)$ is too; for example, $(2,3)$ and $(3,2)$ are both in the relation, and
sure enough $(2,2)$ is also in the relation. Since this relation is not
reflexive and is not symmetric, it is not an equivalence relation.

\part{(b)} This relation is reflexive, because for all~$a$ in the
set~$\{1,2,3,4\}$, the ordered pair~$(a,a)$ is in the relation; in other words,
the relation contains all of $(1,1)$,~$(2,2)$, $(3,3)$, and~$(4,4)$. It is also
symmetric, because for all $a$ and~$b$ in the set~$\{1,2,3,4\}$, if $(a,b)$ is
in the relation, then $(b,a)$ is too; for example, $(1,2)$ is in the relation,
and $(2,1)$ is too. This relation is also transitive. Since this relation is
reflexive, symmetric, and transitive, it is an equivalence relation.

\part{(c)} This relation is not reflexive, since for example it does not
contain $(1,1)$. It is not symmetric, since for example it contains $(1,2)$ but
not $(2,1)$. It is not transitive, since for example it contains $(1,2)$ and
$(2,3)$, but not $(1,3)$. Since this relation has none of these three
properties, it is clearly not an equivalence relation.

\part{(d)} This relation is reflexive and symmetric, but it is not transitive,
since for example it contains $(1,3)$ and $(3,2)$, but not $(1,2)$. Therefore
it is not an equivalence relation.

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

% cheating to get everything to fit on the last page
\hbox{}
\vskip-24pt

\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\}$

\solution

\part{(a)} This relation is not an equivalence relation. It lacks reflexivity
(since for example $5\not>5$) and symmetry (since for example $8>4$, but
$4\not>8$). However, it is transitive, because if $a>b$ and $b>c$, then $a>c$.

\part{(b)} This relation is an equivalence relation. It is reflexive because
$a=a$ for all~$a$; it is symmetric because if $a=b$, then $b=a$; and it
is transitive because if $a=b$ and $b=c$, then $a=c$.

\part{(c)} This relation is not an equivalence relation. It lacks transitivity,
since for example $\labs3-2\rabs\le1$ and $\labs2-1\rabs\le1$ but
$\labs3-1\rabs>1$. However, it is reflexive, since $\labs a-a\rabs=0\le1$ for
all~$a$, and it is symmetric, since if $\labs a-b\rabs\le1$, then
$\labs b-a\rabs\le1$ (this is easily seen by noting that
$\labs a-b\rabs=\labs b-a\rabs$).

\part{(d)} This relation is not an equivalence relation. It lacks symmetry,
since for example 5 divides~10, but not the other way round (10~does not
divide~5). It is actually not reflexive either, since 0 does not divide~0
(though every other integer divides itself). However, it is transitive, because
if $a$ divides~$b$ and $b$~divides~$c$, then $a$ divides~$c$.

\part{(e)} This relation is an equivalence relation. It is reflexive because
$\labs a\rabs=\labs a\rabs$ for all~$a$; it is symmetric because if
$\labs a\rabs=\labs b\rabs$, then $\labs b\rabs=\labs a\rabs$; and it is
transitive, because if $\labs a\rabs=\labs b\rabs$ and
$\labs b\rabs=\labs c\rabs$, then $\labs a\rabs=\labs c\rabs$.

\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.

\solution Let the first subset of the partition be~$\{1,2\}$, and for $i\ge2$
let the $i$th subset of the partition consist of all integers greater than the
$(i-1)$st prime number and less than or equal to the $i$th prime number. Then
the partition is
$$\eqalign{
	\bigl\{\,
	&\{1,2\},\,\{3\},\,\{4,5\},\,\{6,7\},\,\{8,9,10,11\},\,\{12,13\},\,
		\{14,15,16,17\},\cr
	&\{18,19\},\,\{20,21,22,23\},\,\{24,25,26,27,28,29\},\,\{30,31\},\cr
	&\{32,33,34,35,36,37\},\,\{38,39,40,41\},\,\ldots\,\bigr\}.\cr
}$$

Alternatively, for $i\ge1$ let the $i$th subset of the partition consist of all
integers whose least prime factor is the $i$th prime number (and include 1 in
the first subset). Then the partition is
$$\eqalign{
	\bigl\{\,
	&\{1,2,4,6,8,10,12,14,16,18,20,\ldots\},\cr
	&\{3,9,15,21,27,33,39,51,57,\ldots\},\cr
	&\{5,25,35,55,65,85,95,\ldots\},\cr
	&\{7,49,77,91,119,133,\ldots\},\cr
	&\{11,121,143,187,209,\ldots\},\cr
	&\{13,169,221,247,299,\ldots\},\cr
	&\{17,289,323,391,493,\ldots\},\,\ldots\,\bigr\}.\cr
}$$

Note that the first of these partitions has infinitely many subsets, each of
which is finite, while the second has infinitely many subsets, each of which is
infinite.

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

\bye