\documentclass[11pt]{article}

\title{18.901 Problem Set 1}
\author{Chris Laas}
\date{February 7, 2000}

\begin{document}
\maketitle

Section 1, problem 2.

\begin{tabular}{lll}

(a) & false
 & $ A \subset B \mbox{ and } A \subset C \Rightarrow A \subset (B \cup C) $ \\

(b) & false
 & $ A \subset B \mbox{ or } A \subset C \Rightarrow A \subset (B \cup C) $ \\

(c) & false
 & $ A \subset B \mbox{ and } A \subset C \Leftarrow A \subset (B \cap C) $ \\

(d) & false
 & $ A \subset B \mbox{ or } A \subset C \Leftarrow A \subset (B \cap C) $ \\

(e) & false
 & $ A - (A - B) \subset B $ \\

(f) & false
 & $ A - (B - A) \supset A - B $  \\

(g) & true \\

(h) & false
 & $ A \cup (B - C) \supset (A \cup B) - (A \cup C) $ \\

(i) & true \\

(j) & true \\

(k) & false \\

(l) & true \\

(m) & false
 & $ (A \times B) \cup (C \times D) \subset (A \cup C) \times (B \cup D) $ \\

(n) & true \\

(o) & true \\

(p) & false
 & $ (A - B) \times (C - D) \subset (A \times C - B \times C) - A \times D $ \\

(q) & false
 & $ (A \times B) - (C \times D) \supset (A - C) \times (B - D) $ \\

\end{tabular}

Problem 4.

\begin{tabular}{ll}
(a) & $ \exists a \in A | a^2 \notin B $ \\
(b) & $ \forall a \in A | a^2 \notin B $ \\
(c) & $ \exists a \in A | a^2 \in B $ \\
(d) & $ \forall a \notin A | a^2 \notin B $ \\
\end{tabular}

Problem 5.

\begin{tabular}{lll}
& Truth of statement & Truth of converse \\ \hline\hline
(a) & true & true \\
(b) & false & true \\
(c) & true & false \\
(d) & true & true \\
\end{tabular}

\newpage

Section 2, problem 4(c).

We can say that $f$ is injective.  For, if $f$ were not
injective, then two values $x,y \in A$ would map under $f$ to the same
value $z \in B$, and thus both $x$ and $y$ would map under $g \circ f$
to the same value $g(z) \in C$, and thus $g \circ f$ would not be
injective.  Thus, $g \circ f$ is injective implies that $f$ is
injective.

However, we cannot say that $g$ is injective.  For, consider the sets
$A = \{1\}, B = \{2,3\}, C = \{4\}$, and the functions $f$ and $g$
defined by $f(1) = 2, g(2) = 4, g(3) = 4$.  Then clearly the composite
$g \circ f$ is injective, but $g$ is not.

Problem 4(e).

We can say that $g$ is surjective.  For, if $g$ were not surjective,
then there would exist some value $x \in C$ such that no element of
$B$ mapped to $x$ under $g$.  Thus, clearly no element of
$f(A) \subset B$ would map to $x$ under $g$, and thus no element of
$A$ would map to $x$ under $g \circ f$.  Thus, $g \circ f$ is
surjective implies that $g$ is surjective.

However, we cannot say that $f$ is surjective.  For, consider the sets
and functions from the previous example:  clearly the composite
$g \circ f$ is surjective, but $f$ is not.

\end{document}
