FOM Assignment

Problem 1.  Let S be a set with a partition P = \{U_i \subseteq S : i \in \mathcal{I} \}.  Prove that the definition

x \sim y \iff x, y \in U_i

defines an equivalence relation on S.

Problem 2.  (a) Let S be a set.  Prove that the relation defined by

x \sim y \iff x = y

is an equivalence relation.  Describe the set S/\sim.

(b) Let S be a set.  Prove that the relation defined by

x \sim y \iff x, y \in S

is an equivalence relation.  Describe the set S/\sim

Problem 3.  Let f:A\to B be a function from set A to set B.  Recall that a function g:B \to A is said to be the inverse of f if the composite functions f\circ g and g \circ f are identity functions; that is if

\forall \, b \in B, \,\, (f\circ g)(b) = b \,

\forall \, a \in A, \, \, (g\circ f)(a) = a \,

(a) Prove that this inverse function g exists \iff the function f is bijective.

(b) Prove that when this inverse function exists, it is unique.  (For this part, start by assuming that there are two functions, g_1:B\to A and g_2:B\to A that satisfy the definition of being an inverse and then prove that g_1(b) = g_2(b) for all b \in B.)

Problem 4.  Suppose f:A \to B is bijective and that g: B \to C is bijective.  Complete the following proof that the composite function

 g \circ f: A \to C

is also bijective.

proof.  To show g\circ f is one-to-one, let a_1, a_2 \in A and suppose that (g\circ f)(a_1) = (g\circ f)(a_2), i.e. that g(f(a_1)) = g(f(a_2)).  Since g:B\to C is bijective, g is also one-to-one.  If we label b_1 = f(a_1) and b_2 = f(a_2), then we have g(b_1) = g(b_2), and so it follows that ________________________.

We now have that f(a_1) = f(a_2), and so, again by the injectivity of f, it follows that ________________.

This shows that g(f(a_1)) = g(f(a_2)) \Rightarrow a_1 = a_2 and so g\circ f is one-to-one.

To show that the composite function g\circ f is ________, let c \in C be an arbitrary element.  We need to show that \, \exists \, a \in A so that ____________________________.  Since g:B\to C is surjective, there exists b \in B so that g(b) = c.  However, since f:A\to B is also surjective, there exists a \in A so that ________________.  Composing these results tells us that g(f(a)) = ____, completing the proof.  \square

Problem 5.  Consider the function f:(1, \infty) \to (0, \infty) given by

\displaystyle f(x) = \frac{1}{x-1}

(a) Is f one-to-one?  Prove your answer.

(b) Is f onto?  Prove your answer.

(c ) If your answers to the parts above are both “yes,” then find a formula for the function f^{-1}.  If your answers to the parts above are both “no,” then define a new function by either restricting the domain of f above and/or by restricting the co-domain of f above so that this new function is invertible.

Problem 6.  (a) Let (a, b) and (c, d) denote two intervals of real numbers, i.e. a, b, c, d \in \mathbb{R} and a < b and c < d.   Prove that

\left|\,(a,b)\,\right| = \left|\,(c,d)\,\right|.

(b)  Recall from Calculus the function f(x) = \arctan x.  Because the tangent function is not one-to-one, its inverse cannot be defined unless we restrict the tangent function’s domain to a sub-interval; if we restrict the tangent function’s domain to the open interval (-\pi/2, \pi/2) then it will have an inverse.  The arctangent function then has as its domain the entire real line, \mathbb{R}, and has as its codomain the open interval (-\pi/2, \pi/2).  That is

f:\mathbb{R} \to (-\pi/2, \pi/2)

Sketch a graph of y = f(x), and use this graph to argue that f is both onto and one-to-one.

(c ) Prove that every interval of real numbers, (a, b) = \{x \in \mathbb{R} : a < x < b\} satisfies

\left| \, (a, b) \, \right| = \left|\,\mathbb{R}\,\right|.

(d) Compose a short poem (say, a haiku or limerick) about the bizarreness of your conclusion in part (c ).  After all, you have now shown that every interval of points along the real line contains as many elements as the entire real line itself!

Problem 7.  (a)  Suppose A is a set with 3 elements and B is a set with 2 elements.  How many injective functions f:A\to B are there?  Explain your answer.

(b) Suppose A is a set with 3 elements and B is a set with 4 elements.  How many injective functions f:A\to B are there?  Explain your answer.

(c ) Explain why if A and B are finite sets with |A| > |B|, then there are no injective functions f:A \to B.

(d)  Suppose that A and B are finite sets with |A| = n \leq m = |B|.  How many injective functions f:A \to B are there?  Prove your answer.

Problem 8.  Exercises 4, 5, and 6 from Section 13.2

Problem 9.  Exercises 1, 3, and 6 from 13.3

Problem 10.  Observe that Corollary 13.1 does not address the cardinality of a (countably) infinite Cartesian product of countably infinite sets.  The point of this question is to explore when or if such a product is or isn’t countably infinite.

(a) Let A = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} and notate

\displaystyle S = \underbrace{A\times A \times \cdots }_{\mathbb{N} \text{ times}} = \prod_{i=1}^{\infty} \, A

Prove that |S| > |\mathbb{N}| by, in fact, showing that |S| \geq |(0,1)|.  That is, define / describe an injective function f:(0,1) \to S.

(b) Part (a) of this problem shows that the countably infinite product of finite sets is not necessarily countably infinite.  Observe that since A \subset \mathbb{Z}, we can build an injective function f:A \to \mathbb{Z} and, in fact, we can use this to build an injective function f:S \to \prod_{i=1}^{\infty} \, \mathbb{Z}, which shows that the countably infinite product of countably infinite sets is not countably infinite.

Instead of working with an infinite product like

\displaystyle \prod_{i=1}^{\infty} \, \mathbb{N} = \{ \left(x_1, x_2, x_3, \cdots \right) : x_i \in \mathbb{N} \}

consider the related set

T = \{ \left(x_1, x_2, x_3, \cdots \right) : x_i \in \mathbb{N} \text{ and all but finitely many } x_i = 0\}.

One can think of the first set as the set of all sequences of natural numbers, while the second set, T, is the set of all sequences of natural numbers that eventually terminate in an infinite string of 0s.

Prove that the set T above is, in fact, countably infinite.

 

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