# FOM Exam 2 (with answers)

Question 1.  Let $S$ denote the set of all words in the English language and define the relation $\sim$ on $S$ by

$w_1 \sim w_2 \text{ if } w_1 \text{ rhymes with } w_2$

(a) Prove that $\sim$ is an equivalence relation on $S$.

(b) Write down at least three distinct elements in the equivalence class $[\text{cat}]$.

(c ) Write down the smallest equivalence class you can think of.  (The fewer elements it has, the more points you’ll earn.)

Answer.  (a) It is possible to argue that the proposed relation is, in fact, not an equivalence relation.  In particular, single words can belong to more than one “equivalence class” depending on how they are pronounced.  One student pointed out that the word “read” can be pronounced so as to satisfy $\text{ read } \in [\text{ red }]$ and $\text{ read } \in [\text{reed}]$.  One can overcome this technicality be carefully defining what “word” means.

Anyways, back to the problem.

Every word (trivially) rhymes with itself, and so the relation is reflexive.  If $w_1$ rhymes with $w_2$, then certainly $w_2$ rhymes with $w_1$.  Lastly, if $w_1$ rhymes with $w_2$ and $w_2$ rhymes with $w_3$, then $w_1$ rhymes with $w_3$.

(b)  $\text{hat, mat, bat, splat, pat,}\cdots \in [\text{cat}]$

(c ) I’ve been told that no words in the English language rhyme with the word “orange” — I’ve also heard the same thing claimed about the word “purple.”  Therefore

$[\text{orange}] = \{\text{orange}\}$ has one element in it, and so is as small of an equivalence class as possible.

Question 2.  Below you will find various statements taken from proofs (these statements are labeled with letters).  You will also find descriptions of parts of different proofs (these statements are labeled with numbers).  Your job is to match the lettered statements with the numbered ones.  Note that there are more numbered statements than there are lettered statements, so not all of them need to be used.  Also keep in mind that every lettered statement matches with at least one numbered statement, but some may match up with multiple.  Good luck!

(a) Suppose $x \in A$.

(b) Let $b \in B$; we want to show $\exists \, a \in A, \, f(a) = b$.

(c ) Suppose $x\sim y$ and that $y \sim z$.

(d) Therefore $x \in B$.

(e) Suppose $\exists \, a_1, a_2 \in A, \, f(a_1) = f(a_2)$.

(f) Suppose that $f(a) = b_1$ and that $f(a) = b_2$.

(g) Suppose there exists a bijection $\displaystyle f:A\to\mathbb{N}$.

(h) Therefore $1 \in \emptyset$.

(1) This is the concluding line from a proof that $A\subseteq B$.

(2) This is the concluding line from a proof that $B \subseteq A$.

(3)  This is the first line in a proof that a given relation is reflexive.

(4)  This is the first line in a proof that a given relation is symmetric.

(5)  This is the first line in a proof that a given relation is transitive

(6) This is one of the first lines in a proof that a relation from $A$ to $B$ is a function.

(7) This is one of the last lines in a proof that a relation from $A$ to $B$ is a function.

(8) This is the first line in a proof that $A \subseteq B$.

(9) This is the last line in a proof that $A \subseteq B$.

(10) This is the first line in a proof that a function $f:A \to B$ is onto.

(11) This is the last line in a proof that a function $f:A \to B$ is onto.

(12) This is the first line in a proof that a function $f:A \to B$ is one-to-one.

(13) This is the last line in a proof that a function $f:A \to B$ is one-to-one.

(14) This is a line from a proof that $f:A \to B$ is bijective.

(15) This is a line from a proof that shows a set is uncountable.

(16) This is a line from a proof that shows a set is countable.

(17) This is a concluding line from a proof by contradiction.

Question 3.  Recall from various class discussions the definition of ($2\times 2$) matrix multiplication:

$\left( \begin{array}{cc} a & b \\ c & d \end{array}\right) \, \left( \begin{array}{cc} x & y \\ z & w \end{array}\right) = \left( \begin{array}{cc} ax + bz & ay + bw \\ cx + dz & cy + dw \end{array}\right)$

Find a formula for the $n$-th power of the given matrix $A$,

