

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Quiz 2
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem\pts{24} \textbf{Finite and Infinite Sets}

For each of the following sets, state whether it is finite, countably
infinite, or uncountably infinite.  If it is finite, give its size.
If it is countably infinite, give an injective function from the given
set to $\mathbb{N}$.  If it is uncountable, give a brief argument.

\problempart {\bf (6 points)} $R = \mathcal{P}(\{2^{-i} \ | \ i \in
\mathbb{N}\})$

\solution{\bigskip
{\bf Solution:}

Uncountable.  Proof by contradiction by the diagonalization method:
suppose $S_0, S_1, \ldots$ is a complete list of all elements of $R$.  
Consider the set $S = \{ 2^{-i} \ | \ 2^{-i} \notin S_i\}$.  Since $S$
is a member of $R$ it must appear in the list somewhere, so assume its
number is $n$.  This is a contradiction since $2^{-n} \in S 
\Leftrightarrow 2^{-n} \notin S$.  Thus, there must not be any such 
complete list.
}

\smallspace

\problempart {\bf (6 points)} $S = \mathcal{P}(\mathbb{N}) \cap
\mathcal{P}(\{ 2^{-i} \ | \ i \in \mathbb{N}\})$

\solution{\bigskip
{\bf Solution:}

Finite.  The only two subsets in common between $\mathbb{N}$ and $\{
2^{-i}
\ | \ i \in \mathbb{N}\}$ are the subset containing $1$ and the
empty set.  Thus, its 
size is 2.
}



\smallspace
\problempart {\bf (6 points)} $T$, the set of all finite sets of
prime numbers.

\solution{\bigskip
{\bf Solution:}

Countable.  Each finite set of prime numbers defines a different
integer, namely the product of all the numbers in the set.  This
mapping is injective since the prime factorization of a number is
unique.  Thus, $N$ can be mapped into the natural numbers, so $N$ is
countable.  (We can count $T$ by listing the sets that map to integers
in ascending order of the integers.  So the first element would be
$\emptyset$, the second would be $\{2\}$, and the fifth would be $\{2,
3\}$, et cetera).

}

\smallspace
\problempart {\bf (6 points)} $U$, the set of all equivalence classes
of the equivalence relation $\{ (x, y) \ | \ x, y \in \mathbb{R}$ and
$x-y \in \mathbb{Q}\}$

\solution{\bigskip
{\bf Solution:}

Uncountable.  Each equivalence class is a countable set: if $C$ were
countable we could express $R$ as the cartesian product of two
countable sets (namely, the set of equivalence classes and
$\mathbb{Q}$).  But this would make $R$ countable and it is not.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (10 points}) Indicate whether each of the following sets
is finite (F), countably infinite (CI), or uncountably infinite (UI)
by circling the right answer.  {\em Note that an even quantity is
necessarily finite.}

\bigskip

\begin{tabular}{lccc}
The set of all binary strings with even length.
    & F & \us{CI} & UI \\ \\
The set of all infinite binary strings with 1's in every even position.
    & F & CI & \us{UI} \\
(Odd positions may contain either a 0 or a 1.) \\ \\
The set of all infinite binary strings with an even number of 1's.
    & F & \us{CI} & UI \\ \\
The set of even primes.
    & \us{F} & CI & UI \\ \\
The set of all even-size sets of even-length binary strings.
    & F & \us{CI} & UI \\ \\
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points)} Suppose that $A$ and $B$ are non-empty sets
such that $A$ is strictly contained in $B$.  Mark each statement below
{\bf T}rue or {\bf F}alse.

\bigskip

\begin{tabular}{ll}
\underline{\hspace{1cm}} & Set $A$ is finite iff set $B$ is
finite. \\
& \sol{(False.)} \\
\underline{\hspace{1cm}} & If $B$ is finite, then there must
exist a surjection mapping $B$ to $A$. \\
& \sol{(True.)} \\
\underline{\hspace{1cm}} & If $B$ is finite, then there must
exist an injection mapping $A$ to $B$. \\
& \sol{(True.)} \\
\underline{\hspace{1cm}} & If $B$ is finite and there is a bijection
mapping $A$ to $B \setminus A$, then $|B| = 2 |A|$. \\
& \sol{(True.)} \\
\underline{\hspace{1cm}} & There can not exist a bijection from $A$ to
$B$. \\
& \sol{(False.)} \\
\end{tabular}