**Question 1**. Let denote the set of all words in the English language and define the relation on by

(a) Prove that is an equivalence relation on .

(b) Write down at least three distinct elements in the equivalence class .

(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 and . 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 rhymes with , then certainly rhymes with . Lastly, if rhymes with and rhymes with , then rhymes with .

(b)

(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

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 .

(b) Let ; we want to show .

(c ) Suppose and that .

(d) Therefore .

(e) Suppose .

(f) Suppose that and that .

(g) Suppose there exists a bijection .

(h) Therefore .

(1) This is the concluding line from a proof that .

(2) This is the concluding line from a proof that .

(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 to is a function.

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

(8) This is the first line in a proof that .

(9) This is the last line in a proof that .

(10) This is the first line in a proof that a function is onto.

(11) This is the last line in a proof that a function is onto.

(12) This is the first line in a proof that a function is one-to-one.

(13) This is the last line in a proof that a function is one-to-one.

(14) This is a line from a proof that 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 () matrix multiplication:

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

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 -th power of this matrix. A few test cases should help:

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

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

For the inductive step, suppose that

for an arbitrary . Then

Once simplified, the above equation becomes

which is precisely the desired formula when . This completes the proof.

**Question 4**. (a) Suppose is a bijection. Does this imply that ? 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

is uncountable.

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

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

Prove that is a bijection.

**Answer**. (a) It is not true that the existence of a bijection implies that . Consider, for example, the two sets and . The function is clearly a bijection but .

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

Then we can define a new real number, by setting

where if and if . This ensures that but is no where in the given list above.

(c ) To prove that is one-to-one, suppose that where . This means that

which implies that for all indices . This means that whenever so does (and whenever so does ). To prove that this implies , we will show that and that .

Let . Then since is a subset of the naturals. By the definition of the given function , this implies that the value of the decimal place . However, since , we see that therefore . Therefore .

Similarly, if , then . Therefore .

To prove that is onto, let be arbitrary. Then consider the set

By the definition of it follows that .

**Question 5**. Using any proof method you like, prove that if , then either is divisible by 4 or that is divisible by 4.

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

Case 1: ( is even). Suppose that is even. This means . When we square we find

which is a multiple of four, and hence divides .

Case 2: ( is odd). Suppose that is odd. This means . When we square we find

and so

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

**Question 6**. Let be a function from set to set . Define the relation on set by the following rule:

.

(a) Prove that is an equivalence relation.

(b) Consider the function given by the rule . Describe the equivalence class using the equivalence relation from part (a). Describe the equivalence class . Based on these two equivalence class descriptions, describe the equivalence class for an arbitrary, non-zero real number .

**Answer**. (a) We must check the three properties. First, is reflexive since for every , and so . Second, is symmetric since if we have that and this implies that . Therefore . Finally, is transitive since if and it follows that

(b) In this example

.

Similarly,

.

More generally, for any we have