FOM Final (with answers)

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{|} = _______.


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


Leave a Reply

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

You are commenting using your 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