# 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 . Prove or disprove the following statement

.

**Answer**. *proof*. () Suppose and that . This implies that

and so by subtracting from both sides we find that

.

This implies that either or , as desired.

(). Now suppose that or . This assumption implies that . We again expand the product and find

.

This completes the proof.

**Question 2**. Let be a function with domain and codomain .

(a) Using only the above symbols, write down the definition of “ 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 “ 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) .

(b)

**Question 3**. Let and be sets. Prove or disprove the following statement:

If and , then .

**Answer**. *proof*. Suppose that and that . Now let be arbitrary. By the first assumption, we this implies that which means or . Our second assumption implies that , and so it follows that . Since was arbitrary, this proves that

**Question 4**. Let be a set. A relation, , on is called a **partial order** if it satisfies three properties:

(1) (reflexivity)

(2) , (anti-symmetry)

(3) , (transitivity)

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

(a) Let with the relation . Prove that is a **partial order** on and prove that is *not* an equivalence relation on .

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

**Theorem**. If a relation, , on a set , is both a partial order and an equivalence relation, then for every , the cardinality of the equivalence class _______.

*proof.*

**Answer**. (a) The relation on is reflexive since for every it follows that and so .

The relation is anti-symmetric since if and it follows that and . These inequalities imply that , as desired.

The relation is transitive since if and we have that and . This can be expressed as the double-inequality which implies that and so .

Finally, is not an equivalence relation because it is not symmetric. For example, since , but since .

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

Let be an arbitrary element, and suppose . By definition of equivalence class, this means that . Because is an equivalence relation, symmetry implies that . Because is a partial order, we have that since and , it follows that .

This shows that . By reflexivity, it follows that and so for every element we have . In particular, we learn that for every .

**Question 5**. For this problem we will use the set of natural numbers, , and an arbitrary, two-element set .

Consider the two sets of functions

(a) Given the function

determine which statement is true: or .

(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 is countable.

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

**Answer**. (a) since the outputs of are elements of and the inputs of are elements of .

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

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

*proof*. Consider the function defined by

where is arbitrary. We can show that is a bijection, which will then imply that .

To show that is one-to-one, suppose . This means that which implies that and . Because the domain only contains the two elements and , it follows that the functions and are the same. Hence is one-to-one.

To show that is onto, let be arbitrary. Now consider the function defined by

.

By construction, and so 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 . We therefore have that is countable since

This completes the proof.

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

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

where each function . Similar to Cantor’s diagonalization argument, we can construct a function that does not equal *any* of the functions in our presumed list. Define by

By definition, and so, in particular, for any value of .