# Final Exam for FOM

(due 5.7.16 at 2pm)

This exam consists of five questions. To receive full credit on a question you must write clearly and carefully explain your work (e.g. write a good, clear proof when it is called for).  You are allowed to consult your notes, our textbook, and me, but no other resources can be used.

Question 1.  Suppose $x, y \in \mathbb{R}$.  Prove or disprove the following statement

$\displaystyle (x+y)^2 = x^2 + y^2 \, \iff \, x = 0 \text{ or } y = 0$.

Answer.  proof. ($\Rightarrow$) Suppose $x, y \in \mathbb{R}$ and that $(x+y)^2 = x^2+y^2$.  This implies that

$(x+y)^2 = x^2 + 2xy + y^2 = x^2 + y^2$

and so by subtracting $x^2+y^2$ from both sides we find that

$2xy = 0$.

This implies that either $x = 0$ or $y = 0$, as desired.

($\Leftarrow$).  Now suppose that $x = 0$ or $y = 0$.  This assumption implies that $xy = 0$.  We again expand the product and find

$(x+y)^2 = x^2 + 2xy + y^2 = x^2 + y^2$.

This completes the proof.  $\square$

Question 2.  Let $f$ be a function with domain $A$ and codomain $B$.

$\displaystyle f \,\, A \,\, B \,\, a \, \, b \, \, \forall \,\, \exists \, \, \in \, \, \notin \, \, \subseteq \, \, , \,\, (\,) \, \, = \, \, \neq \, \, \Rightarrow \, \, \iff \, \, \vee \, \, \wedge \, \, \sim$

(a) Using only the above symbols, write down the definition of “$f$ is surjective.”  You do not have to use all of the symbols.  (If you wish, you may also write the definition using words for partial credit.)

(b) Using only the above symbols, write down the definition (or its contrapositive) of “$f$ is injective.”  You do not have to use all the symbols.  (If you wish you may also write the definition using words for partial credit.)

Answer.  (a) $\forall \, b \in B, \exists \, a \in A, f(a) = b$.

(b) $\forall \, a, b \in A, f(a) = f(b) \Rightarrow a = b$

Question 3.  Let $A, B,$ and $C$ be sets.  Prove or disprove the following statement:

If $A \subseteq B \cup C$ and $A \cap B = \varnothing$, then $A \subseteq C$.

Answer.  proof.  Suppose that $A \subseteq B \cup C$ and that $A \cap B = \varnothing$.  Now let $x \in A$ be arbitrary.  By the first assumption, we this implies that $x \in B \cup C$ which means $x \in B$ or $x \in C$.  Our second assumption implies that $x \notin B$, and so it follows that $x \in C$.  Since $x \in A$ was arbitrary, this proves that $A \subseteq C \, \square$

Question 4.  Let $S$ be a set.  A relation, $\displaystyle R \subseteq S \times S$, on $S$ is called a partial order if it satisfies three properties:

(1) $\forall \, a \in S, (a, a) \in R$ (reflexivity)

(2) $\displaystyle \forall \, a, b \in S$,  $\Big{(}\,(a,b) \in R \, \wedge \, (b, a) \in R \, \Big{)} \Rightarrow a = b$ (anti-symmetry)

(3) $\displaystyle \forall \, a, b, c \in S$, $\Big{(}\, (a, b) \in R \, \wedge \, (b, c) \in R \, \Big{)} \Rightarrow (a, c) \in R$ (transitivity)

Note the similarity to the definition of an equivalence relation on $S$, but also note the important difference between the symmetry condition and the anti-symmetry condition.

(a) Let $S = \mathbb{R}$ with the relation $\displaystyle R = \{(x, y) \in \mathbb{R}\times\mathbb{R} : x \leq y \}$. Prove that $R$ is a partial order on $\mathbb{R}$ and prove that $R$ is not an equivalence relation on $\mathbb{R}$.

(b) Complete the following Theorem statement and then write a proof that shows it is true:

Theorem.  If a relation, $R$, on a set $S$, is both a partial order and an equivalence relation, then for every $s \in S$, the cardinality of the equivalence class $\displaystyle \Big{|}\,[s]\,\Big{|} =$ _______.

proof.

Answer.  (a) The relation $R = \{(x, y) : x \leq y\}$ on $\mathbb{R}$ is reflexive since for every $x \in \mathbb{R}$ it follows that $x = x \Rightarrow x \leq x$ and so $(x, x) \in R$.

The relation is anti-symmetric since if $(x, y) \in R$ and $(y, x) \in R$ it follows that $x\leq y$ and $y \leq x$.  These inequalities imply that $x = y$, as desired.

