Problem 1. Let be a set with a partition . Prove that the definition
defines an equivalence relation on .
Problem 2. (a) Let be a set. Prove that the relation defined by
is an equivalence relation. Describe the set .
(b) Let be a set. Prove that the relation defined by
is an equivalence relation. Describe the set
Problem 3. Let be a function from set to set . Recall that a function is said to be the inverse of if the composite functions and are identity functions; that is if
(a) Prove that this inverse function exists the function is bijective.
(b) Prove that when this inverse function exists, it is unique. (For this part, start by assuming that there are two functions, and that satisfy the definition of being an inverse and then prove that for all .)
Problem 4. Suppose is bijective and that is bijective. Complete the following proof that the composite function
is also bijective.
proof. To show is one-to-one, let and suppose that , i.e. that . Since is bijective, is also one-to-one. If we label and , then we have , and so it follows that ________________________.
We now have that , and so, again by the injectivity of , it follows that ________________.
This shows that and so is one-to-one.
To show that the composite function is ________, let be an arbitrary element. We need to show that so that ____________________________. Since is surjective, there exists so that . However, since is also surjective, there exists so that ________________. Composing these results tells us that ____, completing the proof.
Problem 5. Consider the function given by
(a) Is one-to-one? Prove your answer.
(b) Is onto? Prove your answer.
(c ) If your answers to the parts above are both “yes,” then find a formula for the function . If your answers to the parts above are both “no,” then define a new function by either restricting the domain of above and/or by restricting the co-domain of above so that this new function is invertible.
Problem 6. (a) Let and denote two intervals of real numbers, i.e. and and . Prove that
(b) Recall from Calculus the function . 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 then it will have an inverse. The arctangent function then has as its domain the entire real line, , and has as its codomain the open interval . That is
Sketch a graph of , and use this graph to argue that is both onto and one-to-one.
(c ) Prove that every interval of real numbers, satisfies
(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 is a set with elements and is a set with elements. How many injective functions are there? Explain your answer.
(b) Suppose is a set with elements and is a set with elements. How many injective functions are there? Explain your answer.
(c ) Explain why if and are finite sets with , then there are no injective functions .
(d) Suppose that and are finite sets with . How many injective functions 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 and notate
Prove that by, in fact, showing that . That is, define / describe an injective function .
(b) Part (a) of this problem shows that the countably infinite product of finite sets is not necessarily countably infinite. Observe that since , we can build an injective function and, in fact, we can use this to build an injective function , which shows that the countably infinite product of countably infinite sets is not countably infinite.
Instead of working with an infinite product like
consider the related set
One can think of the first set as the set of all sequences of natural numbers, while the second set, , is the set of all sequences of natural numbers that eventually terminate in an infinite string of s.
Prove that the set above is, in fact, countably infinite.