# 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 $0$s.

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