The relation is transitive since if $(x, y) \in R$ and $(y, z) \in R$ we have that $x \leq y$ and $y \leq z$.  This can be expressed as the double-inequality $x \leq y \leq z$ which implies that $x \leq z$ and so $(x, z) \in R$.

Finally, $R$ is not an equivalence relation because it is not symmetric.  For example, $(2, 7) \in R$ since $2 \leq 7$, but $(7,2) \notin R$ since $7 > 2$.

(b)  proof.  Suppose $R$ is both a partial order and an equivalence relation on a set $S$.  In addition to being reflexive and transitive, this also implies that $R$ is both symmetric and antisymmetric.

Let $s \in S$ be an arbitrary element, and suppose $x \in [s]$.  By definition of equivalence class, this means that $(x, s) \in R$.  Because $R$ is an equivalence relation, symmetry implies that $(s, x) \in R$.  Because $R$ is a partial order, we have that since $(x, s) \in R$ and $(s, x) \in R$, it follows that $x = s$.

This shows that $[s] \subseteq \{s\}$.  By reflexivity, it follows that $\{s\} \subseteq [s]$ and so for every element $s \in S$ we have $[s] = \{s\}$.  In particular, we learn that for every $s \in S, \left|[s]\right| = 1$.  $\square$

Question 5.  For this problem we will use the set of natural numbers, $\displaystyle \mathbb{N}$, and an arbitrary, two-element set $\displaystyle A = \{a, b\}$.

Consider the two sets of functions

$\displaystyle S_1 = \{ \text{ all functions } f : A \to \mathbb{N} \}$

$\displaystyle S_2 = \{ \text{ all functions } g: \mathbb{N} \to A \}$

(a)  Given the function

$h(x) = \left\{\begin{array}{c} a \text{ if } x \text{ is even } \\ \\ b \text{ if } x \text{ is odd } \end{array}\right.$

determine which statement is true: $h \in S_1$ or $h \in S_2$.

(b) Explain which of the two sets cannot contain any injective functions.  Explain which of the two sets cannot contain any surjective functions.

(c) Prove that $S_1$ is countable.

(d ) Is $S_2$ countable or uncountable?  Prove your answer.

Answer.  (a)  $h \in S_2$ since the outputs of $h$ are elements of $A$ and the inputs of $h$ are elements of $\mathbb{N}$.

(b)  $S_1$ cannot contain any surjective functions, and $S_2$ cannot contain any injective functions.

(c ) There are many ways to prove that $S_1$ is countable.  Here is but one.

proof.  Consider the function $F:S_1 \to \mathbb{N}\times\mathbb{N}$ defined by

$F(f) = (f(a), f(b))$

where $f \in S_1$ is arbitrary.  We can show that $F$ is a bijection, which will then imply that $|S_1| = |\mathbb{N}\times\mathbb{N}|$.

To show that $F$ is one-to-one, suppose $F(f) = F(g)$.  This means that $(f(a), f(b)) = (g(a), g(b))$ which implies that $f(a) = g(a)$ and $f(b) = g(b)$.  Because the domain $A$ only contains the two elements $a$ and $b$, it follows that the functions $f$ and $g$ are the same.  Hence $F$ is one-to-one.

To show that $F$ is onto, let $(m, n) \in \mathbb{N} \times \mathbb{N}$ be arbitrary.  Now consider the function $f \in S_1$ defined by

$f(a) = m \text{ and } f(b) = n$.

By construction, $F(f) = (f(a), f(b)) = (m, n)$ and so $F$ is onto.

We have proven in class (and in the book) that the Cartesian product of two countable sets is countable, and so in particular $|\mathbb{N}\times\mathbb{N}| = |\mathbb{N}|$.  We therefore have that $S_1$ is countable since

$|S_1| = |\mathbb{N}\times\mathbb{N}| = |\mathbb{N}|$

This completes the proof.  $\square$

(d) $S_2$ is uncountable.  This can be proved using a proof by contradiction.

proof (by contradiction).  Suppose that $S_2$ is countable.  This means that the elements of $S_2$ can be listed, say as

$S_2 = \{f_1, f_2, f_3, \cdots \}$

where each function $f_i: \mathbb{N} \to A$.  Similar to Cantor’s diagonalization argument, we can construct a function $g:\mathbb{N} \to A$ that does not equal any of the functions $f_i$ in our presumed list.  Define $g$ by

$g(n) = \left\{ \begin{array}{c} a \text{ if } f_n(n) = b \\ \\ b \text{ if } f_n(n) = a \end{array}\right.$

By definition, $\forall \, k \in \mathbb{N}, g(a) \neq f_k(a) \text{ or } g(b) \neq f_k(b)$ and so, in particular, $g \neq f_k$ for any value of $k$.  $\square$