$A^n = \left( \begin{array}{cc} 2 & 1 \\ -1 & 0 \end{array}\right)^n = \underbrace{\left(\begin{array}{cc} 2 & 1 \\ -1 & 0 \end{array}\right)\left(\begin{array}{cc} 2 & 1 \\ -1 & 0 \end{array}\right)\cdots \left(\begin{array}{cc} 2 & 1 \\ -1 & 0 \end{array}\right)}_{n\,\text{times}}$

and prove that your formula is correct.

(Note: You may e-mail me or ask me for a hint about the formula at the cost of 10 percentage points.)

Answer.  First we need to come up with a formula for the $n$-th power of this matrix.  A few test cases should help:

$A^1 = \left(\begin{array}{cc} 2 & 1 \\ -1 & 0 \end{array}\right)$

$A^2 = \left(\begin{array}{cc} 2 & 1 \\ -1 & 0 \end{array}\right)\left(\begin{array}{cc} 2 & 1 \\ -1 & 0 \end{array}\right) = \left(\begin{array}{cc} 4-1 & 2 \\ -2 & -1 \end{array}\right) = \left(\begin{array}{cc} 3 & 2 \\ -2 & -1 \end{array}\right)$

$A^3 = \left(\begin{array}{cc} 3 & 2 \\ -2 & -1 \end{array}\right)\left(\begin{array}{cc} 2 & 1 \\ -1 & 0 \end{array}\right) = \left(\begin{array}{cc} 4 & 3 \\ -3 & -2 \end{array}\right)$

Based on these computations, a pattern appears to be present; it looks as though

$A^n = \left(\begin{array}{cc} n+1 & n \\ -n & -(n-1) \end{array}\right)$

To prove that this formula is correct, one can proceed by induction.  When $n = 1$, the equation is true, and so the base case is handled.

For the inductive step, suppose that

$A^k = \left(\begin{array}{cc} k+1 & k \\ -k & -(k-1) \end{array}\right)$

for an arbitrary $k \in \mathbb{N}$.  Then

$A^{k+1} = AA^k = \left(\begin{array}{cc} 2 & 1 \\ -1 & 0 \end{array}\right)\left(\begin{array}{cc} k+1 & k \\ -k & -(k-1) \end{array}\right) = \left(\begin{array}{cc} 2k+2 -k & 2k - (k-1) \\ -(k+1) & -k \end{array}\right)$

Once simplified, the above equation becomes

$A^{k+1} = \left(\begin{array}{cc} k+2 & k+1 \\ -(k+1) & -k \end{array}\right)$

which is precisely the desired formula when $n = k+1$.  This completes the proof.  $\square$

Question 4.  (a) Suppose $\displaystyle f:A\to B$ is a bijection.  Does this imply that $A = B$?  Be sure to prove your answer.  (Note: this question has nothing to do with the following parts.  I just wanted to ask it.)

(b) Adjust Cantor’s Diagonalization argument to prove that the subset of real numbers

$\displaystyle S = \left\{0.x_1x_2x_3\dots \,:\, x_i = 0 \text{ or } x_i = 1 \right\}$

is uncountable.

(c ) For this part of the problem we will use a function

$\displaystyle f:\mathcal{P}(\mathbb{N}) \to S$

where the set $S$ is as defined in part (b) above.  Define the function $f$ by

$f(A) = 0.x_1x_2x_3\cdots \text{ where } \begin{array}{c} x_i = 0 \text{ if } i \notin A \\ \\ x_i = 1 \text{ if } i \in A \end{array}$

Prove that $f$ is a bijection.

Answer.  (a)  It is not true that the existence of a bijection $f:A\to B$ implies that $A = B$.  Consider, for example, the two sets $A = \{1, 2\}$ and $B = \{a, b\}$.  The function $f(1) = a, f(2) = b$ is clearly a bijection but $A \neq G$.

(b)  Very little needs to be adjusted to run Cantor’s diagonalization argument on the given set $S$.  For a contradiction, suppose the elements of $S$ could be arranged in a list.  We could notate them as follows:

$s_1 = 0.x_{11}x_{12}x_{13}\cdots$

$s_2 = 0.x_{21}x_{22}x_{23}\cdots$

$s_3 = 0.x_{31}x_{32}x_{33}\cdots$

$\vdots$

