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.

Answer.  This can be proven directly, by addressing two different cases.

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s