Then we can define a new real number, $s$ by setting

$s = 0.x_1x_2x_3\cdots$

where $x_{i} = 0$ if $x_{ii} = 1$ and $x_{i} = 1$ if $x_{ii} = 0$.  This ensures that $s \in S$ but $s$ is no where in the given list above.

(c ) To prove that $f$ is one-to-one, suppose that $f(A) = f(B)$ where $A, B \in \mathcal{P}(\mathbb{N})$.  This means that

$f(A) = 0.a_1a_2a_3\cdots = 0.b_1b_2b_3\cdots = f(B)$

which implies that $a_i = b_i$ for all indices $i$.  This means that whenever $b_i = 0$ so does $a_i$ (and whenever $b_i = 1$ so does $a_i$).  To prove that this implies $A = B$, we will show that $A \subseteq B$ and that $B \subseteq A$.

Let $i \in A$.  Then $i \in \mathbb{N}$ since $A$ is a subset of the naturals.  By the definition of the given function $f$, this implies that the value of the decimal place $a_i = 1$.  However, since $f(A) = f(B)$, we see that therefore $1 = a_i = b_i \Rightarrow i \in B$.  Therefore $A \subseteq B$.

Similarly, if $j \in B$, then $b_j = 1 \Rightarrow a_j = 1 \Rightarrow j \in A \Rightarrow B \subseteq A$.  Therefore $A = B$.

To prove that $f$ is onto, let $s = 0.x_1x_2x_3\cdots \in S$ be arbitrary.  Then consider the set

$A = \{i \in \mathbb{N} : x_i \neq 0\} \subseteq \mathbb{N}$

By the definition of $f$ it follows that $f(A) = 0.x_1x_2x_3\cdots$.

Question 5.  Using any proof method you like, prove that if $n \in \mathbb{N}$, then either $n^2$ is divisible by 4 or that $n^2-1$ is divisible by 4.

Case 1: ($n$ is even).  Suppose that $n$ is even.  This means $\exists \, k \in \mathbb{Z}, n = 2k$.  When we square $n$ we find

$n^2 = 4k^2$

which is a multiple of four, and hence $4$ divides $n^2$.

Case 2: ($n$ is odd).  Suppose that $n$ is odd.  This means $\exists \, k \in \mathbb{Z}, n = 2k+1$.  When we square $n$ we find

$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 4(k^2+k) + 1$

and so

$n^2 - 1 = 4(k^2+k)$

is a multiple of four.  Hence $4$ divides \$latex n^2-14.

Question 6.  Let $\displaystyle f: A \to B$ be a function from set $A$ to set $B$.  Define the relation $\sim \,$ on set $A$ by the following rule:

$a_1 \sim a_2 \text{ means } f(a_1) = f(a_2)$.

(a) Prove that $\sim$ is an equivalence relation.

(b) Consider the function $f:\mathbb{R} \to \mathbb{R}$ given by the rule $f(x) = x^2$.  Describe the equivalence class $[1]$ using the equivalence relation from part (a).  Describe the equivalence class $[0]$.  Based on these two equivalence class descriptions, describe the equivalence class $[s]$ for an arbitrary, non-zero real number $s \in \mathbb{R}$.

Answer.  (a) We must check the three properties.  First, $\sim$ is reflexive since for every $a \in A, f(a) = f(a)$, and so $a \sim a$.  Second, $\sim$ is symmetric since if $a_1 \sim a_2$ we have that $f(a_1) = f(a_2)$ and this implies that $f(a_2) = f(a_1)$.  Therefore $a_2 \sim a_1$.  Finally, $\sim$ is transitive since if $a_1 \sim a_2$ and $a_2 \sim a_3$ it follows that $f(a_1) = f(a_2) = f(a_3) \Rightarrow f(a_1) = f(a_3) \Rightarrow a_1 \sim a_3.$

(b) In this example

$[1] = \{x \in \mathbb{R} : x^2 = 1^2\} = \{-1, 1\}$.

Similarly,

$[0] = \{x \in \mathbb{R} : x^2 = 0^2 \} = \{0\}$.

More generally, for any $s \in \mathbb{R}$ we have

$[s] = \{x \in \mathbb{R} : x^2 = s^2\} = \{-s, s\}$